¿Cómo calculan los ordenadores el seno?

Artículo original ↗ Discusión en Hacker News ↗

Los ordenadores y calculadoras no calculan el seno buscando en una enorme tabla, sino combinando reducción de rango con aproximaciones polinómicas cuidadosamente elegidas o algoritmos como CORDIC, a menudo adaptados a las limitaciones del hardware. Los comentarios contrastan las series de Taylor ingenuas (que pueden ser inexactas o lentas) con polinomios basados en Chebyshev/Remez, pequeñas tablas de búsqueda y trucos en punto fijo usados en sistemas embebidos y viejas consolas de videojuegos. El intercambio también destaca que los estándares de coma flotante definen con precisión la aritmética básica pero dejan las funciones trigonométricas más laxas, lo que produce pequeñas diferencias entre plataformas en los resultados.

Convergencia, series de Taylor y problemas numéricos

  • La serie de Taylor del seno converge globalmente y es relativamente rápida, pero evaluarla de forma ingenua es numéricamente frágil.
  • Para |x| grandes (por ejemplo, x = 10) se necesitan muchos términos y aparecen potencias grandes, factoriales grandes y cancelación por signos alternantes; la precisión limitada amplifica el error.
  • Reescribir la serie (por ejemplo, en formas factorizadas) mejora la estabilidad, pero aun así no es ideal para implementaciones de nivel de producción.
  • Se señala que arcsin y otras funciones trigonométricas inversas son más difíciles debido a un peor comportamiento de convergencia.

Aproximaciones polinómicas y Remez

  • La práctica moderna: reducir el argumento a un intervalo pequeño y luego aproximarlo con polinomios de bajo grado (minimax al estilo Chebyshev / Remez) en lugar de usar la Taylor bruta alrededor de 0.
  • Algunos comentarios cuestionan si un polinomio de ejemplo concreto proviene realmente de Remez, señalando su forma de error similar a Taylor y su simetría.
  • Se describe Remez como un algoritmo iterativo sencillo que puede tener dificultades cerca de polos; en coma flotante se prefieren normas de error ponderadas.

Reducción de rango y pequeñas LUT

  • Las implementaciones suelen hacer reducción de rango (por ejemplo, con múltiplos de π/16 o π/2) y luego aplicar un núcleo polinómico.
  • Son comunes tablas de búsqueda muy pequeñas (por ejemplo, ~32 entradas o valores en nπ/16) más una corrección polinómica; las LUT completas en doble precisión son inviables por tamaño.

CORDIC frente a métodos polinómicos

  • CORDIC se destaca para hardware/FPGAs y microcontroladores pequeños: sumas y desplazamientos, sin multiplicador general, y útil para sin/cos juntos.
  • Otros sostienen que CORDIC está obsoleto donde las multiplicaciones son baratas, converge lentamente (≈1 bit por iteración) y es peor que polinomios cortos en CPUs/GPUs modernas.
  • Hay desacuerdo sobre si los sin/cos actuales de x86/x87 siguen usando CORDIC internamente; las latencias son consistentes con varias decenas de ciclos, pero no concluyentes.

Determinismo en coma flotante y estándares

  • IEEE-754 define estrictamente las operaciones básicas, pero solo “recomienda” el comportamiento para las trascendentales; obtener un sin correctamente redondeado es difícil (el dilema del fabricante de tablas).
  • Como resultado, sin puede diferir entre plataformas, CPUs (por ejemplo, con FMA o sin FMA), bibliotecas y opciones del compilador.
  • Algunos ecosistemas incluyen sus propias bibliotecas matemáticas para mejorar la consistencia entre plataformas.

Usos históricos y prácticos de las tablas

  • El software antiguo y los juegos (por ejemplo, PCs anteriores al Pentium, consolas, demos retro) usaban comúnmente tablas trigonométricas precalculadas; a veces generadas por código auxiliar o incluso por tablas impresas.
  • En hardware moderno, los costes de memoria y caché a menudo superan el beneficio de grandes LUT; hacer el cálculo puede ser más rápido que consultar una tabla.