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

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

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

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

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

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

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

История

Процедуры нахождения квадратных корней (в частности, квадратного корня из 2 ) известны по крайней мере с периода древнего Вавилона в 17 веке до н. э. Вавилонские математики вычисляли квадратный корень из 2 до трех шестидесятеричных «цифр» после 1, но точно не известно, как. Они знали, как аппроксимировать гипотенузу, используя (например, для диагонали ворот, высота которых составляет прутьев, а ширина — прутьев), и они, возможно, использовали аналогичный подход для нахождения аппроксимации ^[2] $${\displaystyle {\sqrt {a^{2}+b^{2}}}\approx a+{\frac {1}{2}}b^{2}a^{-1}}$$ ${\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 = -190/(y+20)+10. Таким образом, для : ${\displaystyle [1,100]}$ ${\displaystyle S=a\cdot 10^{2n}}$ $${\displaystyle {\sqrt {S}}\approx \left({\frac {-190}{a+20}}+10\right)\cdot 10^{n}}$$

Деление с плавающей точкой должно быть точным только до одной десятичной цифры, потому что общая оценка точна только настолько и может быть сделана в уме. Гиперболическая оценка в среднем лучше, чем скалярные или линейные оценки. Она имеет максимальную абсолютную погрешность 1,58 при 100 и максимальную относительную погрешность 16,0% при 10. Для худшего случая при a=10 оценка составляет 3,67. Если начать с 10 и сразу применить итерации Ньютона-Рафсона, потребуются две итерации, что даст 3,66, прежде чем точность гиперболической оценки будет превышена. Для более типичного случая, такого как 75, гиперболическая оценка составляет 8,00, и для получения более точного результата потребуется 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]} Процедура требует лишь немного арифметики, чтобы найти граничное число посередине двух произведений из таблицы умножения. Вот справочная таблица этих границ:

Последняя операция — умножить оценку 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-точечным чем-то , потому что 8 × 8 равно 64, но 9 × 9 равно 81, слишком много, поэтому k равно 8; что-то — это десятичное представление R . Дробь R равна 75 - k ² = 11, числителю, и 81 - k ² = 17, знаменателю. 11/17 немного меньше 12/18, что равно 2/3s или .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{aligned}{\begin{array}{rlll}x_{0}&=6\cdot 10^{2}&&=600.000\\[0.3em]x_{1}&={\frac {\ 1\ }{2}}\left(x_{0}+{\frac {S}{\;x_{0}\ }}\right)&={\frac {\ 1\ }{2}}\left(600.000+{\frac {\ 125348\ }{600.000}}\right)&=404.457\\[0.3em]x_{2}&={\frac {\ 1\ }{2}}\left(x_{1}+{\frac {S}{\;x_{1}\ }}\right)&={\frac {\ 1\ }{2}}\left(404.457+{\frac {\ 125348\ }{404.457}}\right)&=357.187\\[0.3em]x_{3}&={\frac {\ 1\ }{2}}\left(x_{2}+{\frac {S}{\;x_{2}\ }}\right)&={\frac {\ 1\ }{2}}\left(357.187+{\frac {\ 125348\ }{357.187}}\right)&=354.059\\[0.3em]x_{4}&={\frac {\ 1\ }{2}}\left(x_{3}+{\frac {S}{\;x_{3}\ }}\right)&={\frac {\ 1\ }{2}}\left(354.059+{\frac {\ 125348\ }{354.059}}\right)&=354.045\\[0.3em]x_{5}&={\frac {\ 1\ }{2}}\left(x_{4}+{\frac {S}{\;x_{4}\ }}\right)&={\frac {\ 1\ }{2}}\left(354.045+{\frac {\ 125348\ }{354.045}}\right)&=354.045\ \end{array}}\end{aligned}}}$$

Следовательно, с точностью до трех знаков после запятой. ${\displaystyle \ {\sqrt {125348~}}\approx 354.045\ }$

Конвергенция

Полулогарифмические графики, сравнивающие скорость сходимости метода Герона для нахождения квадратного корня из 100 для различных начальных догадок. Отрицательные догадки сходятся к отрицательному корню, положительные догадки — к положительному корню. Обратите внимание, что значения, близкие к корню, сходятся быстрее, а все приближения являются завышенными. В файле SVG наведите курсор на график, чтобы отобразить его точки.

Предположим, что Тогда для любого натурального числа Пусть относительная погрешность определяется как и, таким образом, ${\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}\ }$

Метод Бахшали

Этот метод нахождения приближения к квадратному корню был описан в древнеиндийской рукописи , называемой рукописью Бахшали . Он эквивалентен двум итерациям вавилонского метода, начинающегося с x ₀ . Таким образом, алгоритм является четвертично сходящимся, что означает, что количество правильных цифр приближения примерно учетверяется с каждой итерацией. ^[4] Оригинальное представление с использованием современных обозначений выглядит следующим образом: Чтобы вычислить , пусть будет начальным приближением к . Затем последовательно выполните итерации как: ${\displaystyle {\sqrt {S}}}$ ${\displaystyle x_{0}^{2}}$ ${\displaystyle S}$ $${\displaystyle {\begin{aligned}a_{n}&={\frac {S-x_{n}^{2}}{2x_{n}}},\\b_{n}&=x_{n}+a_{n},\\x_{n+1}&=b_{n}-{\frac {a_{n}^{2}}{2b_{n}}}=(x_{n}+a_{n})-{\frac {a_{n}^{2}}{2(x_{n}+a_{n})}}.\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 S=125348.}$ $${\displaystyle {\begin{aligned}x_{0}&=600\\[1ex]a_{1}&={\frac {125348-600^{2}}{2\times 600}}&&=&-195.543\\[1ex]b_{1}&=600+(-195.543)&&=&404.456\\[1ex]x_{1}&=404.456-{\frac {(-195.543)^{2}}{2\times 404.456}}&&=&357.186\end{aligned}}}$$

Аналогично вторая итерация дает $${\displaystyle {\begin{aligned}a_{2}&={\frac {125348-357.186^{2}}{2\times 357.186}}&&=&-3.126\\[1ex]b_{2}&=357.186+(-3.126)&&=&354.060\\[1ex]x_{2}&=354.06-{\frac {(-3.1269)^{2}}{2\times 354.06}}&&=&354.046\end{aligned}}}$$

Поразрядный расчет

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

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

Недостатки:

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

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

Основной принцип

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

Теперь, используя алгоритм «цифра за цифрой», мы сначала определяем значение X. X — это наибольшая цифра, такая что X ² меньше или равно Z , из которого мы удалили две крайние правые цифры .

В следующей итерации мы спариваем цифры, умножаем X на 2 и помещаем его в разряд десятков, пока пытаемся выяснить значение Y.

Поскольку это простой случай, где ответом является полный квадратный корень XY , алгоритм останавливается здесь.

Эту же идею можно распространить на любое произвольное вычисление квадратного корня. Предположим, мы можем найти квадратный корень N , выразив его как сумму n положительных чисел, таких что $${\displaystyle N=\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}\geq 0}$ ${\displaystyle 1\leq m\leq n,}$ ${\displaystyle X_{0}=N.}$ ${\displaystyle X_{n}=0,}$ ${\displaystyle a_{i}}$ ${\displaystyle X_{n}}$

Например, в десятичной системе счисления имеем , где — заполнители и коэффициенты . На любом m-м этапе вычисления квадратного корня приближенный корень, найденный на данный момент, и член суммирования определяются как $${\displaystyle N=\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}}$

Очевидно, что аналогичный метод можно использовать для вычисления квадратного корня в системах счисления, отличных от десятичной. Например, нахождение поразрядного квадратного корня в двоичной системе счисления довольно эффективно, поскольку значение ищется из меньшего набора двоичных цифр {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.}$

Десятичная (основание 10)

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

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

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

Двоичная система счисления (основание 2)

В этом разделе используется формализм из раздела расчета по цифрам выше, с небольшим изменением, которое мы допускаем , с каждым или . Мы перебираем все , от вниз до , и строим приближенное решение , сумму всех , для которых мы определили значение. Чтобы определить, равно ли или , мы допускаем . Если (т. е. квадрат нашего приближенного решения, включая не превышает целевой квадрат), то , в противном случае и . Чтобы избежать возведения в квадрат на каждом шаге, мы сохраняем разницу и постепенно обновляем ее, устанавливая с помощью . Первоначально мы устанавливаем для наибольшего с помощью . ${\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}}}}.}$$

Применяя это выражение к знаменателю дроби, имеем ${\displaystyle {\sqrt {S}}}$ $${\displaystyle {\sqrt {S}}=a+{\frac {r}{a+(a+{\frac {r}{a+{\sqrt {S}}}})}}=a+{\frac {r}{2a+{\frac {r}{a+{\sqrt {S}}}}}}.}$$

Компактная запись

Разложение числителя/знаменателя для непрерывных дробей (см. слева) является громоздким для записи, а также для встраивания в системы форматирования текста. Поэтому математики разработали несколько альтернативных обозначений, таких как ^[14] $${\displaystyle {\sqrt {S}}=a+{\frac {r}{2a+}}\,{\frac {r}{2a+}}\,{\frac {r}{2a+}}\cdots }$$

Везде , где используется еще более компактная запись: ^[15] Для повторяющихся непрерывных дробей (которые имеют все квадратные корни из неполных квадратов), повторяющаяся часть представляется только один раз, с верхней чертой, чтобы обозначить бесконечное повторение отмеченной части: ^[16] ${\displaystyle r=1}$ $${\displaystyle [a;2a,2a,2a,\cdots ]}$$ $${\displaystyle [a;{\overline {2a}}]}$$

Для √ 2 значение равно 1, поэтому его представление следующее: ${\displaystyle a}$ $${\displaystyle [1;{\overline {2}}]}$$

Действуя таким образом, мы получаем обобщенную цепную дробь для квадратного корня в виде $${\displaystyle {\sqrt {S}}=a+{\cfrac {r}{2a+{\cfrac {r}{2a+{\cfrac {r}{2a+\ddots }}}}}}}$$

Первый шаг к оценке такой дроби ^[17] для получения корня — это сделать числовые подстановки для корня желаемого числа и количества выбранных знаменателей. Например, в канонической форме это 1, а для √ 2 это 1 , поэтому числовая непрерывная дробь для 3 знаменателей выглядит так: ${\displaystyle r}$ ${\displaystyle a}$ $${\displaystyle {\sqrt {2}}\approx 1+{\cfrac {1}{2+{\cfrac {1}{2+{\cfrac {1}{2}}}}}}}$$

Шаг 2 — сократить непрерывную дробь снизу вверх, по одному знаменателю за раз, чтобы получить рациональную дробь, числитель и знаменатель которой являются целыми числами. Сокращение происходит следующим образом (беря первые три знаменателя): $${\displaystyle {\begin{aligned}1+{\cfrac {1}{2+{\cfrac {1}{2+{\cfrac {1}{2}}}}}}&=1+{\cfrac {1}{2+{\cfrac {1}{\frac {5}{2}}}}}\\&=1+{\cfrac {1}{2+{\cfrac {2}{5}}}}=1+{\cfrac {1}{\frac {12}{5}}}\\&=1+{\cfrac {5}{12}}={\frac {17}{12}}\end{aligned}}}$$

Наконец (шаг 3) разделите числитель на знаменатель рациональной дроби, чтобы получить приблизительное значение корня: округленное до трех знаков точности. $${\displaystyle 17\div 12=1.42}$$

Фактическое значение √ 2 равно 1,41 с точностью до трех значащих цифр. Относительная погрешность составляет 0,17%, поэтому рациональная дробь хороша с точностью почти до трех цифр. Взятие большего количества знаменателей дает последовательно лучшие приближения: четыре знаменателя дают дробь , хорошую с точностью почти до четырех цифр и т. д. ${\displaystyle {\frac {41}{29}}=1.4137}$

Ниже приведены примеры квадратных корней, их простых цепных дробей и их первых членов — называемых конвергентами — до знаменателя 99 включительно:

В общем случае, чем больше знаменатель рациональной дроби, тем лучше приближение. Можно также показать, что усечение непрерывной дроби дает рациональную дробь, которая является наилучшим приближением к корню любой дроби со знаменателем, меньшим или равным знаменателю этой дроби — например, никакая дробь со знаменателем, меньшим или равным 70, не является таким же хорошим приближением к √ 2, как 99/70.

Приближения, зависящие от представления с плавающей точкой

Число представлено в формате с плавающей точкой , который также называется научной записью . Его квадратный корень равен и аналогичные формулы применимы для кубических корней и логарифмов. На первый взгляд, это не является улучшением простоты, но предположим, что требуется только приближение: тогда просто хорошо для порядка величины. Далее, признаем, что некоторые степени, p , будут нечетными, таким образом, для 3141,59 = 3,14159 × 10 ${\displaystyle m\times b^{p}}$ ${\displaystyle {\sqrt {m}}\times b^{p/2}}$ ${\displaystyle b^{p/2}}$³ вместо того, чтобы иметь дело с дробными степенями основания, умножьте мантиссу на основание и вычтите единицу из степени, чтобы сделать ее ровной. Скорректированное представление станет эквивалентом 31,4159 × 10² , так что квадратный корень будет √ 31,4159 × 10¹ .

Если берется целая часть скорректированной мантиссы, то могут быть только значения от 1 до 99, и это может быть использовано в качестве индекса в таблице из 99 предварительно вычисленных квадратных корней для завершения оценки. Компьютеру, использующему основание шестнадцать, потребуется таблица большего размера, но компьютеру, использующему основание два, потребуется всего три записи: возможные биты целой части скорректированной мантиссы равны 01 (степень четная, поэтому сдвига не было, помня, что нормализованное число с плавающей точкой всегда имеет ненулевую старшую цифру) или, если степень нечетная, 10 или 11, которые являются первыми двумя битами исходной мантиссы. Таким образом, 6,25 = 110,01 в двоичном коде, нормализованном до 1,1001 × 2 ² четной степени, так что парные биты мантиссы равны 01, в то время как .625 = 0,101 в двоичном коде нормализовано до 1,01 × 2 ⁻¹ нечетной степени, так что корректировка составляет 10,1 × 2 ⁻² , а парные биты равны 10. Обратите внимание, что младший бит степени отражается в старшем бите парной мантиссы. Четная степень имеет свой младший бит нуль, и скорректированная мантисса будет начинаться с 0, тогда как для нечетной степени этот бит равен единице, и скорректированная мантисса будет начинаться с 1. Таким образом, когда степень уменьшается вдвое, это как если бы его младший бит был сдвинут наружу, чтобы стать первым битом парной мантиссы.

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

Многие компьютеры следуют представлению IEEE (или достаточно похожему), и очень быстрое приближение к квадратному корню может быть получено для запуска метода Ньютона. Метод, который следует ниже, основан на том факте, что формат с плавающей точкой (по основанию два) приближает логарифм по основанию 2. То есть ${\displaystyle \log _{2}(m\times 2^{p})=p+\log _{2}(m)}$

Таким образом, для 32-битного числа с плавающей точкой одинарной точности в формате IEEE (где, в частности, степень имеет смещение 127 , добавленное для представленной формы) вы можете получить приблизительный логарифм, интерпретируя его двоичное представление как 32-битное целое число, масштабируя его на и удаляя смещение 127, т.е. ${\displaystyle 2^{-23}}$ $${\displaystyle x_{\text{int}}\cdot 2^{-23}-127\approx \log _{2}(x).}$$

Например, 1.0 представлен шестнадцатеричным числом 0x3F800000, которое представляло бы, если бы было взято как целое число. Используя формулу выше, вы получаете , как и ожидалось из . Аналогичным образом вы получаете 0.5 из 1.5 (0x3FC00000). ${\displaystyle 1065353216=127\cdot 2^{23}}$ ${\displaystyle 1065353216\cdot 2^{-23}-127=0}$ ${\displaystyle \log _{2}(1.0)}$

Чтобы получить квадратный корень, разделите логарифм на 2 и преобразуйте значение обратно. Следующая программа демонстрирует эту идею. Самый низкий бит экспоненты намеренно позволяется распространяться в мантиссу. Один из способов обосновать шаги в этой программе — предположить, что это смещение экспоненты, а это количество явно сохраненных битов в мантиссе, а затем показать, что ${\displaystyle b}$ ${\displaystyle n}$ $${\displaystyle \left(\left({\tfrac {1}{2}}\left(x_{\text{int}}/2^{n}-b\right)\right)+b\right)\cdot 2^{n}={\tfrac {1}{2}}\left(x_{\text{int}}-2^{n}\right)+\left({\tfrac {1}{2}}\left(b+1\right)\right)\cdot 2^{n}.}$$

/* Предполагается, что float имеет формат с плавающей точкой одинарной точности IEEE 754 */ #include <stdint.h> float sqrt_approx ( float z ) { union { float f ; uint32_t i ; } val = { z }; /* Преобразовать тип, сохраняя битовую комбинацию */ /*  * Чтобы оправдать следующий код, докажите, что  *  * ((((val.i / 2^m) - b) / 2) + b) * 2^m = ((val.i - 2^m) / 2) + ((b + 1) / 2) * 2^m)  *  * где  *  * b = смещение экспоненты  * m = количество бит мантиссы  */ val . i -= 1 << 23 ; /* Вычесть 2^m. */ val . i >>= 1 ; /* Деление на 2. */ val . i += 1 << 29 ; /* Добавить ((b + 1) / 2) * 2^m. */                      return val . f ; /* Интерпретируем снова как float */ } 

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

знач . i = ( 1 << 29 ) + ( знач . i >> 1 ) - ( 1 << 22 ) + a ;              

где a — смещение для корректировки ошибок аппроксимации. Например, при a = 0 результаты точны для четных степеней 2 (например, 1,0), но для других чисел результаты будут немного завышены (например, 1,5 для 2,0 вместо 1,414... с ошибкой 6%). При a = −0x4B0D2 максимальная относительная ошибка сводится к минимуму до ±3,5%.

Если приближение должно использоваться для первоначального предположения метода Ньютона к уравнению , то предпочтительнее использовать обратную форму, показанную в следующем разделе. ${\displaystyle (1/x^{2})-S=0}$

Обратная величина квадратного корня

Ниже приведен вариант вышеприведенной процедуры, который можно использовать для вычисления обратной величины квадратного корня, т.е. вместо этого, был написан Грегом Уолшем. Аппроксимация целочисленного сдвига дала относительную погрешность менее 4%, а погрешность снизилась еще больше до 0,15% с одной итерацией метода Ньютона на следующей строке. ^[18] В компьютерной графике это очень эффективный способ нормализации вектора. ${\displaystyle x^{-1/2}}$

float invSqrt ( float x ) { float xhalf = 0.5f * x ; union { float x ; int i ; } u ; u . x = x ; u . i = 0x5f375a86 - ( u . i >> 1 ); /* Следующая строка может быть повторена любое количество раз для повышения точности */ u . x = u . x * ( 1.5f - xhalf * u . x * u . x ); return u . x ; }                                         

Некоторые аппаратные средства VLSI реализуют обратный квадратный корень с использованием оценки полинома второй степени, за которой следует итерация Гольдшмидта . ^[19]

Отрицательный или комплексный квадрат

Если S  < 0, то его главный квадратный корень равен $${\displaystyle {\sqrt {S}}={\sqrt {\vert S\vert }}\,\,i\,.}$$

Если S  =  ​​a + bi , где a и b действительны и b  ≠ 0, то его главный квадратный корень равен $${\displaystyle {\sqrt {S}}={\sqrt {\frac {\vert S\vert +a}{2}}}\,+\,\operatorname {sgn}(b){\sqrt {\frac {\vert S\vert -a}{2}}}\,\,i\,.}$$

Это можно проверить, возведя корень в квадрат. ^{[20] [21]} Здесь $${\displaystyle \vert S\vert ={\sqrt {a^{2}+b^{2}}}}$$

— модуль числа S. Главный квадратный корень комплексного числа определяется как корень с неотрицательной действительной частью.

Смотрите также

• Алгоритм альфа макс плюс бета мин
• алгоритм корня n-го порядка

Примечания

1. Множители два и шесть используются, поскольку они приближают геометрические средние наименьшего и наибольшего возможных значений с заданным количеством цифр: и . ${\displaystyle {\sqrt {{\sqrt {1}}\cdot {\sqrt {10}}}}={\sqrt[{4}]{10}}\approx 1.78\,}$ ${\displaystyle {\sqrt {{\sqrt {10}}\cdot {\sqrt {100}}}}={\sqrt[{4}]{1000}}\approx 5.62\,}$
2. Неокругленная оценка имеет максимальную абсолютную погрешность 2,65 при 100 и максимальную относительную погрешность 26,5% при y=1, 10 и 100.
3. Если число находится точно посередине между двумя квадратами, например, 30,5, укажите большее число, в данном случае 6.
4. Это, кстати, уравнение касательной к y  =  x ² при y  = 1.

Ссылки

1. Джексон 2011.
2. Фаулер и Робсон 1998.
3. Heath 1921.
4. Бейли и Борвейн 2012.
5. Просто любопытно 2018.
6. Гай и UKC 1985.
7. Стейнарсон, Корбит и Хендри 2003.
8. Уилкс, Уиллер и Гилл 1951.
9. Кэмпбелл-Келли 2009.
10. Гауэр 1958.
11. Goldschmidt, Robert E. (1964). Applications of Division by Convergence (PDF) (Thesis). M.Sc. dissertation. MIT OCLC  34136725. Архивировано (PDF) из оригинала 2015-12-10 . Получено 2015-09-15 .
12. "Авторы". IBM Journal of Research and Development . 11 : 125–127. 1967. doi :10.1147/rd.111.0125. Архивировано из оригинала 18 июля 2018 г.
13. Маркштейн 2004.
14. см.: Обобщенная цепная дробь#Обозначение
15. см.: Продолжительная дробь#Обозначения
16. см.: Периодическая цепная дробь
17. Сардина 2007, 2.3j на стр.10.
18. Ломонт 2003.
19. Пиньейро и Диас Бругера 2002.
20. Абрамовиц и Стегун 1964, раздел 3.7.26.
21. Кук 2008.

Библиография

• Абрамовиц, Милтонн; Стиган, Ирен А. (1964). Справочник математических функций с формулами, графиками и математическими таблицами . Courier Dover Publications. стр. 17. ISBN 978-0-486-61272-0.
• Бейли, Дэвид; Борвейн, Джонатан (2012). «Древнеиндийские квадратные корни: упражнение в судебной палеоматематике» (PDF) . American Mathematical Monthly . Том 119, № 8. С. 646–657 . Получено 14 сентября 2017 г. .
• Кэмпбелл-Келли, Мартин (сентябрь 2009 г.). «Происхождение вычислений». Scientific American . 301 (3): 62–69. Bibcode : 2009SciAm.301c..62C. doi : 10.1038/scientificamerican0909-62. JSTOR  26001527. PMID  19708529.
• Кук, Роджер (2008). Классическая алгебра: ее природа, происхождение и использование . John Wiley and Sons. стр. 59. ISBN 978-0-470-25952-8.
• Фаулер, Дэвид; Робсон, Элеанор (1998). «Приближения квадратного корня в старой вавилонской математике: YBC 7289 в контексте» (PDF) . Historia Mathematica . 25 (4): 376. doi : 10.1006/hmat.1998.2209 .
• Gower, John C. (1958). «Заметка об итеративном методе извлечения корня». The Computer Journal . 1 (3): 142–143. doi : 10.1093/comjnl/1.3.142 .
• Джексон, Теренс (01.07.2011). "95.42 Иррациональные квадратные корни натуральных чисел — геометрический подход". The Mathematical Gazette . 95 (533): 327–330. doi :10.1017/S0025557200003193. ISSN  0025-5572. S2CID  123995083.
• Гай, Мартин; UKC (1985). "Быстрое вычисление квадратного корня целого числа с помощью алгоритма абакуса мистера Ву (архив)". Архивировано из оригинала 2012-03-06.
• Хит, Томас (1921). История греческой математики, т. 2. Оксфорд: Clarendon Press. стр. 323–324.
• Ломонт, Крис (2003). «Быстрый обратный квадратный корень» (PDF) .
• Маркштейн, Питер (ноябрь 2004 г.). Разделение программного обеспечения и квадратный корень с использованием алгоритмов Гольдшмидта (PDF) . 6-я конференция по действительным числам и компьютерам. Дагштуль , Германия. CiteSeerX  10.1.1.85.9648 .
• Piñeiro, José-Alejandro; Díaz Bruguera, Javier (декабрь 2002 г.). «Высокоскоростные вычисления двойной точности для обратных чисел, деления, квадратного корня и обратного квадратного корня». IEEE Transactions on Computers . 51 (12): 1377–1388. doi :10.1109/TC.2002.1146704.
• Сардина, Мэнни (2007). «Общий метод извлечения корней с использованием (сложенных) непрерывных дробей». Суррей (Великобритания).
• Simply Curious (5 июня 2018 г.). «Взявшись за рукопись Бахшали». Блог Simply Curious . Получено 21.12.2020 .
• Стейнарсон, Арне; Корбит, Данн; Хендри, Мэтью (2003). «Функция целочисленного квадратного корня».
• Уилкс, М. В.; Уилер , Д. Дж .; Гилл, С. (1951). Подготовка программ для электронного цифрового компьютера. Оксфорд: Addison-Wesley. С. 323–324. OCLC  475783493.

Внешние ссылки

• Вайсштейн, Эрик В. «Алгоритмы вычисления квадратного корня». MathWorld .
• Квадратные корни вычитанием
• Алгоритм целочисленного квадратного корня Андрия Радовича
• Алгоритмы персонального калькулятора I: Квадратные корни (Уильям Э. Эгберт), Hewlett-Packard Journal (май 1977 г.): стр. 22
• Калькулятор для изучения квадратного корня