How do computers calculate sine?

Original Article ↗ Hacker News Discussion ↗

Computers and calculators don’t compute sine by looking it up in a giant table, but by combining range reduction with carefully chosen polynomial approximations or algorithms like CORDIC, often tailored to hardware constraints. Commenters contrast naïve Taylor series (which can be inaccurate or slow) with Chebyshev/Remez-based polynomials, small lookup tables, and fixed‑point tricks used in embedded systems and old game consoles. The exchange also highlights how floating-point standards define basic arithmetic precisely but leave trig functions looser, leading to small, platform-dependent differences in results.

Convergence, Taylor Series, and Numerical Issues

  • Sine’s Taylor series is globally convergent and relatively fast, but naïve evaluation is numerically fragile.
  • For large |x| (e.g., x = 10) you need many terms and face large powers, large factorials, and alternating-sign cancellation; limited precision amplifies error.
  • Rewriting the series (e.g., factored forms) improves stability but still isn’t ideal for production-grade implementations.
  • Arcsin and other inverse trig functions are noted as harder due to worse convergence behavior.

Polynomial Approximations and Remez

  • Modern practice: reduce the argument to a small interval, then approximate with low-degree polynomials (Chebyshev / Remez-style minimax) instead of raw Taylor around 0.
  • Some comments question whether a specific example polynomial is actually from Remez, pointing out its Taylor-like error shape and symmetry.
  • Remez is described as a simple iterative algorithm that can struggle near poles; weighted error norms are preferred in floating point.

Range Reduction and Small LUTs

  • Implementations typically perform range reduction (e.g., with multiples of π/16 or π/2), then apply a polynomial kernel.
  • Very small lookup tables (e.g., ~32 entries or values at nπ/16) plus polynomial correction are common; full double-precision LUTs are infeasible due to size.

CORDIC vs Polynomial Methods

  • CORDIC is highlighted for hardware/FPGAs and tiny microcontrollers: adds and shifts, no general multiplier, good for sin/cos together.
  • Others argue CORDIC is obsolete where multiplies are cheap, converges slowly (≈1 bit per iteration), and is worse than short polynomials on modern CPUs/GPUs.
  • There is disagreement whether current x86/x87 sin/cos still use CORDIC internally; latencies are consistent with several dozen cycles but not conclusive.

Floating-Point Determinism and Standards

  • IEEE-754 strictly defines basic operations but only “recommends” behavior for transcendentals; correctly rounded sin is hard (table-maker’s dilemma).
  • As a result, sin can differ across platforms, CPUs (e.g., FMA vs no FMA), libraries, and compiler options.
  • Some ecosystems ship their own math libraries to improve cross-platform consistency.

Historical and Practical Uses of Tables

  • Earlier software and games (e.g., pre-Pentium PCs, consoles, retro demos) commonly used precomputed trig tables; sometimes generated by auxiliary code or even printed tables.
  • On modern hardware, memory and cache costs often outweigh the benefit of large LUTs; doing the math can be faster than table lookup.