··· / Журнал / Квадратный корень без умножений и делений
Квадратный корень без умножений и делений
Извлечение корня - это операция, следующая за 4 простейшими арифметическими действиями и недалеко ушедшая от классического "дважды-два". Квадратный корень из этого "дважды-два", т.е. из 4, равен 2.
Всё, связанное с корнем, давно вылизано и ныне кроме как учебным вряд ли является. И все же... Поискал я в Интернете алгоритм извлечения корня из больших целых чисел, но не нашел ничего подходящего. Зато, оказывается, у отнюдь не профанов есть масса вопросов с квадратным корнем.
Особое внимание в Интернете уделяют извлечению корня столбиком на бумажке. И это в наше-то время! Сейчас на бумажке даже сложить пару чисел мало кто может без ошибок.
Для учебных, бухгалтерских и инженерных расчетов есть компьютеры. В них специально запаяна процедура извлечения квадратного корня, да и само железо так сложено, чтобы максимально ускорить самые ходовые операции.
Но, наверное, многие сталкивались со случаями переполнения, когда разрядности не хватает, происходит потеря точности, а для целых чисел вовсе выскакивает неверный результат.
Кроме того, в ряде математических задач в ходу числа с тысячами и миллионами цифр, для которых запаянных операций не хватает, и надо искать специальные программы, либо сочинять их самому.
Наиболее быстро корень извлекается методом последовательных приближений, основанном на формуле Герона, известной с глубокой древности. Он в основном запаян в ЭВМ. По достигнутому приближению x следующим берется (a/x+x)/2, где a - исходное число, из которого надо извлечь квадратный корень.
Однако, чтобы подобрать количество итераций и обеспечить нужную точность, уже надо быть специалистом. О массе тонкостей, без которых любые алгоритмы не станут работать, в Интернете не распространяются. (А только в старой доброй литературе, например: Математический анализ. Вычисление элементарных функций. Физматгиз, 1963 г.)
Кроме того, в формуле Герона используется деление, которое медлительно, имеет свои проблемы и обычно не приветствуется в алгоритмах. Поэтому, хотя бы для сравнения, полезен простой и надежный алгоритм без умножений и делений.
Задача, по крайней мере, в постановке проста и не требует специальных знаний.
Задают целое число, например, 6 (в двоичной записи это будет 110), и надо получить квадратный корень из него с точностью до меньшего целого, т.е. в данном примере 2. Можно использовать только быстрые операции: сложение, вычитание и сдвиг (который эквивалентен умножению на 2 или делению на 2).
Конечно, можно переписывать числа (т.е. массивы битов) с места на место, сравнивать пару чисел, читать и записывать отдельные биты. Эти операции гораздо быстрее, поэтому при общей оценке скорости важны только многоразовые многоразрядные сложения и сдвиги. Сложность этой задачи не выше, чем хорошей шахматной.
Не так уж она далека от перетасовывания кубиков ребенком. Так что попробовать свои силы может каждый, кто осилил начальную школу. Вообще, всем образованным людям полезно знать хоть немного о нутре компьютера, в частности, что информация хранится там в двоичном виде, т.е. в виде нулей и единичек, называемых битами.
Можно запрограммировать извлечение корня по образцу извлечения столбиком, хотя и там надо потрудиться, чтобы обойтись без умножений.
Но не стоило бы писать эту статью, если бы я не натасовал другой алгоритм, вдвое быстрее и вдвое компактнее. В нем на каждом шаге только одно сложение и один сдвиг. Понятно, что одной операцией, хоть сложением, хоть сдвигом, корня не извлечь. Так что две - это неулучшаемый результат, и если его не видеть воочию, то он походит на фантастику.
N - исходное целое неотрицательное число, r - разрядность (четное число),
Q - для результата, R1,R2 - рабочие.
1. Полагаем Q=R2=0, k=r.
2. Уменьшаем k на 2. Если стало k<0, то конец.
Вычисляем R1=R2+Q и заносим 1 в k-й бит числа R1. Делим Q на 2 (т.е. сдвиг всех битов вправо на одну позицию). Если N>=R1, то заносим 1 в k-й бит числа Q и пишем R1 в R2. Переход на пункт 2.
Комментарий. Смысл R2: это квадрат достигнутого значения квадратного корня, хотя явного значения корня нет. На новом шаге R1 - ожидаемый квадрат, как если бы в очередной бит корня заслали 1. Если R1 не оправдало ожиданий, т.е. N<R1, то R1 забывается, иначе оно запоминается в R2.
В машинных кодах эта подпрограммка занимает 77 байтов на 32-разрядном процессоре и 73 на 16-разрядном, хотя это, вероятнее всего, не предел. Из 1000-разрядного числа корень извлекается за тысячную долю секунды. Потянет и миллионы разрядов, но с квадратичным падением скорости.
Всем успехов в поиске!
Авторская публикация. Свидетельство о публикации в СМИ № J108-50646.
Приведу пример, который не помешал бы и в статье. Извлечем корень из числа 9, в двоичной записи 1001. Изначально N=9, r=4. 1. Q=R2=0, k=r=4. 2. Уменьшаем k на 2, стало k=2, R1=R2+Q=0. Заносим 1 в 2-й бит числа R1. Будет R1=4. Q=0. У нас N>R1, Пишем 1 в 2-й бит числа Q. Стало Q=4. R2=R1=4.
Снова идем на 2-й пункт алгоритма. k=0, R1=R2+Q=4+4=8. Заносим 1 в 0-й бит, стало R1=9. Делим Q на 2, стало Q=2. Теперь N=R1, заносим 1 в 0-й бит числа Q. Стало Q=3, R2=R1=9.
Опять на пункт 2. Теперь k станет < 0, т.е. конец вычислений. Результат: Q=3.
Антоний, благодарю Вас за интерес! Конечно, сначала окажется R1=0. Но в той же строке алгоритма сразу указано, что далее мы заносим 1 в k-й бит, и тогда R1 будет уже не 0, и всё дело благополучно завертится.
Дорогой Антоний! Главное - участие!!! Хотя бы попробовать разобраться - это уже очень много. Большинство коллег не доходит даже до этого.
На всякий случай сообщаю, что у меня всё выверено до мелочей, и сам я - преподаватель математики. А не так, как у некоторых авторов куча математических значков - это просто орнамент, не имеющий никакого отношения к математике.
Обсуждения Квадратный корень без умножений и делений
ну это если полагать R1 4-значным, как и n
Изначально N=9, r=4.
1. Q=R2=0, k=r=4.
2. Уменьшаем k на 2, стало k=2, R1=R2+Q=0.
Заносим 1 в 2-й бит числа R1. Будет R1=4.
Q=0. У нас N>R1, Пишем 1 в 2-й бит числа Q.
Стало Q=4. R2=R1=4.
Снова идем на 2-й пункт алгоритма.
k=0, R1=R2+Q=4+4=8.
Заносим 1 в 0-й бит, стало R1=9.
Делим Q на 2, стало Q=2.
Теперь N=R1, заносим 1 в 0-й бит числа Q.
Стало Q=3, R2=R1=9.
Опять на пункт 2. Теперь k станет < 0,
т.е. конец вычислений. Результат: Q=3.
Конечно, сначала окажется R1=0.
Но в той же строке алгоритма сразу указано, что далее мы заносим 1 в k-й бит,
и тогда R1 будет уже не 0, и всё дело благополучно завертится.
Хотя бы попробовать разобраться - это уже очень много. Большинство коллег не доходит даже до этого.
На всякий случай сообщаю, что у меня всё выверено до мелочей, и сам я - преподаватель математики.
А не так, как у некоторых авторов куча математических значков - это просто орнамент, не имеющий никакого отношения к математике.