Методы вычисления квадратных корней представляют собой алгоритмы численного анализа для нахождения главного или неотрицательного квадратного корня (обычно обозначаемого √ S , 2 √ S или S 1/2 ) действительного числа. Арифметически это означает данную S, процедуру нахождения числа, которое при умножении на себя дает S; алгебраически это означает процедуру нахождения неотрицательного корня уравнения x 2 - S = 0; геометрически, это означает, что заданная площадь квадрата, процедура построения стороны квадрата.
Каждое действительное число имеет два квадратных корня. [Примечание 1] Главный квадратный корень большинства чисел - это иррациональное число с бесконечным десятичным разложением. В результате десятичное разложение любого такого квадратного корня может быть вычислено только с некоторым приближением конечной точности. Однако даже если мы извлекаем квадратный корень из полного квадратного целого числа, так что результат действительно имеет точное конечное представление, процедура, используемая для его вычисления, может возвращать только серию все более точных приближений.
Представление непрерывной дроби действительного числа может использоваться вместо его десятичного или двоичного разложения, и это представление обладает тем свойством, что квадратный корень любого рационального числа (который уже не является полным квадратом) имеет периодическое, повторяющееся расширение, подобное как рациональные числа имеют повторяющиеся разложения в десятичной системе счисления.
Наиболее распространенные аналитические методы являются итеративными и состоят из двух этапов: поиск подходящего начального значения с последующим итеративным уточнением до тех пор, пока не будут выполнены некоторые критерии завершения. Начальным значением может быть любое число, но чем ближе оно к окончательному результату, тем меньше итераций потребуется. Самый известный из таких методов, наиболее подходящий для программного расчета, - это метод Ньютона, который основан на свойстве производной в исчислении. Некоторые методы, такие как синтетическое деление по бумаге и карандашу и расширение рядов, не требуют начального значения. В некоторых приложениях требуется целочисленный квадратный корень , который представляет собой квадратный корень, округленный или усеченный до ближайшего целого числа (в этом случае может использоваться модифицированная процедура).
Используемый метод зависит от того, для чего будет использоваться результат (т.е. насколько точным он должен быть), сколько усилий человек готов вложить в процедуру и какие инструменты имеются под рукой. Способы можно грубо разделить на те, которые подходят для мысленных вычислений, на те, которые обычно требуют, по крайней мере, бумагу и карандаш, и на те, которые реализуются как программы, выполняемые на цифровом электронном компьютере или другом вычислительном устройстве. Алгоритмы могут учитывать сходимость (сколько итераций требуется для достижения заданной точности), вычислительную сложность отдельных операций (например, деление) или итераций, а также распространение ошибок (точность конечного результата).
Процедуры нахождения квадратных корней (особенно квадратного корня из 2) были известны, по крайней мере, с периода древнего Вавилона в 17 веке до нашей эры. Метод Герона из Египта первого века был первым установленным алгоритмом для вычисления квадратного корня. Современные аналитические методы начали развиваться после введения арабской системы счисления в Западной Европе в период раннего Возрождения. Сегодня почти все вычислительные устройства имеют быструю и точную функцию извлечения квадратного корня либо в виде конструкции языка программирования, либо как встроенную функцию компилятора, либо как библиотечную функцию, либо как аппаратный оператор, основанный на одной из описанных процедур.
Первоначальная оценка
Многие итерационные алгоритмы извлечения квадратного корня требуют начального начального значения . Начальное число должно быть ненулевым положительным числом; он должен быть от 1 до, число, квадратный корень которого требуется, потому что квадратный корень должен находиться в этом диапазоне. Если семя находится далеко от корня, алгоритм потребует больше итераций. Если инициализировать с x 0 = 1 (или S ), то приблизительноитерации будут потрачены впустую, просто получая порядок величины корня. Поэтому полезно иметь приблизительную оценку, которая может иметь ограниченную точность, но ее легко вычислить. В общем, чем лучше первоначальная оценка, тем быстрее сходимость. Для метода Ньютона (также называемого вавилонским или методом Герона) семя несколько больше, чем корень, сходится немного быстрее, чем семя, несколько меньшее, чем корень.
В общем, оценка соответствует произвольному интервалу, который, как известно, содержит корень (например, [x 0 , S / x 0 ]). Оценка - это конкретное значение функционального приближения к f (x) = √ x на интервале. Для получения более точной оценки необходимо либо получить более жесткие границы интервала, либо найти лучшее функциональное приближение к f (x). Последнее обычно означает использование полинома более высокого порядка в приближении, хотя не все приближения являются полиномиальными. Общие методы оценки включают скалярный, линейный, гиперболический и логарифмический. Десятичное основание обычно используется для оценки в уме или карандашом. Бинарная база больше подходит для компьютерных оценок. При оценке показатель степени и мантисса обычно обрабатываются отдельно, поскольку число выражается в научных обозначениях.
Десятичные оценки
Обычно число выражается в научных обозначениях как где и n является целым числом, а диапазон возможных квадратных корней равен где .
Скалярные оценки
Скалярные методы делят диапазон на интервалы, и оценка в каждом интервале представляется одним скалярным числом. Если диапазон рассматривается как один интервал, среднее арифметическое (5.5) или геометрическое () раз являются правдоподобными оценками. Абсолютная и относительная погрешности для них будут разными. В общем, один скаляр будет очень неточным. Более точные оценки делят диапазон на два или более интервалов, но скалярные оценки по своей сути имеют низкую точность.
Для двух интервалов, разделенных геометрически, квадратный корень можно оценить как [Примечание 2]
Эта оценка имеет максимальную абсолютную ошибку при a = 100 и максимальной относительной погрешности 100% при a = 1.
Например, для учитывается как , оценка . , абсолютная ошибка 246 и относительная ошибка почти 70%.
Линейные оценки
Лучшая оценка и используемый стандартный метод - это линейное приближение к функции по небольшой дуге. Если, как указано выше, мощности основания вычтены из числа и интервал, уменьшенный до [1,100], секущая линия, охватывающая дугу, или касательная линия где-то вдоль дуги может использоваться в качестве приближения, но линия регрессии наименьших квадратов, пересекающая дугу, будет более точной.
Линия регрессии методом наименьших квадратов минимизирует среднюю разницу между оценкой и значением функции. Его уравнение. Повторный заказ,. Округляя коэффициенты для простоты вычислений,
Это лучшая оценка в среднем, которая может быть достигнута с помощью однокомпонентной линейной аппроксимации функции y = x 2 в интервале [1,100]. Он имеет максимальную абсолютную ошибку 1,2 при a = 100 и максимальную относительную ошибку 30% при S = 1 и 10. [Примечание 3]
Чтобы разделить на 10, вычтите единицу из показателя степени , или, образно говоря, переместите десятичную запятую на одну цифру влево. Для этой формулы любая аддитивная константа 1 плюс небольшое приращение даст удовлетворительную оценку, поэтому запоминание точного числа не является бременем. Приближение (с округлением или без) с использованием одной линии, охватывающей диапазон [1,100], составляет менее одной значащей цифры точности; относительная ошибка больше 1/2 2 , поэтому предоставляется менее 2 бит информации. Точность сильно ограничена, поскольку диапазон составляет два порядка величины, что довольно велико для такого рода оценок.
Намного лучшую оценку можно получить с помощью кусочно-линейной аппроксимации: несколько отрезков линии, каждый из которых аппроксимирует некоторую поддугу оригинала. Чем больше линейных сегментов используется, тем лучше приближение. Самый распространенный способ - использовать касательные; критический выбор - как разделить дугу и где разместить точки касания. Эффективный способ разделить дугу от y = 1 до y = 100 - геометрически: для двух интервалов границы интервалов представляют собой квадратный корень из границ исходного интервала, 1 * 100, то есть [1, 2 √ 100 ] и [ 2 √ 100 , 100]. Для трех интервалов границами являются кубические корни из 100: [1, 3 √ 100 ], [ 3 √ 100 , ( 3 √ 100 ) 2 ] и [( 3 √ 100 ) 2 , 100] и т. Д. интервалы, 2 √ 100 = 10, очень удобное число. Касательные линии легко получить, они расположены в точках x = √ 1 * √ 10 и x = √ 10 * √ 10 . Их уравнения: y = 3,56x - 3,16 и y = 11,2x - 31,6. При инвертировании квадратные корни равны: x = 0,28y + 0,89 и x = 0,089y + 2,8. Таким образом, для S = a * 10 2n :
Максимальные абсолютные ошибки возникают в верхних точках интервалов, при a = 10 и 100, и составляют 0,54 и 1,7 соответственно. Максимальные относительные ошибки находятся в конечных точках интервалов при a = 1, 10 и 100 и составляют 17% в обоих случаях. 17% или 0,17 больше 1/10, поэтому точность метода меньше десятичной цифры.
Гиперболические оценки
В некоторых случаях гиперболические оценки могут быть эффективными, потому что гипербола также является выпуклой кривой и может лежать вдоль дуги Y = x 2 лучше, чем прямая. Гиперболические оценки более сложны в вычислительном отношении, потому что они обязательно требуют деления с плавающей запятой. Почти оптимальное гиперболическое приближение к x 2 на интервале [1,100] составляет y = 190 / (10-x) -20. При транспонировании квадратный корень равен x = -190 / (y + 20) +10. Таким образом, для:
Плавающее деление должно иметь точность только до одной десятичной цифры, потому что общая оценка является только такой точной и может быть сделана мысленно. Гиперболическая оценка в среднем лучше, чем скалярная или линейная. Он имеет максимальную абсолютную ошибку 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. [Примечание 4] Процедура требует только небольшой арифметики, чтобы найти граничное число в середине двух произведений из таблицы умножения. Вот справочная таблица этих границ:
а | ближайшая площадь | стандартное восточное время. |
---|---|---|
От 1 до 2,5 | 1 (= 1 2 ) | 1 |
От 2,5 до 6,5 | 4 (= 2 2 ) | 2 |
От 6,5 до 12,5 | 9 (= 3 2 ) | 3 |
От 12,5 до 20,5 | 16 (= 4 2 ) | 4 |
От 20,5 до 30,5 | 25 (= 5 2 ) | 5 |
От 30,5 до 42,5 | 36 (= 6 2 ) | 6 |
От 42,5 до 56,5 | 49 (= 7 2 ) | 7 |
56,5–72,5 | 64 (= 8 2 ) | 8 |
72,5 до 90,5 | 81 (= 9 2 ) | 9 |
90,5 к 100 | 100 (= 10 2 ) | 10 |
Последняя операция - умножить оценку k на степень десяти, разделенную на 2, так что для,
Метод неявно дает одну значащую цифру точности, так как он округляется до лучшей первой цифры.
В большинстве случаев метод может быть расширен до 3 значащих цифр путем интерполяции между ближайшими квадратами, ограничивающими операнд. Если, тогда приблизительно равно k плюс дробь, разница между a и k 2, деленная на разницу между двумя квадратами:
- где
Последняя операция, как и выше, - это умножение результата на степень десяти, деленную на 2;
k - десятичная цифра, а R - дробная часть, которую необходимо преобразовать в десятичную. Обычно он имеет только одну цифру в числителе и одну или две цифры в знаменателе, поэтому преобразование в десятичную форму можно произвести мысленно.
Пример: найти квадратный корень из 75. 75 = 75 × 10 2 · 0 , так что составляет 75 и п равно 0. Из таблицы умножения, квадратный корень из мантиссы должен быть 8 Точка - то из - за 8 × 8 64, но 9 × 9 это 81, слишком большое, поэтому k равно 8; что - то есть десятичное представление R . Дробь R равна 75 - k 2 = 11, числитель, и 81 - k 2 = 17, знаменатель. 11/17 немного меньше, чем 12/18, что составляет 2/3 или 0,67, поэтому предположите 0,66 (здесь можно угадать, ошибка очень мала). Таким образом, оценка составляет 8 + 0,66 = 8,66 . √ 75 до трех значащих цифр составляет 8,66, поэтому оценка подходит для трех значащих цифр. Не все такие оценки с использованием этого метода будут такими точными, но они будут близкими.
Бинарные оценки
При работе в двоичной системе счисления (как в компьютерах внутри), выражая в виде где , квадратный корень можно оценить как
которая является линией регрессии методом наименьших квадратов до трехзначных коэффициентов. имеет максимальную абсолютную погрешность 0,0408 при = 2, и максимальная относительная погрешность 3,0% при = 1. Удобная с вычислительной точки зрения округленная оценка (поскольку коэффициенты являются степенями двойки):
который имеет максимальную абсолютную погрешность 0,086 при 2 и максимальную относительную погрешность 6,1% при = 0,5 и = 2,0.
Для , двоичное приближение дает . , поэтому оценка имеет абсолютную ошибку 19 и относительную погрешность 5,3%. Относительная ошибка немного меньше 1/2 4 , поэтому оценка хороша до 4+ бит.
Оценка для хорошее до 8 бит может быть получено поиском в таблице по старшим 8 битам , помня, что старший бит неявен в большинстве представлений с плавающей запятой, а нижний бит 8 должен быть округлен. Таблица состоит из 256 байтов предварительно вычисленных 8-битных значений квадратного корня. Например, для индекса 11101101 2, представляющего 1,8515625 10 , запись будет 10101110 2, представляющая 1,359375 10 , квадратный корень из 1,8515625 с точностью 10 до 8 (2+ десятичных цифры).
Вавилонский метод
Возможно, первый алгоритм, использованный для аппроксимацииизвестен как вавилонский метод , несмотря на отсутствие прямых доказательств, помимо обоснованного предположения, что одноименные вавилонские математики использовали именно этот метод. [1] Этот метод также известен как метод Герона в честь греческого математика I века Героя Александрийского, который дал первое подробное описание метода в своей работе 60 г. н.э. « Метрика» . [2] Основная идея заключается в том, что если x является завышенным значением квадратного корня неотрицательного действительного числа S, тоS/Иксбудет заниженным, или наоборот, поэтому можно разумно ожидать, что среднее этих двух чисел даст лучшее приближение (хотя формальное доказательство этого утверждения зависит от неравенства арифметических и геометрических средних, которое показывает, что это среднее всегда является завышение значения квадратного корня, как указано в статье о квадратных корнях , что обеспечивает сходимость). Это эквивалентно использованию метода Ньютона для решения.
Точнее, если x - наше первоначальное предположение ои ε - ошибка в нашей оценке такая, что S = ( x + ε ) 2 , то мы можем разложить бином и решить для
- поскольку .
Следовательно, мы можем компенсировать ошибку и обновить нашу старую оценку как
Поскольку вычисленная ошибка не была точной, это станет нашим следующим лучшим предположением. Процесс обновления повторяется до тех пор, пока не будет достигнута желаемая точность. Это квадратично сходящийся алгоритм, что означает, что количество правильных цифр приближения примерно удваивается с каждой итерацией. Это происходит следующим образом:
- Начните с произвольного положительного начального значения x 0 (чем ближе к фактическому квадратному корню из S , тем лучше).
- Пусть x n + 1 будет средним от x n иS/х п(используя среднее арифметическое для аппроксимации среднего геометрического ).
- Повторяйте шаг 2 до тех пор, пока не будет достигнута желаемая точность.
Также его можно представить как:
Этот алгоритм одинаково хорошо работает с p -адическими числами , но не может использоваться для определения действительных квадратных корней с p -адическими квадратными корнями; можно, например, построить последовательность рациональных чисел этим методом, которая сходится к +3 в вещественных числах и к −3 в 2-адиках.
Пример
Чтобы вычислить √ S , где S = 125348, до шести значащих цифр, используйте приведенный выше метод приблизительной оценки, чтобы получить
Следовательно, √ 125348 ≈ 354,045 .
Конвергенция
Предположим , что х 0 > 0 и S > 0. Тогда для любого натурального числа п , х п > 0. Пусть относительная погрешность в х п определяется
и поэтому
Тогда можно показать, что
Таким образом,
и, следовательно, сходимость гарантирована и квадратична .
Худший случай сходимости
Если использовать грубую оценку, приведенную выше, с вавилонским методом, то наименее точные случаи в порядке возрастания будут следующими:
Таким образом, в любом случае,
Ошибки округления замедляют сходимость. Рекомендуется оставить по крайней мере одну дополнительную цифру сверх желаемой точности вычисляемого x n , чтобы минимизировать ошибку округления.
Метод Бахшали
Этот метод нахождения приближения к квадратному корню был описан в древнеиндийской математической рукописи, называемой рукописью Бахшали . Это эквивалентно двум итерациям вавилонского метода, начинающимся с x 0 . Таким образом, алгоритм является квартично сходящимся, что означает, что количество правильных цифр приближения примерно в четыре раза увеличивается с каждой итерацией. [3] Исходное представление с использованием современных обозначений выглядит следующим образом: Чтобы вычислитьПусть х 0 2 будет начальное приближение к S . Затем последовательно выполняйте итерацию как:
Это можно использовать для построения рационального приближения к квадратному корню, начиная с целого числа. Если x 0 = N - целое число, выбранное таким образом, что N 2 близко к S , а d = S - N 2 - разность, абсолютное значение которой минимизировано, то первая итерация может быть записана как:
Метод Бахшали можно обобщить для вычисления произвольного корня, включая корни дробного порядка. [4]
Пример
Используя тот же пример, что и для вавилонского метода, пусть Тогда первая итерация дает
Аналогичным образом вторая итерация дает
Цифра за цифрой
Это метод нахождения каждой цифры квадратного корня в последовательности. Он медленнее, чем вавилонский метод, но имеет ряд преимуществ:
- Это может быть проще для ручных расчетов.
- Известно, что каждая найденная цифра корня верна, т. Е. Ее не нужно менять позже.
- Если квадратный корень имеет завершающееся раскрытие, алгоритм завершается после нахождения последней цифры. Таким образом, его можно использовать, чтобы проверить, является ли данное целое число квадратом .
- Алгоритм работает для любой базы , и, естественно, то, как он работает, зависит от выбранной базы.
Кости Нэпьера включают вспомогательное средство для выполнения этого алгоритма. Сдвиг п - го алгоритм корня является обобщением этого метода.
Основной принцип
Сначала рассмотрим случай нахождения квадратного корня из числа Z , то есть квадрата двузначного числа XY , где X - это цифра десятков, а Y - цифра единиц. Конкретно:
Z = (10X + Y) 2 = 100X 2 + 20XY + Y 2
Теперь , используя алгоритм цифры-по-цифре, мы сначала определить значение X . X - самая большая цифра, такая что X 2 меньше или равно Z, из которого мы удалили две крайние правые цифры.
В следующей итерации пары цифр, умножить X на 2, и поместить его на место десятой в то время как мы пытаемся выяснить , что значение Y есть.
Поскольку это простой случай, когда ответ представляет собой точный квадратный корень XY , алгоритм останавливается на этом.
Затем ту же идею можно распространить на любое произвольное вычисление квадратного корня. Предположим, мы можем найти квадратный корень из N , выразив его как сумму n положительных чисел, таких что
Повторно применяя базовую идентичность
член в правой части может быть расширен как
Это выражение позволяет нам найти квадратный корень, последовательно угадывая значения с. Предположим, что числа уже догадались, то m-й член правой части суммирования равен где - это приблизительный квадратный корень, найденный на данный момент. Теперь каждое новое предположение должен удовлетворять рекурсии
такой, что для всех с инициализацией Когда найден точный квадратный корень; если нет, то суммаs дает подходящее приближение квадратного корня, с ошибка аппроксимации.
Например, в десятичной системе счисления мы имеем
где держатели места и коэффициенты . На любом m-м этапе вычисления квадратного корня приближенный корень, найденный на данный момент, и член суммирования даны
Здесь, поскольку значение места является четной степенью 10, нам нужно работать только с парой старших цифр оставшегося члена на любом m-м этапе. В следующем разделе кодифицируется эта процедура.
Очевидно, что аналогичный метод можно использовать для вычисления квадратного корня в системах счисления, отличных от десятичной. Например, поиск квадратного корня по цифрам в двоичной системе счисления весьма эффективен, поскольку значениеищется по меньшему набору двоичных цифр {0,1}. Это ускоряет вычисления, поскольку на каждом этапе значение либо для или же для . Дело в том, что у нас есть только два возможных варианта также делает процесс определения ценности на m-м этапе расчета проще. Это потому, что нам нужно только проверить, для Если это условие выполнено, то возьмем ; если нет то Кроме того, в вычислениях помогает тот факт, что умножение на 2 выполняется сдвигом битов влево.
Десятичный (основание 10)
Запишите исходное число в десятичной форме. Числа записываются аналогично алгоритму длинного деления , и, как и при длинном делении, корень будет записан в строке выше. Теперь разделите цифры на пары, начиная с десятичной точки и идя влево и вправо. Десятичная точка корня будет выше десятичной точки квадрата. Над каждой парой цифр квадрата появится одна цифра корня.
Начиная с самой левой пары цифр, выполните следующую процедуру для каждой пары:
- Начиная слева, запишите наиболее значимую (крайнюю левую) пару цифр, которые еще не используются (если все цифры были использованы, напишите «00»), и запишите их справа от остатка от предыдущего шага (на первом шаг, остатка не будет). Другими словами, умножьте остаток на 100 и сложите две цифры. Это будет текущее значение c .
- Найдите p , y и x следующим образом:
- Пусть p будет частью корня, найденного до сих пор , игнорируя любую десятичную точку. (Для первого шага p = 0.)
- Определите наибольшую цифру x такую, что. Мы будем использовать новую переменную y = x (20 p + x ).
- Примечание: 20 p + x - это просто удвоенное p , с добавленной справа цифрой x .
- Примечание: x можно найти, угадав, что такое c / (20 · p ), и выполнив пробное вычисление y , а затем при необходимости изменив x вверх или вниз.
- Поместите цифру как следующую цифру корня, то есть над двумя цифрами только что выведенного квадрата. Таким образом, следующий p будет старым p, умноженным на 10 плюс x .
- Вычтите y из c, чтобы получить новый остаток.
- Если остаток равен нулю и нет больше цифр, которые нужно сбрасывать, то алгоритм завершен. В противном случае вернитесь к шагу 1 для другой итерации.
Примеры
Найдите квадратный корень из 152,2756.
1 2. 3 4 / \ / 01 52,27 56 01 1 * 1 <= 1 <2 * 2 x = 1 01 у = х * х = 1 * 1 = 1 00 52 22 * 2 <= 52 <23 * 3 x = 2 00 44 у = (20 + х) * х = 22 * 2 = 44 08 27 243 * 3 <= 827 <244 * 4 x = 3 07 29 y = (240 + x) * x = 243 * 3 = 729 98 56 2464 * 4 <= 9856 <2465 * 5 x = 4 98 56 y = (2460 + x) * x = 2464 * 4 = 9856 00 00 Алгоритм завершается: Ответ 12.34
Двоичная система счисления (основание 2)
Алгоритмам по цифрам присущ шаг поиска и проверки: найти цифру, , при добавлении справа от текущего решения , так что , где это значение, для которого требуется корень. Расширение:. Текущее значение- или, как правило, остаток - может эффективно обновляться постепенно при работе в двоичном формате, так как значение будет иметь один набор бит (степень 2), а операции, необходимые для вычисления а также можно заменить более быстрыми операциями битового сдвига .
Пример
Здесь мы получаем квадратный корень из 81, который при преобразовании в двоичную форму дает 1010001. Числа в левом столбце дают возможность выбора между этим числом или нулем, которые будут использоваться для вычитания на этом этапе вычислений. Окончательный ответ - 1001, что в десятичной дроби равно 9.
1 0 0 1 --------- √ 1010001 1 1 1 --------- 101 01 0 -------- 1001 100 0 -------- 10001 10001 10001 ------- 0
Это дает начало простейшим компьютерным реализациям, таким как эта в C: [5]
int32_t isqrt ( int32_t num ) { assert (( «ввод sqrt должен быть неотрицательным» , num > 0 )); int32_t res = 0 ; int32_t bit = 1 << 30 ; // Устанавливается второй верхний бит. // То же, что ((беззнаковый) INT32_MAX + 1) / 2. // «бит» начинается с наивысшей степени из четырех <= аргумент. в то время как ( бит > число ) бит >> = 2 ; в то время как ( бит ! = 0 ) { если ( число > = разрешение + бит ) { число - = разрешение + бит ; res = ( res >> 1 ) + бит ; } иначе res >> = 1 ; бит >> = 2 ; } return res ; }
Используя обозначения выше, переменная «бит» соответствует который , переменная "res" равна , а переменная num равна текущему что является разностью числа, из которого мы хотим получить квадратный корень, и квадрата нашего текущего приближения со всеми битами, установленными на . Таким образом, в первом цикле мы хотим найти наивысшую степень 4 в «битах», чтобы найти наивысшую степень 2 в. Во втором цикле, если num больше, чем res + bit, то больше, чем и мы можем вычесть это. В следующей строке мы хотим добавить к что означает, что мы хотим добавить к так хотим res = res + bit<<1
. Затем обновите к внутри res, который включает деление на 2 или другой сдвиг вправо. Объединение этих двух в одну строку приводит к res = res>>1 + bit
. Если не больше или равно чем тогда мы просто обновляем к внутри res и делим на 2. Затем обновляем к в битах, разделив его на 4. Последняя итерация 2-го цикла имеет бит, равный 1, и вызовет обновление чтобы выполнить еще один раз, удалив множитель 2 из res, сделав его нашим целочисленным приближением корня.
Более быстрые алгоритмы, в двоичном и десятичном виде или с любой другой базой, могут быть реализованы с помощью таблиц поиска - по сути, обмен большего объема памяти для сокращения времени выполнения . [6]
Экспоненциальная идентичность
Карманные калькуляторы обычно реализуют хорошие процедуры для вычисления экспоненциальной функции и натурального логарифма , а затем вычисляют квадратный корень из S, используя тождество, найденное с использованием свойств логарифмов () и экспоненты (): [ необходима ссылка ]
Знаменатель дроби соответствует корню n- й степени. В приведенном выше случае знаменатель равен 2, следовательно, уравнение указывает, что нужно найти квадратный корень. Тот же принцип используется при вычислении квадратных корней с помощью таблиц логарифмов или правил скольжения .
Итерационный метод с двумя переменными
Этот метод применим для нахождения квадратного корня из и лучше всего сходится для . Это, однако, не является реальным ограничением для компьютерных вычислений, так как в представлениях с плавающей запятой и с фиксированной запятой по основанию 2 тривиально умножить на целую степень 4, и, следовательно, на соответствующую степень двойки, изменяя показатель степени или сдвигая соответственно. Следовательно, можно переместить в диапазон . Более того, следующий метод не использует общих делений, а только сложения, вычитания, умножения и деления на степени двойки, которые снова тривиально реализовать. Недостатком метода является то, что численные ошибки накапливаются, в отличие от итерационных методов с одной переменной, таких как вавилонский.
Шаг инициализации этого метода
в то время как итерационные шаги читаются
Потом, (пока ).
Отметим, что сходимость , а следовательно, и , является квадратичным.
Доказательство метода довольно просто. Во-первых, перепишите итеративное определение в виде
- .
Тогда по индукции нетрудно доказать, что
и, следовательно, сходимость к желаемому результату обеспечивается сходимостью до 0, что, в свою очередь, следует из .
Этот метод был разработан около 1950 г. М. В. Уилксом , Д. Уиллером и С. Гиллом [7] для использования на EDSAC , одном из первых электронных компьютеров. [8] Позже метод был обобщен, что позволило вычислять неквадратные корни. [9]
Итерационные методы вычисления обратных квадратных корней
Ниже приведены итерационные методы нахождения обратного квадратного корня из S, который равен. Как только он будет найден, найдите простым умножением: . Эти итерации включают только умножение, а не деление. Поэтому они быстрее, чем вавилонский метод . Однако они нестабильны. Если начальное значение не близко к обратному квадратному корню, итерации будут отклоняться от него, а не сходиться к нему. Поэтому может быть полезно выполнить итерацию вавилонского метода для грубой оценки, прежде чем начинать применять эти методы.
- Применение метода Ньютона к уравнению производит метод, который сходится квадратично с использованием трех умножений на шаг:
- Другая итерация получается методом Галлея , который является методом Хаусхолдера второго порядка. Это сходится кубически , но требует пяти умножений на итерацию: [ необходима цитата ]
- , а также
- .
- При выполнении арифметики с фиксированной точкой умножение на 3 и деление на 8 можно реализовать с помощью сдвигов и сложений. При использовании чисел с плавающей запятой метод Галлея можно сократить до четырех умножений на итерацию путем предварительного вычисления и корректировка всех остальных констант для компенсации:
- , а также
- .
Алгоритм Гольдшмидта
Некоторые компьютеры используют алгоритм Гольдшмидта для одновременного вычисления а также . Алгоритм Гольдшмидта находитбыстрее, чем итерация Ньютона-Рафсона на компьютере с объединенной инструкцией умножения-сложения и либо конвейерным модулем с плавающей запятой, либо двумя независимыми модулями с плавающей запятой. [10]
Первый способ написания алгоритма Гольдшмидта начинается
- (обычно используется поиск по таблице)
и повторяет
до того как достаточно близко к 1 или фиксированному числу итераций. Итерации сходятся к
- , а также
- .
Обратите внимание, что можно опустить либо а также из расчета, и если оба желательны, то может использоваться в конце, а не вычислять его на каждой итерации.
Вторая форма, использующая объединенные операции умножения и сложения , начинается
- (обычно используется поиск по таблице)
и повторяет
до того как достаточно близко к 0 или фиксированному числу итераций. Это сходится к
- , а также
- .
Серия Тейлора
Если N - приближение к, лучшее приближение можно найти, используя ряд Тейлора функции квадратного корня :
Как итеративный метод, порядок сходимости равен количеству используемых терминов. С двумя терминами он идентичен вавилонскому методу . С тремя членами каждая итерация требует почти столько же операций, сколько приближение Бахшали , но сходится медленнее. [ необходима цитата ] Следовательно, это не особенно эффективный способ расчета. Чтобы максимизировать скорость сходимости, выберите N так, чтобы как можно меньше.
Непрерывное расширение фракции
Квадратичные иррациональные числа (числа вида, где a , b и c - целые числа), и, в частности, квадратные корни из целых чисел имеют периодические цепные дроби . Иногда требуется найти не числовое значение квадратного корня, а его разложение в непрерывную дробь и, следовательно, его рациональное приближение. Пусть S будет положительным числом, для которого нам нужно найти квадратный корень. Затем, предполагая, что a - число, которое служит первоначальным предположением, а r - остаточный член, мы можем написать Поскольку у нас есть , мы можем выразить квадратный корень из S как
Применяя это выражение для к знаменателю дроби, имеем
Расширение числитель / знаменатель для непрерывных дробей (см. Слева) громоздко как для написания, так и для встраивания в системы форматирования текста. Поэтому были разработаны специальные обозначения для компактного представления целых и повторяющихся частей непрерывных дробей. Одним из таких соглашений является использование лексической «собачьей ноги» для представления винкулума между числителем и знаменателем, что позволяет увеличивать дробь по горизонтали, а не по вертикали:
Здесь каждый винкулум представлен тремя линейными сегментами, двумя вертикальными и одним горизонтальным, разделяющими из .
Еще более компактная нотация, в которой отсутствуют лексические приемы, принимает особую форму:
Для повторяющихся непрерывных дробей (что и делают все квадратные корни) повторяющееся выражение представлено только один раз, с надстрочной линией, чтобы обозначить непрерывное повторение выделенной части:
Для √ 2 значение равно 1, поэтому его представление:
Поступая таким образом, мы получаем обобщенную цепную дробь для квадратного корня как
Первым шагом к вычислению такой дроби для получения корня является выполнение числовых замен корня желаемого числа и количества выбранных знаменателей. Например, в канонической форме1 и √ 2 , равно 1, поэтому числовая непрерывная дробь для 3 знаменателей будет:
Шаг 2 - уменьшить непрерывную дробь снизу вверх, по одному знаменателю за раз, чтобы получить рациональную дробь, числитель и знаменатель которой являются целыми числами. Приведение происходит таким образом (принимая первые три знаменателя):
Наконец (шаг 3) разделите числитель на знаменатель рациональной дроби, чтобы получить приблизительное значение корня:
- округлено до трех знаков точности.
Фактическое значение √ 2 составляет 1,41 до трех значащих цифр. Относительная погрешность составляет 0,17%, поэтому рациональная дробь имеет точность почти до трех знаков. Чем больше знаменателей, тем лучше приближение: четыре знаменателя дают дробь, точность почти до 4 разрядов и т. д.
Обычно непрерывная дробь для данного квадратного корня ищется вверх, а не расширяется на месте, потому что это утомительно. Непрерывные дроби доступны как минимум для квадратных корней из малых целых чисел и общих констант. Для произвольного десятичного числа предварительно вычисленные источники могут оказаться бесполезными. Ниже приводится таблица малых рациональных дробей, называемых подходящими дробями, сокращенная из канонических непрерывных дробей для квадратных корней из нескольких общих констант:
√ S | продолжение доля | ~ десятичный | сходящиеся |
---|---|---|---|
√ 2 | 1,41421 | ||
√ 3 | 1,73205 | ||
√ 5 | 2,23607 | ||
√ 6 | 2.44949 | ||
√ 10 | 3,16228 | ||
1,77245 | |||
1,64872 | |||
1,27202 |
Примечание: указаны все подходящие дроби до знаменателя 99 включительно.
В общем, чем больше знаменатель рациональной дроби, тем лучше приближение. Также можно показать, что усечение непрерывной дроби дает рациональную дробь, которая является наилучшим приближением к корню любой дроби со знаменателем, меньшим или равным знаменателю этой дроби, например, без дроби со знаменателем, меньшим или равным 99 - такое же хорошее приближение к √ 2, как 140/99.
Метод последовательности Лукаса
последовательность Лукас первого рода U п ( Р , Q ) определяется рекуррентным соотношениям :
и его характеристическое уравнение:
он имеет дискриминант и корни:
все это дает следующее положительное значение:
так что когда мы хотим , мы можем выбрать а также , а затем вычислить с использованием а также за большую стоимость . Самый эффективный способ расчета а также является:
Резюме:
потом, когда :
Приближения, зависящие от представления с плавающей запятой
Число представлено в формате с плавающей запятой какчто также называется научным обозначением . Его квадратный корень равенаналогичные формулы применимы для кубических корней и логарифмов. На первый взгляд, это не улучшение простоты, но предположим, что требуется только приближение: тогда простохорошо на порядок. Затем осознайте , что некоторые степени p будут нечетными, поэтому для 3141,59 = 3,14159 × 10 3 вместо того, чтобы иметь дело с дробными степенями основания, умножьте мантиссу на основание и вычтите единицу из степени, чтобы сделать ее четной. Скорректированное представление станет эквивалентом 31,4159 × 10 2, так что квадратный корень будет √ 31,4159 × 10 1 .
Если берется целая часть скорректированной мантиссы, могут быть только значения от 1 до 99, и их можно использовать в качестве индекса в таблице из 99 предварительно вычисленных квадратных корней для завершения оценки. Для компьютера с основанием шестнадцать потребуется таблица большего размера, но для компьютера с основанием два потребуются только три записи: возможные биты целой части скорректированной мантиссы равны 01 (степень даже при отсутствии сдвига, помня, что нормализованная число с плавающей запятой всегда имеет ненулевую старшую цифру) или, если степень была нечетной, 10 или 11, это первые два бита исходной мантиссы. Таким образом, 6,25 = 110,01 в двоичном формате, нормализованное до 1,1001 × 2 2 в четной степени, поэтому парные биты мантиссы равны 01, в то время как 0,625 = 0,101 в двоичном формате нормализуется до 1,01 × 2 -1 для нечетной степени, поэтому корректировка составляет 10,1 × 2-2, а парные биты равны 10. Обратите внимание, что бит младшего разряда мощности отражается эхом в бите старшего разряда попарной мантиссы. У четной степени бит младшего разряда равен нулю, а скорректированная мантисса начинается с 0, тогда как для нечетной мощности этот бит равен единице, а скорректированная мантисса начинается с 1. Таким образом, когда мощность уменьшается вдвое, это как если бы ее бит младшего разряда сдвигается, чтобы стать первым битом попарной мантиссы.
Таблица только с тремя записями может быть увеличена за счет включения дополнительных бит мантиссы. Однако с компьютерами, чем вычислять интерполяцию в таблицу, часто лучше найти более простые вычисления, дающие эквивалентные результаты. Теперь все зависит от точных деталей формата представления, а также от того, какие операции доступны для доступа и управления частями числа. Например, Fortran предлагает EXPONENT(x)
функцию для получения мощности. Усилия, затраченные на разработку хорошего начального приближения, должны окупаться за счет исключения дополнительных итераций процесса уточнения, которые потребовались бы для плохого приближения. Поскольку их немного (одна итерация требует деления, добавления и деления пополам), ограничение является серьезным.
Многие компьютеры следуют IEEE (или достаточно похожему) представлению, и для начала метода Ньютона можно получить очень быстрое приближение к квадратному корню. Следующая методика основана на том факте, что формат с плавающей запятой (по основанию два) аппроксимирует логарифм по основанию 2. Это
Таким образом, для 32-битного числа с плавающей запятой одинарной точности в формате IEEE (где, в частности, мощность имеет смещение 127, добавленное для представленной формы), вы можете получить приблизительный логарифм, интерпретируя его двоичное представление как 32-битное целое число, масштабируя это от, и устранение смещения 127, т. е.
Например, 1.0 представлен шестнадцатеричным числом 0x3F800000, которое будет представлятьесли рассматривать как целое число. Используя формулу выше, вы получите, как и ожидалось от . Аналогичным образом получается 0,5 из 1,5 (0x3FC00000).
Чтобы получить квадратный корень, разделите логарифм на 2 и преобразуйте значение обратно. Следующая программа демонстрирует эту идею. Обратите внимание, что младшему разряду экспоненты намеренно разрешено распространяться в мантиссу. Один из способов обосновать шаги в этой программе - это предположить, что - смещение экспоненты и это количество явно сохраненных бит в мантиссе, а затем показать, что
/ * Предполагается, что float имеет формат с плавающей запятой одинарной точности IEEE 754 * / #include float sqrt_approx ( float z ) { объединение { 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 . я + = 1 << 29 ; / * Добавить ((b + 1) / 2) * 2 ^ m. * /вернуть val . f ; / * Снова интерпретируем как float * / }
Три математические операции, составляющие основу вышеупомянутой функции, можно выразить одной строкой. Для уменьшения максимальной относительной погрешности можно добавить дополнительную настройку. Итак, три операции, не считая приведение, можно переписать как
val . я = ( 1 << 29 ) + ( val_int >> 1 ) - ( 1 << 22 ) + a ;
где a - смещение для корректировки ошибок аппроксимации. Например, при a = 0 результаты точны для четных степеней 2 (например, 1,0), но для других чисел результаты будут немного завышенными (например, 1,5 для 2,0 вместо 1,414 ... с ошибкой 6%). При a = −0x4B0D2 максимальная относительная погрешность сводится к минимуму до ± 3,5%.
Если приближение должно использоваться для первоначального предположения метода Ньютона для уравнения, то предпочтительна обратная форма, показанная в следующем разделе.
Величина, обратная квадратному корню
Ниже приведен вариант описанной выше процедуры, который можно использовать для вычисления обратной величины квадратного корня, т. Е.вместо этого был написан Грегом Уолшем. Приближение целочисленного сдвига дало относительную ошибку менее 4%, и ошибка упала еще до 0,15% с одной итерацией метода Ньютона в следующей строке. [11] В компьютерной графике это очень эффективный способ нормализации вектора.
float invSqrt ( float x ) { float xhalf = 0,5f * x ; объединение { float x ; int i ; } u ; u . х = х ; u . i = 0x5f375a86 - ( u . i >> 1 ); / * Следующая строка может повторяться любое количество раз для повышения точности * / u . х = и . х * ( 1.5f - xhalf * u . x * u . x ); верни тебя . х ; }
Некоторые аппаратные средства СБИС реализуют обратный квадратный корень с использованием полиномиальной оценки второй степени, за которой следует итерация Гольдшмидта . [12]
Отрицательный или сложный квадрат
Если S <0, то его главный квадратный корень равен
Если S = a + bi, где a и b действительны и b 0, то его главный квадратный корень равен
В этом можно убедиться, возведя корень в квадрат. [13] [14] Здесь
это модуль из S . Главный квадратный корень комплексного числа определяется как корень с неотрицательной действительной частью.
Смотрите также
- Алгоритм альфа-макс плюс бета-мин
- n- й корневой алгоритм
- Корень квадратный из 2
Заметки
- ^ В дополнение к основному квадратному корню существует отрицательный квадратный корень, равный по величине, но противоположный по знаку основному квадратному корню, за исключением нуля, который имеет двойные квадратные корни из нуля.
- ^ Коэффициенты два и шесть используются потому, что они аппроксимируют средние геометрические наименьшего и наибольшего возможных значений с заданным количеством цифр: а также .
- ^ Неокругленная оценка имеет максимальную абсолютную ошибку 2,65 при 100 и максимальную относительную ошибку 26,5% при y = 1, 10 и 100.
- ^ Если число находится точно посередине между двумя квадратами, например 30,5, угадайте большее число, которое в данном случае равно 6.
- ^ Между прочим, это уравнение касательной к y = x 2 при y = 1.
Рекомендации
- ^ Фаулер, Дэвид; Робсон, Элеонора (1998). «Приближения квадратного корня в древней вавилонской математике: YBC 7289 в контексте». Historia Mathematica . 25 (4): 376. DOI : 10,1006 / hmat.1998.2209 .
- ^ Хит, Томас (1921). История греческой математики, Vol. 2 . Оксфорд: Clarendon Press. стр. 323 -324.
- ^ Бейли, Дэвид; Борвейн, Джонатан (2012). «Древние индийские квадратные корни: упражнение в судебной палео-математике» (PDF) . Американский математический ежемесячник . 119 (8). С. 646–657 . Проверено 14 сентября 2017 .
- ^ «Приводя к рукописи Бахшали» . Просто любопытный блог . 5 июня 2018 . Проверено 21 декабря 2020 .
- ^ Быстрый целочисленный квадратный корень по алгоритму счёта мистера Ву (в архиве)
- ^ Целочисленная функция квадратного корня
- ^ М. В. Уилкс, Д. Уиллер и С. Гилл, "Подготовка программ для электронного цифрового компьютера", Аддисон-Уэсли, 1951.
- ^ М. Кэмпбелл-Келли, «Происхождение вычислений», Scientific American, сентябрь 2009 г.
- ↑ JC Gower, «Заметка об итерационном методе извлечения корня», The Computer Journal 1 (3): 142–143, 1958.
- ^ Маркштейн, Питер (ноябрь 2004 г.). Отделение программного обеспечения и извлечение квадратного корня с использованием алгоритмов Гольдшмидта (PDF) . 6-я конференция по действительным числам и компьютерам . Дагштуль , Германия. CiteSeerX 10.1.1.85.9648 .
- ^ Быстрый обратный квадратный корень Криса Ломонта
- ^ "Высокоскоростное вычисление с двойной точностью обратного, деления, квадратного корня и обратного квадратного корня" Хосе-Алехандро Пиньейро и Хавьер Диас Бругера 2002 (аннотация)
- ^ Абрамовиц, Милтонн; Стегун, Ирен А. (1964). Справочник математических функций с формулами, графиками и математическими таблицами . Courier Dover Publications. п. 17. ISBN 978-0-486-61272-0., Раздел 3.7.26, стр. 17
- ^ Кук, Роджер (2008). Классическая алгебра: ее природа, происхождение и использование . Джон Уайли и сыновья. п. 59. ISBN 978-0-470-25952-8., Выписка: стр. 59
Внешние ссылки
- Вайсштейн, Эрик В. "Алгоритмы извлечения квадратного корня" . MathWorld .
- Квадратные корни путем вычитания
- Алгоритм целочисленного квадратного корня Андрия Радовича
- Алгоритмы персонального калькулятора I: квадратные корни (Уильям Эгберт), Hewlett-Packard Journal (май 1977 г.): стр. 22
- Калькулятор для вычисления квадратного корня