Нахождение квадратного корня данного числа с помощью битовых операций
Существует ли алгоритм для нахождения квадратного корня данного числа с помощью битовых операций?
3 ответа
Есть этот знаменитый фрагмент кода , который вычисляет обратный квадратный корень с очень умным тидлингом. Его ошибочно приписывают Джону Кармаку - здесь более глубокое исследование его происхождения. Может быть, вы об этом спрашиваете?
Я бы не советовал использовать это. На современных процессорах он не может превзойти специальные трансцендентные инструкции. Ваш обычный внутренний C ++ sqrt () , вероятно, победит его.
[Edit:] В процитированной статье описан общий метод вывода для таких быстрых приближений, и в последних строках явно указано, что «Вывести аналогичный метод для sqrt (x)» как домашнее задание. Таким образом, вы должны иметь возможность отслеживать его рассуждения и напрямую разработать аналогичный метод для sqrt (без обратного).
В Википедии есть статья и код. А в другой статье в Википедии показан алгоритм (даже для корней больше 2), который можно легко реализовать в двоичном формате (то есть с использованием операций с битами).
Если вы хотите использовать только реальные побитовые операторы, вам нужно реализовать + с помощью Ands, Ors, Xors, Nots ... Если вы хотите делать это с плавающей точкой в соответствии с IEEE, вам нужно больше работы (первый код в Википедии можно было бы использовать с мантиссой «напрямую», вероятно, с определенными ограничениями, и скорректировать экспоненту «соответственно» ... вы должны выяснить, как, однако!)
Нет ... Полагаю, это ради производительности? Если это так, лучшее, что вы, вероятно, получите, - это использовать таблицу поиска. Если у вас есть возможность работать с целочисленной математикой (например, работая с числами, умноженными на 10, 100 или 1000 вместо чисел с плавающей запятой), вы можете использовать побитовое вращение, чтобы быстро сбросить ненужную точность и перейти в таблицу поиска.