![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Entry tags:
Как двоичный корень извлечь
Вы не поверите, насколько просто, оказывается, извлекать вручную квадратный корень в двоичной системе!
https://projectf.io/posts/square-root-in-verilog/
В отличие от десятичной системы, в двоичной это практически в точности как деление столбиком, только знай себе приписывай к пробному "делителю" справа 01.
Например, вычислим корень из 2 с точностью до скольких-нибудь знаков. Припишем к числу 10 несколько групп из пар нулей: 10 00 00 00 00 ...
Дальше будем думать в терминах "текущего остатка" и "текущего результата", первоначально пустых.
Основной шаг алгоритма таков:
Для данного примера имеем:
Действительно, корень из 2 в двоичной системе начинается с 1.011010...
Даже странно, что в современных компьютерах нет операции целочисленного квадратного корня.
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...
Даже странно, что в современных компьютерах нет операции целочисленного квадратного корня.
no subject
no subject