Методы вычисления квадратных корней

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages) This article possibly contains original research. Please improve it by verifying the claims made and adding inline citations. Statements consisting only of original research should be removed. (January 2012) (Learn how and when to remove this message) This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details. (September 2012) (Learn how and when to remove this message) (Learn how and when to remove this message)

Методы вычисления квадратных корней — это алгоритмы для аппроксимации неотрицательного квадратного корня положительного действительного числа . Поскольку все квадратные корни натуральных чисел , кроме полных квадратов , являются иррациональными , ^[1] квадратные корни обычно можно вычислить только с некоторой конечной точностью: эти методы обычно строят ряд все более точных аппроксимаций .${\displaystyle {\sqrt {S}}}$ ${\displaystyle S}$

Большинство методов вычисления квадратного корня являются итеративными: после выбора подходящей начальной оценки выполняется итеративное уточнение до тех пор, пока не будет выполнен некоторый критерий завершения. Одной из схем уточнения является метод Герона, частный случай метода Ньютона . Если деление намного более затратно, чем умножение, может быть предпочтительнее вычислить вместо этого обратный квадратный корень.${\displaystyle {\sqrt {S}}}$

Другие методы доступны для вычисления квадратного корня цифра за цифрой или с использованием ряда Тейлора. Рациональные приближения квадратных корней могут быть вычислены с использованием расширений непрерывных дробей.

Применяемый метод зависит от необходимой точности, а также доступных инструментов и вычислительной мощности. Методы можно грубо классифицировать как подходящие для устного расчета, те, которые обычно требуют как минимум бумаги и карандаша, и те, которые реализованы в виде программ для выполнения на цифровом электронном компьютере или другом вычислительном устройстве. Алгоритмы могут учитывать сходимость (сколько итераций требуется для достижения заданной точности), вычислительную сложность отдельных операций (например, деления) или итераций и распространение ошибок (точность конечного результата).

Некоторые методы, такие как синтетическое деление на бумаге и карандаше и расширение ряда, не требуют начального значения. В некоторых приложениях требуется целочисленный квадратный корень , который представляет собой квадратный корень, округленный или усеченный до ближайшего целого числа (в этом случае может использоваться модифицированная процедура).

Процедуры нахождения квадратных корней (в частности, квадратного корня из 2 ) известны по крайней мере с периода древнего Вавилона в 17 веке до н. э. Вавилонские математики вычисляли квадратный корень из 2 до трех шестидесятеричных «цифр» после 1, но точно не известно, как. Они знали, как аппроксимировать гипотенузу, используя (например, для диагонали ворот, высота которых составляет прутьев, а ширина — прутьев), и они, возможно, использовали аналогичный подход для нахождения аппроксимации ^[2]$${\displaystyle {\sqrt {a^{2}+b^{2}}}\approx a+{\frac {b^{2}}{2a}}}$$${\displaystyle {\frac {41}{60}}+{\frac {15}{3600}}}$${\displaystyle {\frac {40}{60}}}$${\displaystyle {\frac {10}{60}}}$${\displaystyle {\sqrt {2}}.}$

Метод Герона из Египта первого века был первым установленным алгоритмом вычисления квадратного корня. ^[3]

Современные аналитические методы начали разрабатываться после введения арабской системы счисления в Западной Европе в эпоху раннего Возрождения. ^{[ необходима ссылка ]}

Сегодня почти все вычислительные устройства имеют быструю и точную функцию квадратного корня, либо как конструкцию языка программирования, либо как встроенную или библиотечную функцию компилятора, либо как аппаратный оператор, основанный на одной из описанных процедур.

Многие итеративные алгоритмы квадратного корня требуют начального начального значения . Начальное значение должно быть ненулевым положительным числом; оно должно быть между 1 и , числом, квадратный корень которого требуется, поскольку квадратный корень должен быть в этом диапазоне. Если начальное значение находится далеко от корня, алгоритму потребуется больше итераций. Если инициализировать с помощью (или ), то приблизительные итерации будут потрачены впустую только на получение порядка величины корня. Поэтому полезно иметь грубую оценку, которая может иметь ограниченную точность, но ее легко вычислить. В общем, чем лучше начальная оценка, тем быстрее сходимость. Для метода Ньютона начальное значение, несколько большее, чем корень, будет сходиться немного быстрее, чем начальное значение, несколько меньшее, чем корень.${\displaystyle S}$${\displaystyle x_{0}=1}$${\displaystyle S}$${\displaystyle {\tfrac {1}{2}}\vert \log _{2}S\vert }$

В общем случае оценка соответствует произвольному интервалу, который, как известно, содержит корень (например, ). Оценка представляет собой определенное значение функционального приближения к на интервале. Получение лучшей оценки включает либо получение более узких границ на интервале, либо нахождение лучшего функционального приближения к . Последнее обычно означает использование полинома более высокого порядка в приближении, хотя не все приближения являются полиномиальными. Распространенные методы оценки включают скалярный, линейный, гиперболический и логарифмический. Десятичное основание обычно используется для умственной или бумажно-карандашной оценки. Двоичное основание больше подходит для компьютерных оценок. При оценке показатель степени и мантисса обычно обрабатываются отдельно, так как число будет выражено в научной нотации.${\displaystyle [x_{0},S/x_{0}]}$${\displaystyle f(x)={\sqrt {x}}}$${\displaystyle f(x)}$

Обычно число выражается в экспоненциальной записи как , где и n — целое число, а диапазон возможных квадратных корней равен , где . ${\displaystyle S}$${\displaystyle a\times 10^{2n}}$${\displaystyle 1\leq a<100}$${\displaystyle {\sqrt {a}}\times 10^{n}}$${\displaystyle 1\leq {\sqrt {a}}<10}$

Скалярные методы делят диапазон на интервалы, и оценка в каждом интервале представлена ​​одним скалярным числом. Если диапазон рассматривается как один интервал, среднее арифметическое (5,5) или среднее геометрическое ( ) раз являются правдоподобными оценками. Абсолютная и относительная погрешность для них будет отличаться. В общем случае один скаляр будет очень неточным. Лучшие оценки делят диапазон на два или более интервалов, но скалярные оценки имеют изначально низкую точность.${\displaystyle {\sqrt {10}}\approx 3.16}$${\displaystyle 10^{n}}$

Для двух интервалов, разделенных геометрически, квадратный корень можно оценить как ^{[Примечание 1]}${\displaystyle {\sqrt {S}}={\sqrt {a}}\times 10^{n}}$$${\displaystyle {\sqrt {S}}\approx {\begin{cases}2\cdot 10^{n}&{\text{if }}a<10,\\6\cdot 10^{n}&{\text{if }}a\geq 10.\end{cases}}}$$

Эта оценка имеет максимальную абсолютную погрешность при a = 100 и максимальную относительную погрешность 100% при a = 1.${\displaystyle 4\cdot 10^{n}}$

Например, для факторизованного как оценка составляет . , абсолютная погрешность составляет 246, а относительная погрешность — почти 70%.${\displaystyle S=125348}$${\displaystyle 12.5348\times 10^{4}}$${\displaystyle {\sqrt {S}}\approx 6\cdot 10^{2}=600}$${\displaystyle {\sqrt {125348}}=354.0}$

Лучшая оценка и стандартный используемый метод — это линейное приближение функции по малой дуге. Если, как указано выше, степени основания выносятся за скобки из числа , а интервал сокращается до , в качестве приближения можно использовать секущую линию, охватывающую дугу, или касательную линию где-то вдоль дуги, но линия регрессии наименьших квадратов, пересекающая дугу, будет более точной.${\displaystyle y=x^{2}}$${\displaystyle S}$${\displaystyle [1,100]}$

Линия регрессии наименьших квадратов минимизирует среднюю разницу между оценкой и значением функции. Ее уравнение . Переупорядочение, . Округление коэффициентов для простоты вычислений,${\displaystyle y=8.7x-10}$${\displaystyle x=0.115y+1.15}$$${\displaystyle {\sqrt {S}}\approx (a/10+1.2)\cdot 10^{n}}$$

Это наилучшая оценка в среднем , которая может быть достигнута с помощью однокомпонентной линейной аппроксимации функции y=x ² в интервале . Она имеет максимальную абсолютную погрешность 1,2 при a=100 и максимальную относительную погрешность 30% при S=1 и 10. ^{[Примечание 2]}${\displaystyle [1,100]}$

Чтобы разделить на 10, вычтите единицу из показателя степени или, образно говоря, переместите десятичную точку на одну цифру влево. Для этой формулы любая аддитивная константа 1 плюс небольшой прирост дадут удовлетворительную оценку, поэтому запоминание точного числа не будет обузой. Аппроксимация (округленная или нет) с использованием одной линии, охватывающей диапазон, составляет менее одной значащей цифры точности; относительная погрешность больше 1/2 ² , поэтому предоставляется менее 2 бит информации. Точность сильно ограничена, поскольку диапазон составляет два порядка величины, что довольно много для такого рода оценки. ${\displaystyle a}$${\displaystyle [1,100]}$

Гораздо лучшую оценку можно получить с помощью кусочно-линейной аппроксимации: несколько отрезков прямой, каждый из которых аппроксимирует некоторую поддугу исходной. Чем больше отрезков прямой используется, тем лучше аппроксимация. Наиболее распространенный способ — использовать касательные линии; критический выбор — как разделить дугу и где разместить точки касания. Эффективный способ разделить дугу от y  = 1 до y  = 100 — геометрический: для двух интервалов границы интервалов являются квадратным корнем границ исходного интервала, 1×100, т. е. [1, ² √ 100 ] и [ ² √ 100 ,100]. Для трех интервалов границы — кубические корни из 100: [1, ³ √ 100 ], [ ³ √ 100 ,( ³ √ 100 ) ² ], и [( ³ √ 100 ) ² ,100] и т. д. Для двух интервалов ² √ 100 = 10, очень удобное число. Касательные линии легко вывести, и они расположены в точках x = √ 1* √ 10 и x = √ 10* √ 10 . Их уравнения: и . Инвертируя, квадратные корни: и . Таким образом, для :${\displaystyle y=3.56x-3.16}$${\displaystyle y=11.2x-31.6}$${\displaystyle x=0.28y+0.89}$${\displaystyle x=.089y+2.8}$${\displaystyle S=a\cdot 10^{2n}}$$${\displaystyle {\sqrt {S}}\approx {\begin{cases}(0.28a+0.89)\cdot 10^{n}&{\text{if }}a<10,\\(.089a+2.8)\cdot 10^{n}&{\text{if }}a\geq 10.\end{cases}}}$$

Максимальные абсолютные погрешности возникают в верхних точках интервалов при a = 10 и 100 и составляют 0,54 и 1,7 соответственно. Максимальные относительные погрешности возникают в конечных точках интервалов при a = 1, 10 и 100 и составляют 17% в обоих случаях. 17% или 0,17 больше 1/10, поэтому метод дает точность менее десятичного знака.

В некоторых случаях гиперболические оценки могут быть эффективными, поскольку гипербола также является выпуклой кривой и может лежать вдоль дуги y  =  x ² лучше, чем вдоль прямой. Гиперболические оценки более сложны в вычислительном отношении, поскольку они обязательно требуют плавающего деления. Почти оптимальное гиперболическое приближение к x ² на интервале равно y = 190/(10−x) − 20. Транспонируя, квадратный корень равен x  = 10 − 190/(y+20). Таким образом, для :${\displaystyle [1,100]}$${\displaystyle S=a\cdot 10^{2n}}$$${\displaystyle {\sqrt {S}}\approx \left(10-{\frac {190}{a+20}}\right)\cdot 10^{n}}$$

Деление должно быть точным только до одной десятичной цифры, потому что общая оценка точна только настолько и может быть сделана в уме. Эта гиперболическая оценка в среднем лучше, чем скалярные или линейные оценки. Она имеет максимальную абсолютную погрешность 1,58 при a  = 100 и максимальную относительную погрешность при a  = 10, где оценка 3,67 на 16,0% выше корня из 3,16. Если вместо этого выполнить итерации Ньютона-Рафсона, начиная с оценки 10, потребуется две итерации, чтобы получить 3,66, что соответствует гиперболической оценке. Для более типичного случая, такого как 75, гиперболическая оценка 8,00 составляет всего 7,6% ниже, и для получения более точного результата потребуется 5 итераций Ньютона-Рафсона, начиная с 75.

Метод, аналогичный кусочно-линейной аппроксимации, но использующий только арифметику вместо алгебраических уравнений, использует таблицы умножения в обратном порядке: квадратный корень числа от 1 до 100 находится между 1 и 10, поэтому, если мы знаем, что 25 — это полный квадрат (5 × 5), а 36 — это полный квадрат (6 × 6), то квадратный корень числа, большего или равного 25, но меньшего 36, начинается с 5. Аналогично для чисел между другими квадратами. Этот метод даст правильную первую цифру, но он не точен до одной цифры: первая цифра квадратного корня из 35, например, равна 5, но квадратный корень из 35 почти равен 6.

Лучший способ — разделить диапазон на интервалы посередине между квадратами. Так, любое число от 25 до половины 36, что равно 30,5, оценивается как 5; любое число больше 30,5 до 36, оценивается как 6. ^{[Примечание 3]} Процедура требует лишь немного арифметики, чтобы найти граничное число посередине двух произведений из таблицы умножения. Вот справочная таблица этих границ:

а	ближайшая площадь	${\displaystyle k={\sqrt {a}}}$стандартное восточное время.
1
	1 (= 1 2 )	1
2.5
	4 (= 2 2 )	2
6.5
	9 (= 3 2 )	3
12.5
	16 (= 4 2 )	4
20.5
	25 (= 5 2 )	5
30.5
	36 (= 6 2 )	6
42.5
	49 (= 7 2 )	7
56.5
	64 (= 8 2 )	8
72,5
	81 (= 9 2 )	9
90,5
	100 (= 10 2 )	10
100

Последняя операция — умножить оценку k на степень десяти, деленную на 2, так что для ,${\displaystyle S=a\cdot 10^{2n}}$$${\displaystyle {\sqrt {S}}\approx k\cdot 10^{n}}$$

Метод неявно обеспечивает одну значимую цифру точности, поскольку округляет до лучшей первой цифры.

Метод может быть расширен на 3 значащие цифры в большинстве случаев путем интерполяции между ближайшими квадратами, ограничивающими операнд. Если , то приблизительно равно k плюс дробь, разница между a и k ² делится на разницу между двумя квадратами: где${\displaystyle k^{2}\leq a<(k+1)^{2}}$${\displaystyle {\sqrt {a}}}$$${\displaystyle {\sqrt {a}}\approx k+R}$$$${\displaystyle R={\frac {(a-k^{2})}{(k+1)^{2}-k^{2}}}}$$

Последняя операция, как и выше, заключается в умножении результата на степень числа десять, деленную на 2;$${\displaystyle {\sqrt {S}}={\sqrt {a}}\cdot 10^{n}\approx (k+R)\cdot 10^{n}}$$

k — десятичная цифра, а R — дробь, которую необходимо преобразовать в десятичную. Обычно она имеет только одну цифру в числителе и одну или две цифры в знаменателе, поэтому преобразование в десятичную можно выполнить в уме.

Пример: найдите квадратный корень из 75. 75 = 75 × 10 ^{2  · 0} , поэтому a равно 75, а n равно 0. Из таблиц умножения квадратный корень мантиссы должен быть 8-точечным чем-то , потому что a находится между 8×8 = 64 и 9×9 = 81, поэтому k равно 8; что-то — это десятичное представление R . Дробь R равна 75 − k ² = 11, числителю, и 81 − k ² = 17, знаменателю. 11/17 немного меньше, чем 12/18 = 2/3 = .67, поэтому предположим, что .66 (здесь можно угадывать, ошибка очень мала). Окончательная оценка составляет 8 + .66 = 8.66 . √ 75 до трех значащих цифр равно 8,66, поэтому оценка хороша до трех значащих цифр. Не все такие оценки с использованием этого метода будут настолько точными, но они будут близки.

При работе в двоичной системе счисления ( как это делают компьютеры) квадратный корень можно оценить как${\displaystyle S}$${\displaystyle a\times 2^{2n}}$${\displaystyle 0.1_{2}\leq a<10_{2}}$${\displaystyle {\sqrt {S}}={\sqrt {a}}\times 2^{n}}$$${\displaystyle {\sqrt {S}}\approx (0.485+0.485\cdot a)\cdot 2^{n}}$$

что является линией регрессии наименьших квадратов к коэффициентам с тремя значащими цифрами. имеет максимальную абсолютную погрешность 0,0408 при =2 и максимальную относительную погрешность 3,0% при =1. Удобная для вычислений округленная оценка (поскольку коэффициенты являются степенями 2) выглядит так:${\displaystyle {\sqrt {a}}}$${\displaystyle a}$${\displaystyle a}$

${\displaystyle {\sqrt {S}}\approx (0.5+0.5\cdot a)\cdot 2^{n}}$^{[Примечание 4]}

что имеет максимальную абсолютную погрешность 0,086 при 2 и максимальную относительную погрешность 6,1% при a = 0,5 и a = 2,0 .

Для двоичное приближение дает . , поэтому оценка имеет абсолютную погрешность 19 и относительную погрешность 5,3%. Относительная погрешность немного меньше 1/2 ⁴ , поэтому оценка верна до 4+ бит.${\displaystyle S=125348=1\;1110\;1001\;1010\;0100_{2}=1.1110\;1001\;1010\;0100_{2}\times 2^{16}\,}$${\displaystyle {\sqrt {S}}\approx (0.5+0.5\cdot a)\cdot 2^{8}=1.0111\;0100\;1101\;0010_{2}\cdot 1\;0000\;0000_{2}=1.456\cdot 256=372.8}$${\displaystyle {\sqrt {125348}}=354.0}$

Оценку для good to 8 bits можно получить, просмотрев таблицу по старшим 8 битам , помня, что старший бит подразумевается в большинстве представлений с плавающей точкой, а младший бит 8 должен быть округлен. Таблица представляет собой 256 байт предварительно вычисленных 8-битных значений квадратного корня. Например, для индекса 11101101 _{2 ,} представляющего 1,8515625 ₁₀ , запись будет 10101110 ₂ , представляющего 1,359375 ₁₀ , квадратный корень 1,8515625 ₁₀ с точностью до 8 бит (2+ десятичных знака).${\displaystyle a}$${\displaystyle a}$

Первый явный алгоритм аппроксимации известен как метод Герона , в честь греческого математика первого века Герона Александрийского , который описал этот метод в своей работе «Метрика» в 60 году нашей эры . ^[3] Этот метод также называют вавилонским методом (не путать с вавилонским методом аппроксимации гипотенуз), хотя нет никаких доказательств того, что этот метод был известен вавилонянам .${\displaystyle \ {\sqrt {S~}}\ }$

Дано положительное действительное число , пусть x ₀ > 0 — любая положительная начальная оценка. Метод Герона заключается в итеративном вычислении до тех пор, пока не будет достигнута желаемая точность. Последовательность, определяемая этим уравнением, сходится к${\displaystyle S}$$${\displaystyle x_{n+1}={\frac {1}{2}}\left(x_{n}+{\frac {S}{x_{n}}}\right),}$$${\displaystyle \ {\bigl (}\ x_{0},\ x_{1},\ x_{2},\ x_{3},\ \ldots \ {\bigr )}\ }$${\displaystyle \ \lim _{n\to \infty }x_{n}={\sqrt {S~}}~.}$

Это эквивалентно использованию метода Ньютона для решения . Этот алгоритм квадратично сходится : количество правильных цифр примерно удваивается с каждой итерацией.${\displaystyle x^{2}-S=0}$${\displaystyle x_{n}}$

Основная идея заключается в том, что если является завышенной оценкой квадратного корня неотрицательного действительного числа, то будет заниженной оценкой, и наоборот, поэтому можно обоснованно ожидать, что среднее значение этих двух чисел обеспечит лучшее приближение (хотя формальное доказательство этого утверждения зависит от неравенства арифметических и геометрических средних значений , которое показывает, что это среднее значение всегда является завышенной оценкой квадратного корня, как отмечено в статье о квадратных корнях , тем самым обеспечивая сходимость). ${\displaystyle \ x\ }$${\displaystyle \ S\ }$${\displaystyle \ {\tfrac {\ S\ }{x}}\ }$

Точнее, если — наше первоначальное предположение, а — ошибка в нашей оценке, так что мы можем разложить бином как: и решить для определения ошибки${\displaystyle \ x\ }$${\displaystyle \ {\sqrt {S~}}\ }$${\displaystyle \ \varepsilon \ }$${\displaystyle \ S=\left(x+\varepsilon \right)^{2}\ ,}$$${\displaystyle \ {\bigl (}\ x+\varepsilon \ {\bigr )}^{2}=x^{2}+2x\varepsilon +\varepsilon ^{2}}$$

${\displaystyle \varepsilon ={\frac {\ S-x^{2}\ }{\ 2x+\varepsilon \ }}\approx {\frac {\ S-x^{2}\ }{2x}}\ ,}$если мы предположим, что${\displaystyle \ \varepsilon \ll x~}$

Поэтому мы можем компенсировать ошибку и обновить нашу старую оценку как Поскольку вычисленная ошибка не была точной, это не фактический ответ, а становится нашей новой догадкой для использования в следующем раунде исправления. Процесс обновления повторяется до тех пор, пока не будет достигнута желаемая точность.$${\displaystyle \ x+\varepsilon \ \approx \ x+{\frac {\ S-x^{2}\ }{2x}}\ =\ {\frac {\ S+x^{2}\ }{2x}}\ =\ {\frac {\ {\frac {S}{\ x\ }}+x\ }{2}}\ \equiv \ x_{\mathsf {revised}}~.}$$

Этот алгоритм одинаково хорошо работает в p -адических числах , но не может быть использован для идентификации действительных квадратных корней с p -адическими квадратными корнями; например, с помощью этого метода можно построить последовательность рациональных чисел, которая сходится к +3 в действительных числах, но к −3 в 2-адических числах.

Для расчета до семи значащих цифр используйте метод грубой оценки, описанный выше, чтобы получить${\displaystyle {\sqrt {S\,}}}$${\displaystyle S=125348}$$${\displaystyle {\begin{alignedat}{5}x_{0}&=6\cdot 10^{2}&&&&=600\\[0.3em]x_{1}&={\frac {1}{2}}\left(x_{0}+{\frac {S}{x_{0}}}\right)&&={\frac {1}{2}}\left(600{\phantom {.1}}+{\frac {125348}{600}}\right)&&=404.457\approx 400\\[0.3em]x_{2}&={\frac {1}{2}}\left(x_{1}+{\frac {S}{x_{1}}}\right)&&={\frac {1}{2}}\left(400{\phantom {.1}}+{\frac {125348}{400}}\right)&&=356.685\approx 360\\[0.3em]x_{3}&={\frac {1}{2}}\left(x_{2}+{\frac {S}{x_{2}}}\right)&&={\frac {1}{2}}\left(360{\phantom {.1}}+{\frac {125348}{360}}\right)&&=354.094\approx 354.1\\[0.3em]x_{4}&={\frac {1}{2}}\left(x_{3}+{\frac {S}{x_{3}}}\right)&&={\frac {1}{2}}\left(354.1+{\frac {125348}{354.1}}\right)&&=354.045199\end{alignedat}}}$$

Следовательно, до семи знаков после запятой. (Истинное значение равно 354,0451948551....) Обратите внимание, что ранние итерации требовалось вычислить только до 1, 2 или 4 знаков, чтобы получить точный окончательный ответ.${\displaystyle {\sqrt {\,125348\,}}\approx 354.0452}$

Предположим, что Тогда для любого натурального числа Пусть относительная погрешность определяется как и, таким образом,${\displaystyle \ x_{0}>0~~{\mathsf {and}}~~S>0~.}$${\displaystyle \ n:x_{n}>0~.}$${\displaystyle \ x_{n}\ }$$${\displaystyle \ \varepsilon _{n}={\frac {~x_{n}\ }{\ {\sqrt {S~}}\ }}-1>-1\ }$$$${\displaystyle \ x_{n}={\sqrt {S~}}\cdot \left(1+\varepsilon _{n}\right)~.}$$

Тогда можно показать, что$${\displaystyle \ \varepsilon _{n+1}={\frac {\varepsilon _{n}^{2}}{2(1+\varepsilon _{n})}}\geq 0~.}$$

И таким образом , и следовательно, что сходимость обеспечена, причем квадратичная .$${\displaystyle \ \varepsilon _{n+2}\leq \min \left\{\ {\frac {\ \varepsilon _{n+1}^{2}\ }{2}},{\frac {\ \varepsilon _{n+1}\ }{2}}\ \right\}\ }$$

Если использовать приведенную выше грубую оценку с использованием вавилонского метода, то наименее точные случаи в порядке возрастания будут следующими:$${\displaystyle {\begin{aligned}S&=\ 1\ ;&x_{0}&=\ 2\ ;&x_{1}&=\ 1.250\ ;&\varepsilon _{1}&=\ 0.250~.\\S&=\ 10\ ;&x_{0}&=\ 2\ ;&x_{1}&=\ 3.500\ ;&\varepsilon _{1}&<\ 0.107~.\\S&=\ 10\ ;&x_{0}&=\ 6\ ;&x_{1}&=\ 3.833\ ;&\varepsilon _{1}&<\ 0.213~.\\S&=\ 100\ ;&x_{0}&=\ 6\ ;&x_{1}&=\ 11.333\ ;&\varepsilon _{1}&<\ 0.134~.\end{aligned}}}$$

Таким образом, в любом случае,$${\displaystyle {\begin{aligned}\varepsilon _{1}&\leq 2^{-2}.\\\varepsilon _{2}&<2^{-5}<10^{-1}~.\\\varepsilon _{3}&<2^{-11}<10^{-3}~.\\\varepsilon _{4}&<2^{-23}<10^{-6}~.\\\varepsilon _{5}&<2^{-47}<10^{-14}~.\\\varepsilon _{6}&<2^{-95}<10^{-28}~.\\\varepsilon _{7}&<2^{-191}<10^{-57}~.\\\varepsilon _{8}&<2^{-383}<10^{-115}~.\end{aligned}}}$$

Ошибки округления замедляют сходимость. Рекомендуется сохранять по крайней мере одну дополнительную цифру за пределами желаемой точности вычислений , чтобы избежать значительной ошибки округления.${\displaystyle \ x_{n}\ }$

Этот метод нахождения приближения к квадратному корню был описан в древнеиндийской рукописи , называемой рукописью Бахшали . Он алгебраически эквивалентен двум итерациям метода Герона и, таким образом, является четвертично сходящимся, что означает, что количество правильных цифр приближения примерно учетверяется с каждой итерацией. ^[4] Оригинальное представление с использованием современных обозначений выглядит следующим образом: Чтобы вычислить , пусть будет начальным приближением к . Затем последовательно выполните итерации как:${\displaystyle {\sqrt {S}}}$${\displaystyle x_{0}^{2}}$${\displaystyle S}$$${\displaystyle {\begin{aligned}a_{n}&={\frac {S-x_{n}^{2}}{2x_{n}}},\\x_{n+1}&=x_{n}+a_{n},\\x_{n+2}&=x_{n+1}-{\frac {a_{n}^{2}}{2x_{n+1}}}.\end{aligned}}}$$

Значения и точно такие же, как и те, которые вычисляются методом Герона. Чтобы увидеть это, второй шаг метода Герона вычислит и мы можем использовать определения и для перестановки числителя в:${\displaystyle x_{n+1}}$${\displaystyle x_{n+2}}$$${\displaystyle x_{n+2}={\frac {x_{n+1}^{2}+S}{2x_{n+1}}}=x_{n+1}+{\frac {S-x_{n+1}^{2}}{2x_{n+1}}}}$$${\displaystyle x_{n+1}}$${\displaystyle a_{n}}$$${\displaystyle {\begin{aligned}S-x_{n+1}^{2}&=S-(x_{n}+a_{n})^{2}\\&=S-x_{n}^{2}-2x_{n}a_{n}-a_{n}^{2}\\&=S-x_{n}^{2}-(S-x_{n}^{2})-a_{n}^{2}\\&=-a_{n}^{2}.\end{aligned}}}$$

Это можно использовать для построения рационального приближения к квадратному корню, начиная с целого числа. Если — целое число, выбранное так, чтобы оно было близко к , а — разность, абсолютное значение которой минимизировано, то первую итерацию можно записать как:${\displaystyle x_{0}=N}$${\displaystyle N^{2}}$${\displaystyle S}$${\displaystyle d=S-N^{2}}$$${\displaystyle {\sqrt {S}}\approx N+{\frac {d}{2N}}-{\frac {d^{2}}{8N^{3}+4Nd}}={\frac {8N^{4}+8N^{2}d+d^{2}}{8N^{3}+4Nd}}={\frac {N^{4}+6N^{2}S+S^{2}}{4N^{3}+4NS}}={\frac {N^{2}(N^{2}+6S)+S^{2}}{4N(N^{2}+S)}}.}$$

Метод Бахшали можно обобщить для вычисления произвольного корня, включая дробные корни. ^[5]

Можно было бы подумать, что вторая половина метода Бахшали может быть использована как более простая форма итерации Герона и использоваться многократно, например, однако, это численно нестабильно . Без какой-либо ссылки на исходное входное значение точность ограничена точностью исходного вычисления , и это быстро становится неадекватным.$${\displaystyle {\begin{aligned}a_{n+1}&={\frac {-a_{n}^{2}}{2x_{n+1}}},&x_{n+2}&=x_{n+1}+a_{n+1},\\a_{n+2}&={\frac {-a_{n+1}^{2}}{2x_{n+2}}},&x_{n+3}&=x_{n+2}+a_{n+2},{\text{ etc.}}\end{aligned}}}$$${\displaystyle S}$${\displaystyle a_{n}}$

Используя тот же пример, что и в примере метода Герона, первая итерация дает${\displaystyle S=125348}$$${\displaystyle {\begin{alignedat}{3}x_{0}&=600\\[1ex]a_{0}&={\frac {125348-600^{2}}{2\times 600}}&&=-195.5433\approx -200\\[1ex]x_{1}&=600+(-200)&&={\phantom {-}}400\\[1ex]x_{2}&=400-{\frac {(-200)^{2}}{2\times 400}}&&={\phantom {-}}350\end{alignedat}}}$$

Аналогично вторая итерация дает В отличие от метода Герона, необходимо вычислить до 8 цифр, поскольку формула для не исправляет никаких ошибок в .$${\displaystyle {\begin{alignedat}{3}a_{2}&={\frac {125348-350^{2}}{2\times 350}}&&={\phantom {00}}4.06857\\[1ex]x_{3}&=350+4.06857&&=354.06857\\[1ex]x_{4}&=354.06857-{\frac {4.06857^{2}}{2\times 354.06857}}&&=354.045194\end{alignedat}}}$$${\displaystyle x_{3}}$${\displaystyle x_{4}}$${\displaystyle x_{3}}$

This section is missing information about identity and origin of this algorithm. Please expand the section to include this information. Further details may exist on the talk page. (August 2023)

Это метод нахождения каждой цифры квадратного корня в последовательности. Этот метод основан на биномиальной теореме и по сути является обратным алгоритмом решения . Он медленнее вавилонского метода, но имеет несколько преимуществ:${\displaystyle (x+y)^{2}=x^{2}+2xy+y^{2}}$

• Это может быть проще для ручных расчетов.
• Каждая найденная цифра корня заведомо верна, т.е. ее не нужно менять в дальнейшем.
• Если квадратный корень имеет расширение, которое завершается, алгоритм завершается после нахождения последней цифры. Таким образом, его можно использовать для проверки, является ли заданное целое число квадратным числом .
• Алгоритм работает для любой базы , и, естественно, способ его реализации зависит от выбранной базы.

Недостатки:

• Для более высоких корней это становится неуправляемым.
• Он не терпит неточных догадок или подвычислений; такие ошибки приводят к тому, что каждая последующая цифра результата оказывается неверной, в отличие от метода Ньютона , который самостоятельно исправляет любые ошибки аппроксимации.
• Хотя поразрядный расчет достаточно эффективен на бумаге, он слишком дорог для программной реализации. Каждая итерация включает в себя более крупные числа, требуя больше памяти, но продвигает ответ только на одну правильную цифру. Таким образом, алгоритму требуется больше времени для каждой дополнительной цифры.

Кости Нейпира включают в себя вспомогательное средство для выполнения этого алгоритма. Алгоритм сдвига n-го корня является обобщением этого метода.

Сначала рассмотрим случай нахождения квадратного корня числа S , то есть квадрата двузначного числа XY с основанием 10 , где X — это цифра десятков, а Y — цифра единиц. В частности: S будет состоять из 3 или 4 десятичных цифр.$${\displaystyle S=\left(10X+Y\right)^{2}=100X^{2}+20XY+Y^{2}.}$$

Теперь, чтобы начать алгоритм «цифра за цифрой», мы разделим цифры S на две группы по две цифры, начиная справа. Это означает, что первая группа будет состоять из 1 или 2 цифр. Затем мы определяем значение X как наибольшую цифру, такую, что X ² меньше или равно первой группе. Затем мы вычисляем разницу между первой группой и X ² и начинаем вторую итерацию, присоединяя к ней вторую группу. Это эквивалентно вычитанию из S , и у нас остается . Мы делим S' на 10, затем делим его на 2X и сохраняем целую часть, чтобы попытаться угадать Y . Мы присоединяем 2X к предварительному Y и умножаем его на Y . Если наша догадка верна, это эквивалентно вычислению: и поэтому остаток, то есть разница между S' и результатом, равен нулю; если результат больше, чем S' , мы уменьшаем наше предположение на 1 и повторяем попытку, пока остаток не станет равен 0. Поскольку это простой случай, где ответом является полный квадратный корень XY , алгоритм останавливается здесь.${\displaystyle 100X^{2}}$${\displaystyle S'=20XY+Y^{2}}$$${\displaystyle (10(2X)+Y)Y=20XY+Y^{2}=S',}$$

Эту же идею можно распространить на любое произвольное вычисление квадратного корня. Предположим, мы можем найти квадратный корень S , выразив его как сумму n положительных чисел, таких что$${\displaystyle S=\left(a_{1}+a_{2}+a_{3}+\dots +a_{n}\right)^{2}.}$$

Повторно применяя основное тождество, правый член можно расширить следующим образом:$${\displaystyle (x+y)^{2}=x^{2}+2xy+y^{2},}$$$${\displaystyle {\begin{aligned}&(a_{1}+a_{2}+a_{3}+\dotsb +a_{n})^{2}\\=&\,a_{1}^{2}+2a_{1}a_{2}+a_{2}^{2}+2(a_{1}+a_{2})a_{3}+a_{3}^{2}+\dots +a_{n-1}^{2}+2\left(\sum _{i=1}^{n-1}a_{i}\right)a_{n}+a_{n}^{2}\\=&\,a_{1}^{2}+[2a_{1}+a_{2}]a_{2}+[2(a_{1}+a_{2})+a_{3}]a_{3}+\dots +\left[2\left(\sum _{i=1}^{n-1}a_{i}\right)+a_{n}\right]a_{n}.\end{aligned}}}$$

Это выражение позволяет нам найти квадратный корень, последовательно угадывая значения s. Предположим, что числа уже угаданы, тогда m -й член правой части вышеприведенного суммирования задается как где — приближенный квадратный корень, найденный на данный момент. Теперь каждая новая догадка должна удовлетворять рекурсии , где — сумма всех членов после , т. е. остаток, такой, что для всех с инициализацией Когда точный квадратный корень был найден; если нет, то сумма s дает подходящее приближение квадратного корня, причем — ошибка приближения.${\displaystyle a_{i}}$${\displaystyle a_{1},\ldots ,a_{m-1}}$${\displaystyle Y_{m}=\left[2P_{m-1}+a_{m}\right]a_{m},}$${\textstyle P_{m-1}=\sum _{i=1}^{m-1}a_{i}}$${\displaystyle a_{m}}$$${\displaystyle X_{m}=X_{m-1}-Y_{m},}$$${\displaystyle X_{m}}$${\displaystyle Y_{m}}$${\displaystyle X_{m}\geq 0}$${\displaystyle 1\leq m\leq n,}$${\displaystyle X_{0}=S.}$${\displaystyle X_{n}=0,}$${\displaystyle a_{i}}$${\displaystyle X_{n}}$

Например, в десятичной системе счисления имеем , где — заполнители и коэффициенты . На любом m-м этапе вычисления квадратного корня приближенный корень, найденный на данный момент, и член суммирования определяются как $${\displaystyle S=\left(a_{1}\cdot 10^{n-1}+a_{2}\cdot 10^{n-2}+\cdots +a_{n-1}\cdot 10+a_{n}\right)^{2},}$$${\displaystyle 10^{n-i}}$${\displaystyle a_{i}\in \{0,1,2,\ldots ,9\}}$${\displaystyle P_{m-1}}$${\displaystyle Y_{m}}$$${\displaystyle P_{m-1}=\sum _{i=1}^{m-1}a_{i}\cdot 10^{n-i}=10^{n-m+1}\sum _{i=1}^{m-1}a_{i}\cdot 10^{m-i-1},}$$$${\displaystyle Y_{m}=\left[2P_{m-1}+a_{m}\cdot 10^{n-m}\right]a_{m}\cdot 10^{n-m}=\left[20\sum _{i=1}^{m-1}a_{i}\cdot 10^{m-i-1}+a_{m}\right]a_{m}\cdot 10^{2(n-m)}.}$$

Здесь, поскольку разрядное значение является четной степенью 10, нам нужно работать только с парой старших цифр остатка , первый член которого равен , на любом m-м этапе. Раздел ниже кодифицирует эту процедуру.${\displaystyle Y_{m}}$${\displaystyle X_{m-1}}$${\displaystyle Y_{m}}$

Очевидно, что аналогичный метод можно использовать для вычисления квадратного корня в системах счисления, отличных от десятичной. Например, нахождение поразрядного квадратного корня в двоичной системе счисления довольно эффективно, поскольку значение ищется из меньшего набора двоичных цифр {0,1}. Это ускоряет вычисления, поскольку на каждом этапе значение равно либо для , либо для . Тот факт, что у нас есть только два возможных варианта для , также упрощает процесс определения значения на m -м этапе вычислений. Это потому, что нам нужно только проверить, для Если это условие выполняется, то мы берем ; если нет, то Кроме того, тот факт, что умножение на 2 выполняется левыми битовыми сдвигами, помогает в вычислениях.${\displaystyle a_{i}}$${\displaystyle Y_{m}}$${\displaystyle Y_{m}=0}$${\displaystyle a_{m}=0}$${\displaystyle Y_{m}=2P_{m-1}+1}$${\displaystyle a_{m}=1}$${\displaystyle a_{m}}$${\displaystyle a_{m}}$${\displaystyle Y_{m}\leq X_{m-1}}$${\displaystyle a_{m}=1.}$${\displaystyle a_{m}=1}$${\displaystyle a_{m}=0.}$

Запишите исходное число в десятичной форме. Числа записываются аналогично алгоритму деления в столбик , и, как и в делении в столбик, корень будет записан на строке выше. Теперь разделите цифры на пары, начиная с десятичной точки и идя как влево, так и вправо. Десятичная точка корня будет над десятичной точкой квадрата. Одна цифра корня будет появляться над каждой парой цифр квадрата.

Начиная с крайней левой пары цифр, выполните следующую процедуру для каждой пары:

1. Начиная слева, снесите вниз самую значимую (самую левую) пару цифр, которая еще не использована (если все цифры использованы, напишите «00») и запишите их справа от остатка от предыдущего шага (на первом шаге остатка не будет). Другими словами, умножьте остаток на 100 и сложите две цифры. Это будет текущее значение c .
2. Найдите p , y и x следующим образом:
   • Пусть p — часть корня, найденная на данный момент , игнорируя любые десятичные точки. (Для первого шага p = 0.)
   • Определите наибольшую цифру x такую, что . Мы будем использовать новую переменную y = x (20 p + x ).${\displaystyle x(20p+x)\leq c}$
     • Примечание: 20 p + x — это просто удвоенное p , с добавленной справа цифрой x .
     • Примечание: x можно найти, предположив, чему равно c /(20· p ), и выполнив пробный расчет y , а затем скорректировав x в сторону увеличения или уменьшения по мере необходимости.
   • Поместите цифру как следующую цифру корня, т. е. над двумя цифрами квадрата, который вы только что свели. Таким образом, следующее p будет старым p умножить на 10 плюс x .${\displaystyle x}$
3. Вычтите y из c, чтобы получить новый остаток.
4. Если остаток равен нулю и больше нет цифр для снесения, то алгоритм завершается. В противном случае возвращаемся к шагу 1 для еще одной итерации.

Найдите квадратный корень из 152,2756.

  1 2. 3 4 / \/ 01 52.27 56 01 1*1 <= 1 < 2*2 х=1 01 у = х*х = 1*1 = 1 00 52 22*2 <= 52 < 23*3 х=2 00 44 у = (20+х)*х = 22*2 = 44 08 27 243*3 <= 827 < 244*4 х=3 07 29 у = (240+х)*х = 243*3 = 729 98 56 2464*4 <= 9856 < 2465*5 х=4 98 56 у = (2460+х)*х = 2464*4 = 9856 00 00 Алгоритм завершается: Ответ=12.34

В этом разделе используется формализм из раздела расчета по цифрам выше, с небольшим изменением, которое мы допускаем , с каждым или . Мы перебираем все , от вниз до , и строим приближенное решение , сумму всех , для которых мы определили значение. Чтобы определить, равно ли или , мы допускаем . Если (т. е. квадрат нашего приближенного решения, включая не превышает целевой квадрат), то , в противном случае и . Чтобы избежать возведения в квадрат на каждом шаге, мы сохраняем разницу и постепенно обновляем ее, устанавливая с помощью . Первоначально мы устанавливаем для наибольшего с помощью .${\displaystyle N^{2}=(a_{n}+\dotsb +a_{0})^{2}}$${\displaystyle a_{m}=2^{m}}$${\displaystyle a_{m}=0}$
${\displaystyle 2^{m}}$${\displaystyle 2^{n}}$${\displaystyle 2^{0}}$${\displaystyle P_{m}=a_{n}+a_{n-1}+\ldots +a_{m}}$${\displaystyle a_{i}}$
${\displaystyle a_{m}}$${\displaystyle 2^{m}}$${\displaystyle 0}$${\displaystyle P_{m}=P_{m+1}+2^{m}}$${\displaystyle P_{m}^{2}\leq N^{2}}$${\displaystyle 2^{m}}$${\displaystyle a_{m}=2^{m}}$${\displaystyle a_{m}=0}$${\displaystyle P_{m}=P_{m+1}}$
${\displaystyle P_{m}}$${\displaystyle X_{m}=N^{2}-P_{m}^{2}}$${\displaystyle X_{m}=X_{m+1}-Y_{m}}$${\displaystyle Y_{m}=P_{m}^{2}-P_{m+1}^{2}=2P_{m+1}a_{m}+a_{m}^{2}}$
${\displaystyle a_{n}=P_{n}=2^{n}}$${\displaystyle n}$${\displaystyle (2^{n})^{2}=4^{n}\leq N^{2}}$

В качестве дополнительной оптимизации мы сохраняем и , два члена в случае, если , не равно нулю, в отдельных переменных , :${\displaystyle P_{m+1}2^{m+1}}$${\displaystyle (2^{m})^{2}}$${\displaystyle Y_{m}}$${\displaystyle a_{m}}$${\displaystyle c_{m}}$${\displaystyle d_{m}}$$${\displaystyle c_{m}=P_{m+1}2^{m+1}}$$$${\displaystyle d_{m}=(2^{m})^{2}}$$$${\displaystyle Y_{m}={\begin{cases}c_{m}+d_{m}&{\text{if }}a_{m}=2^{m}\\0&{\text{if }}a_{m}=0\end{cases}}}$$

${\displaystyle c_{m}}$и может эффективно обновляться на каждом этапе:${\displaystyle d_{m}}$$${\displaystyle c_{m-1}=P_{m}2^{m}=(P_{m+1}+a_{m})2^{m}=P_{m+1}2^{m}+a_{m}2^{m}={\begin{cases}c_{m}/2+d_{m}&{\text{if }}a_{m}=2^{m}\\c_{m}/2&{\text{if }}a_{m}=0\end{cases}}}$$$${\displaystyle d_{m-1}={\frac {d_{m}}{4}}}$$

Обратите внимание: это конечный результат, возвращаемый функцией ниже.$${\displaystyle c_{-1}=P_{0}2^{0}=P_{0}=N,}$$

Реализация этого алгоритма на языке C: ^[6]

int32_t isqrt ( int32_t n ) {    assert (( "входной квадратный корень должен быть неотрицательным" , n > 0 ));    // Х_(n+1) int32_t x = n ;    // c_n int32_t c = 0 ;    // d_n, который начинается с наивысшей степени четырех <= n int32_t d = 1 << 30 ; // Устанавливается второй сверху бит.       // То же, что и ((без знака) INT32_MAX + 1) / 2. в то время как ( д > н ) {     д >>= 2 ;   } // для dₙ … d₀ пока ( д != 0 ) {     если ( x >= c + d ) { // если X_(m+1) ≥ Y_m тогда a_m = 2^m        x -= c + d ; // X_m = X_(m+1) - Y_m      c = ( c >> 1 ) + d ; // c_(m-1) = c_m/2 + d_m (a_m равно 2^m)        } еще {  c >>= 1 ; // c_(m-1) = c_m/2 (aₘ равно 0)    } d >>= 2 ; // d_(m-1) = d_m/4    } вернуть с ; // с_(-1)  }

Более быстрые алгоритмы, в двоичной и десятичной системе счисления или в любой другой системе счисления, могут быть реализованы с помощью таблиц поиска — по сути, за счет увеличения дискового пространства за счет сокращения времени выполнения . ^[7]

Карманные калькуляторы обычно реализуют хорошие процедуры для вычисления показательной функции и натурального логарифма , а затем вычисляют квадратный корень из S, используя тождество, найденное с использованием свойств логарифмов ( ) и экспонент ( ): ^{[ необходима цитата ]} Знаменатель в дроби соответствует корню n- й степени. В приведенном выше случае знаменатель равен 2, поэтому уравнение указывает, что квадратный корень должен быть найден. То же самое тождество используется при вычислении квадратных корней с помощью таблиц логарифмов или логарифмических линеек .${\displaystyle \ln x^{n}=n\ln x}$${\displaystyle e^{\ln x}=x}$$${\displaystyle {\sqrt {S}}=e^{{\frac {1}{2}}\ln S}.}$$

Этот метод применим для нахождения квадратного корня из и лучше всего сходится при . Однако это не является реальным ограничением для вычислений на основе компьютера, так как в представлениях с плавающей и фиксированной точкой по основанию 2 умножение на целую степень 4 и, следовательно, на соответствующую степень 2, путем изменения показателя степени или сдвига соответственно, является тривиальным. Поэтому, может быть перемещено в диапазон . Более того, следующий метод не использует общие деления, а только сложения, вычитания, умножения и деления на степени двойки, которые снова тривиальны для реализации. Недостатком метода является то, что числовые ошибки накапливаются, в отличие от итерационных методов с одной переменной, таких как вавилонский.${\displaystyle 0<S<3\,\!}$${\displaystyle S\approx 1}$${\displaystyle S\,\!}$${\displaystyle {\sqrt {S}}}$${\displaystyle S\,\!}$${\textstyle {\tfrac {1}{2}}\leq S<2}$

Шаг инициализации этого метода выполняется в то время, пока итерационные шаги читаются как Then, (while ).$${\displaystyle {\begin{aligned}a_{0}&=S\\c_{0}&=S-1\end{aligned}}}$$$${\displaystyle {\begin{aligned}a_{n+1}&=a_{n}-a_{n}c_{n}/2\\c_{n+1}&=c_{n}^{2}(c_{n}-3)/4\end{aligned}}}$$${\displaystyle a_{n}\to {\sqrt {S}}}$${\displaystyle c_{n}\to 0}$

Сходимость , а следовательно, и , является квадратичной.${\displaystyle c_{n}\,\!}$${\displaystyle a_{n}\,\!}$

Доказательство метода довольно простое. Сначала перепишем итеративное определение в виде Тогда по индукции несложно доказать, что и, следовательно, сходимость к требуемому результату обеспечивается сходимостью к 0, что в свою очередь следует из .${\displaystyle c_{n}}$$${\displaystyle 1+c_{n+1}=(1+c_{n})(1-{\tfrac {1}{2}}c_{n})^{2}.}$$$${\displaystyle S(1+c_{n})=a_{n}^{2}}$$${\displaystyle a_{n}\,\!}$${\displaystyle {\sqrt {S}}}$${\displaystyle c_{n}\,\!}$${\displaystyle -1<c_{0}<2\,\!}$

Этот метод был разработан около 1950 года М. В. Уилксом , Д. Д. Уилером и С. Гиллом ^[8] для использования на EDSAC , одном из первых электронных компьютеров. ^[9] Метод был позже обобщен, что позволило вычислять неквадратные корни. ^[10]

Ниже приведены итерационные методы нахождения обратного квадратного корня S , который равен . После того, как он найден, найдите простым умножением: . Эти итерации включают только умножение, а не деление. Поэтому они быстрее, чем вавилонский метод. Однако они нестабильны. Если начальное значение не близко к обратному квадратному корню, итерации будут расходиться от него, а не сходиться к нему. Поэтому может быть выгодно выполнить итерацию вавилонского метода на грубой оценке, прежде чем начинать применять эти методы.${\displaystyle 1/{\sqrt {S}}}$${\displaystyle {\sqrt {S}}}$${\displaystyle {\sqrt {S}}=S\cdot (1/{\sqrt {S}})}$

• Применение метода Ньютона к уравнению дает метод, который сходится квадратично, используя три умножения на шаг:${\displaystyle (1/x^{2})-S=0}$$${\displaystyle x_{n+1}={\frac {x_{n}}{2}}\cdot (3-S\cdot x_{n}^{2})=x_{n}\cdot \left({\frac {3}{2}}-{\frac {S}{2}}\cdot x_{n}^{2}\right).}$$
• Другая итерация получается методом Галлея , который является методом Хаусхолдера второго порядка. Он сходится кубически , но включает пять умножений на итерацию: ^{[ требуется ссылка ]} и$${\displaystyle y_{n}=S\cdot x_{n}^{2},}$$$${\displaystyle x_{n+1}={\frac {x_{n}}{8}}\cdot (15-y_{n}\cdot (10-3\cdot y_{n}))=x_{n}\cdot \left({\frac {15}{8}}-y_{n}\cdot \left({\frac {10}{8}}-{\frac {3}{8}}\cdot y_{n}\right)\right).}$$
• Если используется арифметика с фиксированной точкой , умножение на 3 и деление на 8 можно реализовать с помощью сдвигов и сложений. Если используется плавающая точка, метод Галлея можно сократить до четырех умножений на итерацию путем предварительного вычисления и корректировки всех других констант для компенсации: и${\textstyle {\sqrt {3/8}}S}$$${\displaystyle y_{n}={\sqrt {\frac {3}{8}}}S\cdot x_{n}^{2},}$$$${\displaystyle x_{n+1}=x_{n}\cdot \left({\frac {15}{8}}-y_{n}\cdot \left({\sqrt {\frac {25}{6}}}-y_{n}\right)\right).}$$

Алгоритм Голдшмидта — это расширение деления Голдшмидта , названного в честь Роберта Эллиота Голдшмидта, ^{[11] [12],} которое можно использовать для вычисления квадратных корней. Некоторые компьютеры используют алгоритм Голдшмидта для одновременного вычисления и . Алгоритм Голдшмидта находит быстрее, чем итерация Ньютона-Рафсона на компьютере с объединенной инструкцией умножения-сложения и либо конвейерным блоком с плавающей точкой, либо двумя независимыми блоками с плавающей точкой. ^[13]${\displaystyle {\sqrt {S}}}$${\displaystyle 1/{\sqrt {S}}}$${\displaystyle {\sqrt {S}}}$

Первый способ записи алгоритма Гольдшмидта начинается

${\displaystyle b_{0}=S}$

${\displaystyle Y_{0}\approx 1/{\sqrt {S}}}$(обычно с использованием табличного поиска)

${\displaystyle y_{0}=Y_{0}}$

${\displaystyle x_{0}=Sy_{0}}$

и повторяется до тех пор, пока не станет достаточно близко к 1 или фиксированному числу итераций. Итерации сходятся к и Обратите внимание, что можно исключить любой из и из вычисления, и если оба желательны, то можно использовать в конце, а не вычислять его в каждой итерации.$${\displaystyle {\begin{aligned}b_{n+1}&=b_{n}Y_{n}^{2}\\Y_{n+1}&={\tfrac {1}{2}}(3-b_{n+1})\\x_{n+1}&=x_{n}Y_{n+1}\\y_{n+1}&=y_{n}Y_{n+1}\end{aligned}}}$$${\displaystyle b_{i}}$$${\displaystyle \lim _{n\to \infty }x_{n}={\sqrt {S}},}$$$${\displaystyle \lim _{n\to \infty }y_{n}=1/{\sqrt {S}}.}$$${\displaystyle x_{n}}$${\displaystyle y_{n}}$${\displaystyle x_{n}=Sy_{n}}$

Вторая форма, использующая объединенные операции умножения-сложения , начинается

${\displaystyle y_{0}\approx 1/{\sqrt {S}}}$(обычно с использованием табличного поиска)

${\displaystyle x_{0}=Sy_{0}}$

${\displaystyle h_{0}={\tfrac {1}{2}}y_{0}}$

и повторяется до тех пор, пока не станет достаточно близко к 0 или фиксированному числу итераций. Это сходится к и$${\displaystyle {\begin{aligned}r_{n}&=0.5-x_{n}h_{n}\\x_{n+1}&=x_{n}+x_{n}r_{n}\\h_{n+1}&=h_{n}+h_{n}r_{n}\end{aligned}}}$$${\displaystyle r_{i}}$$${\displaystyle \lim _{n\to \infty }x_{n}={\sqrt {S}},}$$$${\displaystyle \lim _{n\to \infty }2h_{n}=1/{\sqrt {S}}.}$$

Если N является приближением к , лучшее приближение можно найти, используя ряд Тейлора функции квадратного корня :${\displaystyle {\sqrt {S}}}$$${\displaystyle {\sqrt {N^{2}+d}}=N\sum _{n=0}^{\infty }{\frac {(-1)^{n}(2n)!}{(1-2n)n!^{2}4^{n}}}{\frac {d^{n}}{N^{2n}}}=N\left(1+{\frac {d}{2N^{2}}}-{\frac {d^{2}}{8N^{4}}}+{\frac {d^{3}}{16N^{6}}}-{\frac {5d^{4}}{128N^{8}}}+\cdots \right)}$$

Как итеративный метод, порядок сходимости равен количеству используемых членов. С двумя членами он идентичен вавилонскому методу. С тремя членами каждая итерация занимает почти столько же операций, сколько и приближение Бахшали, но сходится медленнее. ^{[ необходима цитата ]} Поэтому это не особенно эффективный способ вычисления. Чтобы максимизировать скорость сходимости, выберите N так, чтобы оно было как можно меньше.${\displaystyle {\frac {|d|}{N^{2}}}\,}$

Представление действительного числа в виде непрерывной дроби можно использовать вместо его десятичной или двоичной записи, и это представление обладает тем свойством, что квадратный корень любого рационального числа (которое уже не является полным квадратом) имеет периодическое, повторяющееся разложение, подобно тому, как рациональные числа имеют повторяющиеся разложения в десятичной системе счисления.

Квадратичные иррациональные числа (числа вида , где a , b и c — целые числа), и в частности, квадратные корни из целых чисел, имеют периодические цепные дроби . Иногда требуется найти не численное значение квадратного корня, а его разложение в цепную дробь и, следовательно, его рациональное приближение. Пусть S — положительное число, для которого нам требуется найти квадратный корень. Тогда, предполагая, что a — число, которое служит начальным предположением, а r — остаточным членом, мы можем записать Поскольку у нас есть , мы можем выразить квадратный корень из S как${\displaystyle {\frac {a+{\sqrt {b}}}{c}}}$${\displaystyle S=a^{2}+r.}$${\displaystyle S-a^{2}=({\sqrt {S}}+a)({\sqrt {S}}-a)=r}$$${\displaystyle {\sqrt {S}}=a+{\frac {r}{a+{\sqrt {S}}}}.}$$