Как двоичный корень извлечь

[spamsink]

Вы не поверите, насколько просто, оказывается, извлекать вручную квадратный корень в двоичной системе!

https://projectf.io/posts/square-root-in-verilog/

В отличие от десятичной системы, в двоичной это практически в точности как деление столбиком, только знай себе приписывай к пробному "делителю" справа 01.

Например, вычислим корень из 2 с точностью до скольких-нибудь знаков. Припишем к числу 10 несколько групп из пар нулей: 10 00 00 00 00 ...

Дальше будем думать в терминах "текущего остатка" и "текущего результата", первоначально пустых.

Основной шаг алгоритма таков:

• Добавим справа к текущему остатку очередную пару бит аргумента.
  
• Для пробы добавим справа к текущему результату магическую пару бит 01.
  
• Сравним текущий остаток и пробный результат. Если остаток меньше, то припишем справа к текущему результату 0; иначе вычтем пробный результат из текущего остатка и припишем справа к текущему результату 1.
  

Для данного примера имеем:

Остаток	Проба	Результат	Комментарий
10	01	1	10 - 01 = 01 в остатке
01 00	1 01	10	остаток не изменился
01 00 00	10 01	101	10000 - 1001 = 111 в остатке
01 11 00	1 01 01	1011	11100-10101 = 111 в остатке
01 11 00	10 11 01	10110	остаток не изменился
01 11 00 00	1 01 10 01	101101	1110000-1011001=10111
01 01 11 00	10 11 01 01	1011010	...

Действительно, корень из 2 в двоичной системе начинается с 1.011010...

Даже странно, что в современных компьютерах нет операции целочисленного квадратного корня.

Comments

[sobriquet9]

Похоже на метод поиска верблюда в пустыне последовательным делением области поиска пополам. Поднимаем по одному биты, начиная со старших, если квадрат получился больше - опускаем обратно, поднимаем следующий бит. Если квадрат получился меньше - оставляем поднятым и переходим к следующему биту.

[spamsink]

Удобство в том, что собственно умножать никогда не приходится.

[sobriquet9]

Квадрат мы всё равно считаем, только не каждый раз целиком, а один раз и постепенно, добавляя по одной четверичной цифре за итерацию.

[nicolas83]

Корень из 2х = 1.4142135 (с деццтва помню).

[spamsink]

Нет, корень из 2х - это примерно 1.4142135, умноженное на корень из x.

А вот корень из 2 - это да, примерно 1.4142135.

[nicolas83]

Сэр, Вы зануда.

Догадываюсь, что, если бы я написал "корень из 2-х", Вы бы не преминули определить, что х ≤2.

[spamsink]

Я не зануда, я в данном случае чистоплюй. Когда я вижу падежные наращения у количественных числительных, я брезгливо морщусь.

[nicolas83]

Хм, а дело хуже, чем я только мог предположить... :-)

[spamsink]

Чего ж плохого, просто порядок должен быть.