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

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

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...

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

Я хочу развидеть это!

Я думал, что меня уже трудно чем-то неприятно удивить. Оказалось, что я ошибался.

( попробуйте и вы )