Por qué el algoritmo CORDIC quedó grabado permanentemente en mi cabeza

Por qué el algoritmo CORDIC vive gratis en mi corazón

Evitar Floating Point usando Fixed Point

• Al usar Fixed Point en lugar de Floating Point, se pueden representar números reales
• Usando enteros de 32 bits, los 16 bits superiores se usan para la parte entera y los 16 bits inferiores para la parte fraccionaria
• Con esto se puede representar aproximadamente desde -32768.99997 hasta 32767.99997
• El programador puede ajustar la precisión indicando la posición del punto fijo
• Para convertir de Float a Fixed Point, se multiplica por 2^16 y luego se hace cast a int32_t
• Para convertir de Fixed Point a Float, se divide entre 2^16
• La suma y la resta funcionan tal cual, mientras que en la multiplicación y la división hay que ajustar el Scaling Factor

Resumen del algoritmo CORDIC

• CORDIC es la abreviatura de "Co-ordinate Rotation Digital Computer" y fue desarrollado a mediados de los años 50
• Es un método para obtener valores de seno y coseno rotando gradualmente un vector sobre el círculo unitario con ángulos cada vez más pequeños
• Similar a una búsqueda binaria, primero se mueve con ángulos grandes para acercarse al ángulo objetivo y luego converge reduciendo el ángulo a la mitad, girando en sentido horario o antihorario
• El ángulo máximo de rotación se fija en 90 grados (π/2 radianes) y se repite 16 veces para converger hacia el ángulo objetivo
• El valor y del vector convergente es aproximadamente sin(a) y el valor x es aproximadamente cos(a)

Simplificación de la matriz para usar solo multiplicaciones por constantes

• La matriz de rotación incluye funciones seno, coseno y tangente, por lo que el cálculo es complejo
• Como la función tangente rota con ángulos fijos, se puede precalcular y guardar en una tabla (unos 64 bytes)
• El término del coseno aparece en todas las iteraciones, pero como su valor convergente es una constante (aprox. 0.6366), basta con multiplicarlo una sola vez al final

Usar solo operaciones de Shift y Add

• Los ángulos usados en la función tangente se eligen con la función arcotangente como valores 2^-i
• Esto permite reemplazar la multiplicación por operaciones de desplazamiento de bits
• El valor convergente del término del coseno también se recalcula y queda en aproximadamente 0.60725, que se establece como el valor inicial de x del vector
• Cada iteración del algoritmo CORDIC se simplifica así
  • Si z es mayor o igual que 0, rota en sentido antihorario (restar y>>i de x, sumar x>>i a y)
  • Si z es menor que 0, rota en sentido horario (sumar y>>i a x, restar x>>i de y)
  • Se actualiza z restando o sumando el valor del ángulo desde la tabla
• Así, es posible calcular funciones trigonométricas usando solo multiplicaciones por constantes, desplazamientos de bits y sumas

La opinión de GN⁺

• CORDIC parece ser un algoritmo muy útil en entornos con recursos de hardware limitados, como sistemas embebidos o FPGA. Es especialmente una opción a considerar cuando no se soportan operaciones de punto flotante.
• Resulta muy llamativa la idea de elegir estratégicamente los ángulos de la función tangente para reemplazar multiplicaciones por desplazamientos de bits. Es un gran ejemplo de la combinación entre intuición matemática y comprensión de la arquitectura de computadores.
• También es interesante que pueda usarse no solo para funciones trigonométricas, sino también para calcular logaritmos, exponenciales y raíces cuadradas. Vale la pena revisar también el algoritmo relacionado BKM.
• Aun así, en hardware moderno muchas veces ya viene integrada una FPU, y al usar aritmética de punto fijo puede haber pérdida de precisión, así que conviene tener cuidado al aplicarlo.
• Si se trata de un sistema que necesita realizar muchos cálculos similares, también podría considerarse diseñar hardware dedicado para CORDIC.

[GN⁺]

Opiniones de Hacker News

• El algoritmo CORDIC puede usarse no solo en FPGA, sino también en desarrollo de videojuegos o simulaciones físicas distribuidas. Los cálculos de punto flotante dificultan garantizar un comportamiento determinista entre plataformas, así que implementar un motor físico de punto fijo y las funciones trigonométricas con CORDIC puede ser una posible solución.

• CORDIC puede aplicarse no solo a seno y coseno, sino también a logaritmos, exponenciales, raíces cuadradas, magnitud de vectores, conversión entre coordenadas polares y cartesianas, rotación de vectores y muchas otras operaciones. Usando cuaterniones, parece posible realizar operaciones basadas en CORDIC de forma más eficiente y precisa.

• En una clase de precálculo en la preparatoria aprendieron sobre cómo se implementaban las funciones trigonométricas en las calculadoras, y luego descubrieron que en realidad no era con series de Taylor sino con CORDIC; comparten la experiencia de haberlo implementado personalmente en TI Basic.

• En 2023, incluso MCU de bajo costo como el STM32G4 ya traen FPU integrada, por lo que se puede usar punto flotante libremente en lugar de punto fijo. Sin embargo, el G4 también incluye un periférico CORDIC implementado en hardware dedicado, lo que parece estar pensado para evitar la pérdida de precisión del punto flotante.

• Parece haber un error en la explicación de que una rotación de 22.75° es igual a una rotación de 45° seguida de una de -22.5°. Da la impresión de que debería ser 22.5°.

• El sistema de octree de Meagher fue implementado únicamente con operaciones enteras, sin multiplicación ni división de enteros. Esto facilitó la creación de hardware acelerador gráfico VLSI rápido y hecho a medida para la representación de octrees.

• CORDIC puede verse como un concepto parecido a la sucesión de Farey para ángulos (o mediant, suma ingenua de fracciones).

• CORDIC también fue implementado en calculadoras programables HP vintage con CPU de 4 bits. También es posible programar un método de aproximación usando el desarrollo de Taylor de la función seno.

• Si te gustó este artículo, también vale la pena leer la obra clásica de Donald Knuth, "The Art of Computer Programming", que explica algoritmos matemáticos con ejemplos.

• CORDIC fue un algoritmo muy popular en el campo del DSP en el pasado.

• Es un algoritmo genial y parece que podría ser útil para ejecutar redes neuronales en hardware de bajo rendimiento.