2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Алгоритм извлечения кубического корня ("в столбик")
Сообщение20.08.2009, 20:48 


22/05/09

685
Подскажите, пожалуйста, существует ли алгоритм извлечения кубического корня в столбик, аналогичный тому, что для квадратных корней? Пытался применять его по аналогии, но нашёл только один разряд. При извлечении корня второй степени число делят на "грани" по два разряда справа налево, а я брал по три и т.д. Моё число - $42875$, кубический корень из него - $35$.$3$ я нашёл, но как дойти до $5$?

 Профиль  
                  
 
 Re: Алгоритм извлечения кубического корня.
Сообщение20.08.2009, 21:27 
Заслуженный участник
Аватара пользователя


28/07/09
1178
Так он же ровно 35

 Профиль  
                  
 
 Re: Алгоритм извлечения кубического корня.
Сообщение20.08.2009, 21:48 


22/05/09

685
Legioner93 в сообщении #236591 писал(а):
Так он же ровно 35


Я знаю. Мне интересен алгоритм нахождения кубических корней.

-- Чт авг 20, 2009 22:58:04 --

Вот. Нашёл дореволюционный источник, но сути пока не понял.

Изображение

 Профиль  
                  
 
 Re: Алгоритм извлечения кубического корня.
Сообщение20.08.2009, 22:02 
Заслуженный участник
Аватара пользователя


11/04/08
2736
Физтех
Для начала хочу написать обоснования алгоритма для вычисления квадратного корня в столбик.

Пусть исходное число можно разбить на 2 разряда по 2 цифры. Значит его можно представить в виде

$\[
\left( {10a + b} \right)^2  = 100a^2  + 20ab + b^2 
\]$.

Первый шаг этого алгоритма уходит на то, чтобы найти число $a$.

Далее, $\[
20ab + b^2  = b\left( {10 \cdot \left( {2a} \right) + b} \right)
\]$.

Это, собственно обосновывает дальнейшие шаги (думаю, не сложно разобраться).

Если разрядов, скажем, 3, то фактически находим число в таком виде:

$\[
\left( {100a + 10b + c} \right)^2  = 10^4 a^2  + 100b\left[ {10 \cdot \left( {2a} \right) + b} \right] + c\left\{ {10\left[ {2\left( {10a + b} \right)} \right] + c} \right\}
\]$.

Теперь как поступать с кубическим корнем.

Пусть имеем 2 разряда по три цифры, как в нашем случае: $042'875$. Представим наше число в таком виде:

$\[
\left( {10a + b} \right)^3  = 1000a^3  + 3 \cdot 100a^2  \cdot b + 3 \cdot 10a \cdot b^2  + b^3 
\]$.

Первый шаг алгоритма аналогичен случаю для квадратного корня, первая цифра искомого числа - 3, возводим в куб - 27, вычитаем, получаем $015'875$. В нашем случае $a=3$, осталось распознать $\[
3 \cdot 100a^2  \cdot b + 3 \cdot 10a \cdot b^2  + b^3 
\]
$.

Теперь предлагаю такой маневр: получившееся число разбиваем уже по разрядам, содержащим 2 цифры: $01'58'75$. Теперь подбирается наибольшее $b$, чтобы число, составленное из цифр, идущих подряд с левого конца до последнего разряда (в нашем случае это число 158), было больше $27b$. Конечно, это число $b=5$.

В остатке получается число 2375. Оно сверяется с $\[
b^2 \left( {10\left( {3a} \right) + b} \right)
\]
$. Если равны - стоп, на выход - 35. Если не равны, то проверяем, какое из них меньше. Если остаток меньше - возвращаемся к предыдущему шагу, где подбираем $b$ - берем его на единицу меньше и продолжаем в том же духе. Если остаток больше (собственно это означает сами знаете что), то ... (надо додумать)

Ну наверно как-то так :)

 Профиль  
                  
 
 Re: Алгоритм извлечения кубического корня.
Сообщение20.08.2009, 22:03 


22/05/09

685
ShMaxG, спасибо! :) Постараюсь разобраться. А квадратные корни я извлекать умею.

 Профиль  
                  
 
 Re: Алгоритм извлечения кубического корня.
Сообщение20.08.2009, 22:07 
Заслуженный участник
Аватара пользователя


28/07/09
1178
Покажу один способ извлечения квадратных корней, по аналогии которого можно извлечь и кубический.
Допустим, вы хотите извлечь корень из 40. Он находится между 6 и 7. Пусть $\sqrt 40 =6+x$, тогда $40=x^2+12x+36$ Т.к x<1, то при первом приближении опустим квадратный член. Тогда $40=12x+36$, $x=\frac{1}{3}$.
$\sqrt 40 =6,3$ (Я написал $6,3$ вместо $6\frac{1}{3}$ потому что при первом приближении точность низка и даже сотые части писать уже бессмысленно.) Сделаем второе приближение.
$\sqrt 40 =6,3+x$, $40 =x^2+12,6x+39,69$, $40 =12,6x+39,7$, $x=0,02$. Т.е $\sqrt 40 =6,32$
При желании можно сделать еще 1-2 приближение. $x$ может получиться отрицательный, это нормально. Метод достаточно тупой, просто как вариант.

Так вот, по аналогии можно вычислить и куб. корень, только придется отбрасывать уже 2 члена (с кубом и квадратом), поэтому начальное приближение должно быть достаточно точное (до десятых).

 Профиль  
                  
 
 Re: Алгоритм извлечения кубического корня.
Сообщение20.08.2009, 22:48 
Заслуженный участник
Аватара пользователя


11/04/08
2736
Физтех
Собственно, что дальше:

Вычитаем остаток из $\[
b^2 \left( {10\left( {3a} \right) + b} \right)
\]$ и умножаем на тысячу, тогда следующая цифра $c$ (перед которой надо еще запятую поставить) будет определяться отсюда:

$\[
\left( {100a + 10b + c} \right)^3  - 1000A^3  = 3 \cdot 100A^2 c + 3 \cdot 10Ac^2  + c^3 
\]$, где $\[A = 10a + b\]$.

Далее - все повторяется. Раньше роль A играла цифра, теперь это число.

Я не думаю, что этот алгоритм работает быстро, возможно существует алгоритм куда выразительней :)
Но тем не менее...

 Профиль  
                  
 
 Re: Алгоритм извлечения кубического корня.
Сообщение20.08.2009, 22:53 


22/05/09

685
Legioner93, весьма оригинальный и простой способ. Большое спасибо! Но простой он только на первый взгляд. Если числа имеют знаков шесть, он приводит к очень сложным вычислениям. Да и с тремя знаками они далеко не просты...

 Профиль  
                  
 
 Re: Алгоритм извлечения кубического корня.
Сообщение21.08.2009, 00:08 
Заслуженный участник
Аватара пользователя


11/04/08
2736
Физтех
Между прочим, "эти дореволюционные методы" очень похожи на мои. Ну смотрите:

1) 4-ку понятно как находят.
2) Теперь надо найти две оставшиеся цифры, потому что число получится трехзначное (если оно целое).

Обратите внимание, что они число $24716$ разбили как и я на разряды по $2$ цифры (!). И далее как и я подбирают наибольшее число $b$ в моих обозначениях такое, что $\[3 \cdot a^2 b = 48b\]$ не превосходит $247$. Отсюда находят $b=4$.

Итак, что мы сделали: мы вычли $88716-40^3=24716$. Откуда слева $48$? А это коэффициент перед $b$ в $3a^{2}b$. Первая "$192$" - это $\[3 \cdot 40^2  \cdot 4\]$ (что означает "вторая" $192$ и $64$ - сообразите сами).

Так вот, число $21184$ - сумма этих трех, мы его вычитаем из $24716$ и получаем $3532$ (далее дописываем справа $536$).

Таким образом, мы фактически вычли $88716-44^3=3532$.

По моей "теории" осталось найти $c$ (если, конечно, корень - целое число).

Заменяем $a=4$, $b=4$ в моей "теории", получаем, что $c$ как-то находится отсюда:

$\[
\left( {44 + c} \right)^3  - 44^3  = 3 \cdot 44^2 c + 3 \cdot 44c^2  + c^3 
\]$.

Теперь, я думаю, понятно, что надо найти такое наибольшее $c$, которое (и т.д., продолжите сами). Что они собственно и делают.

Так что этот "дореволюционный пример" - демонстрация того, что я тут вам придумал :)

А справа, кстати, опечатки, там должно быть $\[
3 \times 44 \times 6^2 
\]$, а не $\[
3 \times 44 \times 16^2 
\]
$

 Профиль  
                  
 
 Re: Алгоритм извлечения кубического корня.
Сообщение21.08.2009, 06:38 
Заслуженный участник


08/04/08
8556
Если из каких-то несложных чисел корень извлекать, можно пользоваться цепными дробями.
Например:
$$\sqrt[3]{2}-1=\frac{1}{\sqrt[3]{4}+ \sqrt[3]{2}+1}=\frac{1}{3+(\sqrt[3]{4}-1)+ (\sqrt[3]{2}-1)}$$
$$\sqrt[3]{4}-1=\frac{1}{\sqrt[3]{4}+ 2\sqrt[3]{2}+1}=\frac{1}{4+(\sqrt[3]{4}-1)+ 2(\sqrt[3]{2}-1)}$$
а затем подставляете одно в другое много раз, потом просто упрощаете дробь.

А еще лучше использовать метод Ньютона:
Найти $\sqrt[3]{a} \Leftrightarrow$ решить уравнение $x^3-a=0$ и решаете его методом Ньютона (сходится очень быстро)

 Профиль  
                  
 
 Re: Алгоритм извлечения кубического корня.
Сообщение24.08.2009, 20:31 
Модератор
Аватара пользователя


11/01/06
5660
см. topic4987.html

 Профиль  
                  
 
 Re: Алгоритм извлечения кубического корня.
Сообщение02.12.2009, 20:28 


02/12/09
1
ShMaxG
с целым числом я разобрался , а вот как, к примеру посчитать кубический корень, для дробного числа?
1,12476.

 Профиль  
                  
 
 Re: Алгоритм извлечения кубического корня.
Сообщение02.12.2009, 20:50 
Заслуженный участник
Аватара пользователя


11/04/08
2736
Физтех
Да я уже и забыл, что я там напридумывал :)

А для вашего дробного первое, что приходит в голову, - домножить на $10^6$ исходное число, провести все эти хитрые операции и полученный ответ разделить на $100$.

 Профиль  
                  
 
 Re: Алгоритм извлечения кубического корня ("в столбик")
Сообщение22.01.2012, 15:04 


22/01/12
1
Удивительно, что профи-математики ТУТ так и не смогли внятно описать искомый алгоритм. Придется сделать мне - биологу.

Сначала для разминки корень квадратный:
Алгоритм такой. Имеем некое число. Например, 31843449. Разбиваем его на двойки справа налево. Каждая двойка даст в ответе свою цифру.

31’84’34’49|| 5643
25
100 х 6 6 84
36 6 36
1120 х 4 48 34
16 44 96
11280х 3 3 38 49
9 3 38 49
Считать начинаем слева. Ближайший «снизу» к 31 квадрат (25)имеет число $Х = 5$, ибо квадрат $Х+1=6 (36)$уже больше имеющихся 31. Разницу $31-25=6$ сносим и прибавляем к ней следующую пару цифр(84), получили число 684. Подбор каждого следующего числа Х в квадратном корне производится по формуле (20а х Х + Х^2), где а – это уже имеющееся число в ответе. Результат должен быть ближайшим «снизу» к числу 684. Имеем $а = 5.$ Для$ Х=6$ это будет $(20\cdot5=100 100\cdot6=600 600+36=636)$ 636. А для $Х=7 $соответственно ($(20\cdot5=100 100\cdot7=700 700+49=749).$ Ясно, что 7 –это перебор, так как 749 больше 684. Выбираем $Х=6$ и повторяем весь цикл для следующего числа. Разницу $684-636=48 $сносим и прибавляем к ней следующую пару 34. Получили число 4834. Теперь $а=56$, ищем следующую Х.
При $Х=4 (20\cdot56=1120 1120\cdot4=4480 4480+16=4496)$ формула дала 4496. При $Х=5 $формула даст 5625 – «перебор»! выбираем $Х=4$. Снова повторяем цикл. Разницу $4834-4496=338$ сносим, добавляем пару 49 получаем число 33849. Теперь $а=564$ применим формулу для $Х=3 (20\cdot564=11280 11280\cdot3=33840 33840+9=33849)$ Всё! Получили ответ без остатка. Если остаток есть, то сносим его, добавляем к нему два нуля справа и вновь повторяем цикл столько раз, сколько значащих цифр нам надо.

Описание громоздко для понятности, сам же расчет идет довольно легко и быстро. Этот алгоритм есть и в Вики-педии. Там он описан не менее громоздко. А теперь ТО(!!), что ни в Вики, ни в Гугле с Яндексом не нашел.

Алгоритм вычисления кубического корня.

82’881’856| 436
$4800\cdot3$ 64
$120\cdot9   $ 18 881
27 15 507
$554700\cdot6$
$1290\cdot36 $ 3 374 856
216 3 374 856

Теперь искомое число разбиваем справа налево на тройки, каждая из которых даст свою цифру в ответе. В последней левой «тройке» оказалось две цифры (82,) а могла быть и одна, и три. Ближайшее «снизу»$ Х=4$ имеет куб 64, а у $Х=5$ куб 125 уже «перебор» для 82. Разницу $82-64=18$ сносим и добавляем следующую тройку (881), получив число 18881. Следующее число Х в кубическом корне вычисляем по формуле, где логично уже не два компонента, а три:(300а^2 хХ + 30а х Х^2 + Х^3), чтобы результат был ближайшим «снизу». У нас сейчас $а=4$. Для $Х=3$ имеем: $(300\cdot16=4800\cdot3=14400 30\cdot4=120\cdot9=1080 3\cdot3\cdot3=27) 14400+1080+27=15507$. Для $Х=4$ соответственно $(300\cdot16\cdot4=19200 30\cdot4\cdot16=1920 4\cdot4\cdot4=64) 19200+1920+64=21184,$ что есть «перебор» для 18881, поэтому выбираем $Х=3$. Далее цикл повторяем. Разницу $18881-15507=3374$ сносим, к ней добавляем следующую тройку 856, получив число 3374856. На этом этапе$ а=43.$ Определяем Х. Для $Х=6 (300\cdot43\cdot43=554700\cdot6=3328200 30\cdot43\cdot36=46440 6\cdot6\cdot6=216) $Итого $3328200+46440+216=3374856$. Готово! Если же есть остаток и нам надо следующую цифру в ответе, добавляем к остатку три нуля и снова повторяем цикл.

-- 22.01.2012, 13:10 --

Ума не приложу как поправить автоматический разгром моего предыдущего сообщения тегом math : испортил всё , убрал все пробелы, часть символов и т.д. Тогда алгоритм повторю в ЖЖ http://afp-zp.livejournal.com/338860.html

-- 22.01.2012, 13:49 --

А если так?
Изображение

Изображение

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group