2012-01-15 23 views
7

Estoy tratando de encontrar un poco más de información para algoritmos eficientes de raíz cuadrada que muy probablemente se implementen en FPGA. Ya se han encontrado muchos algoritmos, pero ¿cuál es, por ejemplo, de Intel o AMD? Por eficiente quiero decir que son muy rápidos o no necesitan mucha memoria.¿Implementación de hardware de raíz cuadrada?

EDIT: probablemente debería mencionar que la pregunta es generalmente un número flotante y la mayoría del hardware implementa el estándar IEEE 754 donde el número se representa como: 1 bit de signo, 8 bits de exponente y 23 bits mantissa.

Gracias!

+0

http://stackoverflow.com/questions/1528727/why-is-sse-scalar-sqrtx-slower-than-rsqrtx-x tiene información detallada. –

+0

¿Por qué no implementar [this] (http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Binary_numeral_system_.28base_2.29)? Solo hace turnos y agrega y no se necesita memoria adicional para cosas como tablas de búsqueda. Parece un buen candidato para un FPGA. –

+0

Gracias por el comentario @Alex. Trataré de encontrar algunos recursos más, porque todavía no sé cómo puedo implementar eso en VHDL. Una pregunta más, ¿no encuentra eso solo la parte entera de sqrt? –

Respuesta

5

No es una solución completa, pero un par de consejos.

Supongo que está trabajando en punto flotante, por lo que el punto 1 es recordar que el punto flotante se almacena como mantisa y exponente. El exponente de la raíz cuadrada será aproximadamente la mitad del exponente del número original gracias a los logaritmos.

Luego la mantisa se puede aproximar con una tabla de búsqueda, y luego puede usar un par de rondas newton-raphson para dar cierta precisión al resultado de la LUT.

No he implementado algo como esto durante aproximadamente 8 años, pero creo que así es como lo hice y pude obtener un resultado en 3 o 4 ciclos.

+0

Gracias Paul! ¿Puedes señalarme un algoritmo particular? Sí, estoy trabajando en punto flotante y solo edité mi pregunta ... o podrías ampliar un poco tu explicación porque no entendí todo :) –

+0

Lamentablemente, ha pasado tanto tiempo que no puedo recordar la precisión detalles, y fue para un empleador anterior, así que tampoco puedo buscarlo. Si tiene preguntas específicas, haré todo lo posible para responderlas. –

+0

Gracias @Paul. He marcado su pregunta como la mejor respuesta, ya que eso me dio algunas ideas y me señaló (con suerte) en la dirección correcta. Gracias –

2

Este es uno excelente para la raíz inversa de quar rápido.
Échale un vistazo here. Fíjate que es más o menos la conjetura inicial, un documento bastante sorprendente :)

+0

¡Muchas gracias! Ya lo he visto y parece bastante impresionante, sin embargo, el "número mágico" me asustó un poco al principio. Volveré a echar un vistazo :) –

+0

No creo que esta respuesta sea realmente relevante para la pregunta. Este algoritmo solo calcula una aproximación aproximada del inverso de la raíz cuadrada, y definitivamente no se implementó en el –

+0

de FPGA Gracias Sven. ¿La mayoría de las implementaciones en FPGA solo usan alguna variante en el método de Newton-Raphson? Como una inversión para deshacerse de la división, que a su vez es una operación costosa? –

Cuestiones relacionadas