Encontrar la raíz cuadrada de un número dado usando operaciones bit a bit

Question

¿Hay un algoritmo para encontrar la raíz cuadrada de un número dado usando operaciones bit a bit?

Answer 1

Hay this famous piece of code magic que calcula inversa raíz cuadrada con un poco de astucia muy inteligente. Se atribuyó erróneamente a John Carmack - here's a deeper dig en su origen. Tal vez es por eso que preguntas?

No recomendaría su uso, sin embargo. En las CPU modernas no puede vencer las instrucciones trascendentales dedicadas. Su habitual C++ intrínseca sqrt() probablemente lo superaría sin lugar a dudas.

[Editar:] El artículo citado describe un método de derivación general para tales aproximaciones rápidas, y explícitamente dice 'Derivar un método similar para sqrt (x)' como un problema de tarea en sus líneas finales. Por lo tanto, debería poder rastrear su razonamiento e idear un método similar para sqrt (sin recíproco) directamente.

Answer 2

No ... Supongo que es por el bien de rendimiento? Si es así, lo mejor que probablemente obtendrás es usar una tabla de búsqueda. Si tiene la opción de trabajar con matemática entera (por ejemplo, trabajando con números multiplicados por 10, 100 o 1000 en lugar de flotantes), puede usar la rotación en modo bit para quitar rápidamente la precisión innecesaria y saltar a una tabla de búsqueda.

Answer 3

Wikipedia tiene un artículo sobre y un código también. Y another wikipedia article muestra un algoritmo (incluso para las raíces mayores que 2) que se puede implementar fácilmente en binario (por lo tanto, que implica la operación en bits).

Si desea adherirse solo a los operadores de bit a bit reales, debe implementar + usando Ands, Ors, Xors, Nots ... Si desea hacerlo en flotadores de acuerdo con IEEE, necesita más trabajo (el primero el código en wikipedia podría usarse en la mantisa "directamente", probablemente bajo cierta restricción, y ajustar el exponente "en consecuencia" ... ¡hay que averiguar cómo, sin embargo!)