Оригинальный метод извлечения квадратного корня
TODO Обновить в соответствие с оригиналом (спасибо упомянутому ниже С. В. Савичу за текст).
Автор — Елизавета Александровна Калинина; оригинал статьи спасён с WebArchive -- FrBrGeorge 2022-08-16 10:27:45
Об извлечении квадратного корня в столбик я уже писала здесь. Сейчас хочу вам предложить модификацию этого метода, которая мне кажется гораздо более простой и красивой. Предложил ее Сергей Валентинович Савич, который и написал мне об этом. Метод был изобретен для арифмометра — механической вычислительной машины, на которой в свое время считали, причем очень активно. Вот что пишет сам Сергей Валентинович:
- «Схема вычисления квадратных корней была придумана мной в конце 70-х г., и мне хотелось даже опубликовать её описание. Но время арифмометров закончилось, и этот алгоритм остался только в моей памяти. Теперь немного истории. В 1975–76 гг. я учился в Ленинградском топографическом техникуме, и у нас было очень много высокоточных измерений и расчётов. Калькуляторов и ПК тогда ещё не было, всё считали на арифмометрах, а значения функций приходилось брать из толстых 7 — 10-значных таблиц. Тогда у меня и появилась мысль “научить” арифмометр вычислять корни. Проштудировал кучу литературы, но ничего подходящего не нашёл. Методы последовательных приближений (дихотомии, Ньютона) отложил как неэкономичные для реализации на арифмометре. Когда я узнал о свойстве арифметической прогрессии нечётных чисел, то решил попробовать на его основе разработать алгоритм извлечения квадратного корня. Наибольшую трудность представляло то, что я никак не мог сообразить, что делать с остатком от вычитания квадрата первой цифры из аргумента. Интуитивно было понятно, что решение где-то рядом. В общем, вертел этот остаток и так, и сяк, и в конечном итоге набрёл на правильное решение.»
Как уже говорилось, идея очень красивая. В основе метода лежит следующее свойство суммы $$n$$ первых нечетных чисел:
$$1+3+5+\ldots+(2n-1)=n^2$$ .
Доказать это легко, если вспомнить формулу суммы $$n$$ первых членов арифметической прогрессии. Еще понадобится следующая идея, которая основывается на этом свойстве. Если требуется приписать к какому-то числу $$a$$ справа еще одну цифру b, а потом умножить полученное число на эту же цифру, то сделать это можно сложением $$b$$ последовательных нечетных чисел:
$$(10a+b)\cdot b=(10a+1)+(10a+3)+(10a+5)+\ldots+(10a+(2b-1))$$ .
Действительно, давайте раскроем скобки во всех $$b$$ слагаемых справа и их перегруппируем:
$$(10a+1)+(10a+3)+(10a+5)+\ldots+(10a+(2b-1))=$$
$$=10ab+(1+3+5+\ldots+(2b-1))=10ab+b^2=(10a+b)b$$ .
А теперь можно изменять метод, о котором уже было рассказано. Я опишу каждый шаг, а затем на примере покажу, как он выполняется.
Сначала мы точно так же, как было описано, делим число, из которого будем извлекать квадратный корень, на группы цифр, по две цифры в каждой группе. Целую часть числа (то, что стоит слева от десятичной запятой) разбиваем на группы по две цифры справа налево, а дробную часть (начиная от первой цифры справа от десятичной запятой) — слева направо. Пример давайте рассмотрим тот же, что уже был просчитан. Можно будет сравнить, насколько проще получается алгоритм. Возьмем число $$56789,321$$. Итак, разбиваем цифры этого числа на пары $$5^{\prime}67^{\prime}89.32^{\prime}1$$.
Из первой группы цифр слева вычитаем последовательно нечетные числа $$1,3,5,7,\ldots,(2n-1)$$ до тех пор, пока не получится отрицательное число. Запомним последнюю положительную разность, которая получилась — $$A$$, и то число, которое при этом вычитали — $$2n-1$$. Если последняя разность равна $$0$$, то корень извлечен точно. В нашем примере можно вычесть два нечетных числа: $$5-1=4,4-3=1$$ . Это означает, что первая цифра корня — $$2$$, остаток $$A = 1$$, вычитали при его получении число $$2n - 1 = 3$$. Здесь $$n$$ — порядковый номер последнего нечётного числа. Далее, к последнему вычитаемому прибавим $$1$$. В нашем случае к $$3$$ прибавляем $$1$$, получаем число $$y = 4$$.
Теперь к остатку $$A$$ справа припишем следующую группу $$C$$ из двух цифр подкоренного числа, получим число $$100A + C$$. В нашем примере, приписывая следующие две цифры, получим число $$167$$. Из числа $$100A + C$$ снова начинаем вычитать последовательно нечётные числа, предварительно сдвинув вычитаемое на один разряд вправо. Эти нечётные числа формируются следующим образом: первое число, которое будем вычитать, будет число y, к которому справа припишем цифру $$1$$, т.е. $$10y + 1$$, затем $$10y + 3; 10y + 5;\ldots, 10y + (2n - 1)$$. Делаем вычитания до тех пор, пока остаток не станет меньше вычитаемого. И снова запомним остаток (это будет $$A$$), последнее вычитаемое $$10y + (2n - 1)$$ и количество вычитаний n. Если же получили разность $$0$$, и оставшиеся цифры в подкоренном числе — нули, то корень извлечён точно. В нашем примере делаем следующие действия: $$167- 41 = 126; 126 - 43 = 83; 83 - 45 = 38; 38 < 47$$, поэтому вычитания прекращаем. Было выполнено три вычитания, значит, следующая цифра корня — $$3$$.
Если нам нужно посчитать следующие цифры корня, то возьмём снова ту последнюю положительную разность, которую мы запомнили в п. $$3$$, как $$A$$ и последнее вычитаемое $$10y + (2n - 1)$$, увеличенное на $$1$$ — как $$y$$. Для разбираемого нами примера получим $$A = 38, y = 45 + 1 = 46$$. И повторяем алгоритм, начиная с шага 3. В том случае, если первое вычитаемое $$10y + 1$$ больше, чем $$100A + C$$, то следующая цифра корня — $$0$$, так как ни одного вычитания сделать нельзя. В этом случае принимаем $$100A + C$$ за $$A$$, $$10y$$ за $$y$$, и выполняем действия, начиная с шага 3. Если же корень вычислен точно (последняя разность равна $$0$$ и оставшиеся цифры справа в подкоренном числе — нули) или корень вычислен с требуемой точностью, то завершаем процесс. Далее я не буду описывать все шаги, просто приведу то, что получается, если все вычисления записать в столбик. Пояснения — в фигурных скобках.
К сожалению, в этом месте была картинка, и она на webarchive не попала -- FrBrGeorge 2022-08-16 10:27:45
$$\sqrt{56789,321} = 238,305$$ {точность — 6 значащих цифр, 21 вычитание}
Как видно из приведённого описания, этот способ легко может быть формализован и записан в виде программного кода для ЭВМ, причём время выполнения этой программы сопоставимо с временем выполнения операции деления. Сергей Валентинович предложил также некоторые изменения, упрощающие процесс вычислений и позволяющие повысить точность. Так, можно заметить, что после каждого цикла вычитаний цифры последнего вычитаемого, увеличенного на $$1$$ (т.е. y, по нашему соглашению), представляют собой цифры удвоенного значения корня. Поэтому можно не подсчитывать число вычитаний, а просто разделить y, полученное из последнего вычитаемого, на $$2$$. Положение запятой можно определить, руководствуясь следующим правилом: количество цифр целой части результата равно количеству пар цифр в целой части аргумента, каждой паре цифр аргумента соответствует одна цифра результата.
Примеры
аргумент $$61\prime71,67\prime36$$ (1)
результат $$78,56$$
аргумент $$0,00\prime78\prime93\prime10$$ (2)
результат $$0,08884312$$
Кроме этого, вдобавок можно получить ещё примерно столько же значащих цифр, сколько уже было получено, простым делением последнего остатка с приписанными неиспользованными парами цифр на последнее вычитаемое, увеличенное на $$1$$. Для описанного нами примера имеем: $$47975 / 476610 = 0,10065881\ldots$$; Здесь шесть цифр $$100659$$ являются, с учётом округления последней, верными. Отсюда получаем конечный результат с точностью 12 дес. знаков (!): $$\sqrt{56789,321} = 238,305100659$$. Конечно, вычислять вручную с такой точностью значения корней вряд ли целесообразно, но данное правило позволяет для нахождения корней с точностью 5-6 знаков ограничиться вычислением с помощью вычитания нечётных чисел только 3-х цифр.
Ни Сергей Валентинович, ни я нигде не встречали описание данного метода. Если кто-либо из вас где-то об этом читал, напишите, пожалуйста. Заранее большое спасибо.
Подробный пример извлечения квадратного корня на арифмометре можно увидеть в статье Савича С.В.
Есть похожая статья на английском -- FrBrGeorge 2022-08-16 10:27:45