Алгоритм извлечения кубического корня ("в столбик")

[Mitrius_Math]

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

[Legioner93]

Так он же ровно 35

[Mitrius_Math]

Legioner93 в сообщении #236591 писал(а):

Так он же ровно 35

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

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

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

[ShMaxG]

Для начала хочу написать обоснования алгоритма для вычисления квадратного корня в столбик.

Пусть исходное число можно разбить на 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$ - берем его на единицу меньше и продолжаем в том же духе. Если остаток больше (собственно это означает сами знаете что), то ... (надо додумать)

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

[Mitrius_Math]

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

[Legioner93]

Покажу один способ извлечения квадратных корней, по аналогии которого можно извлечь и кубический.
Допустим, вы хотите извлечь корень из 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 члена (с кубом и квадратом), поэтому начальное приближение должно быть достаточно точное (до десятых).

[ShMaxG]

Собственно, что дальше:

Вычитаем остаток из $\[ 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 играла цифра, теперь это число.

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

[Mitrius_Math]

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

[ShMaxG]

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

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 \] $

[Sonic86]

Если из каких-то несложных чисел корень извлекать, можно пользоваться цепными дробями.
Например:

$$\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$ и решаете его методом Ньютона (сходится очень быстро)

[maxal]

см. topic4987.html

[Vlad]

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

[ShMaxG]

Да я уже и забыл, что я там напридумывал

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

[AFPzp]

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

Сначала для разминки корень квадратный:
Алгоритм такой. Имеем некое число. Например, 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 --

А если так?