Нахождение квадратного корня данного числа с использованием побитовых операций

Question

Существует ли алгоритм для нахождения квадратного корня данного числа с помощью побитовых операций?

Answer 1

Существует этот знаменитый фрагмент кода , который вычисляет обратный квадратный корень с некоторыми очень умными хитростями.Это ошибочно приписывают Джону Кармаку - вот глубже в его происхождение.Может быть, это то, что вы спрашиваете?

Я бы не советовал использовать его, хотя.На современных процессорах он не может превзойти специальные трансцендентные инструкции.Ваша обычная внутренняя сущность c ++ sqrt(), вероятно, превзошла бы его.

[Edit:] В цитируемой статье описывается общий метод вывода для таких быстрых приближений, и в явном виде говорится: «Извлекайте аналогичный метод для sqrt (x)».'как домашнее задание на последних линиях.Таким образом, вы должны быть в состоянии отследить его обоснование и разработать аналогичный метод для sqrt (без обратной).

Answer 2

Википедия имеет статью и код тоже.И другая статья в Википедии показывает алгоритм (даже для корней больше 2), который может быть легко реализован в двоичном формате (т. Е. С использованием операции над битами).

Если вы хотите придерживаться тольконастоящие побитовые операторы, вы должны реализовать +, используя Ands, Ors, Xors, Nots ... Если вы хотите сделать это с плавающей точкой в ​​соответствии с IEEE, вам нужно больше работать (первый код в википедии может быть использован на мантиссе«напрямую», вероятно, при определенных ограничениях и скорректировать показатель степени «соответственно» ... однако вы должны выяснить, как!)

Answer 3

Нет ... Я предполагаю, что это ради производительности? Если это так, то лучшее, что вы, вероятно, получите, это использование справочной таблицы. Если у вас есть возможность работать с целочисленной математикой (например, работая с числами, умноженными на 10, 100 или 1000 вместо числа с плавающей запятой), вы можете использовать битовое вращение, чтобы быстро отбросить ненужную точность и перейти в таблицу поиска.