计算机如何计算正弦？

原文 ↗ Hacker News 讨论 ↗

计算机和计算器并不是通过查询一个巨大的表来计算正弦，而是通过范围缩减结合精心选择的多项式近似或 CORDIC 之类的算法，通常会针对硬件约束进行优化。评论者将朴素的泰勒级数（可能不准确或速度慢）与基于 Chebyshev/Remez 的多项式、小型查找表，以及嵌入式系统和老式游戏机中使用的定点技巧进行了对比。讨论还强调了浮点标准如何精确定义基本算术，却对三角函数规定得更宽松，从而导致结果在不同平台上出现细微差异。

收敛性、泰勒级数与数值问题

  • 正弦的泰勒级数在全局上收敛，而且相对较快，但直接求值在数值上很脆弱。
  • 对于较大的 |x|（例如 x = 10），你需要很多项，并且会遇到很大的幂、很大的阶乘以及交替符号带来的相消；有限精度会放大误差。
  • 重写级数（例如因式分解形式）可以提高稳定性，但对于生产级实现来说仍然不是理想方案。
  • 反正弦和其他反三角函数被指出更难处理，因为收敛行为更差。

多项式近似与 Remez

  • 现代做法：先把参数缩减到一个小区间，然后用低阶多项式（Chebyshev / Remez 风格的极小极大）来近似，而不是直接在 0 附近使用原始泰勒展开。
  • 有些评论质疑某个具体示例多项式是否真的来自 Remez，指出它的误差形状更像泰勒展开，并且具有对称性。
  • Remez 被描述为一个简单的迭代算法，在接近极点时可能会遇到困难；在浮点中更偏好加权误差范数。

范围缩减与小型 LUT

  • 实现通常会先做范围缩减（例如使用 π/16 或 π/2 的倍数），然后再应用一个多项式内核。
  • 非常小的查找表（例如约 32 项，或 nπ/16 处的值）再加上多项式修正很常见；由于体积太大，完整的双精度 LUT 不现实。

CORDIC 与多项式方法

  • CORDIC 因其适用于硬件/FPGAs 和小型微控制器而受到强调：只需加法和移位，不需要通用乘法器，并且适合同时计算 sin/cos。
  • 也有人认为，在乘法已经很便宜的地方，CORDIC 已经过时；它收敛较慢（每次迭代大约 1 bit），在现代 CPU/GPU 上不如短多项式。
  • 对于当前 x86/x87 的 sin/cos 是否仍在内部使用 CORDIC 存在争议；其延迟与几十个周期相符，但并不能说明问题。

浮点确定性与标准

  • IEEE-754 严格定义了基本运算，但对超越函数只“推荐”行为；对正确舍入的 sin 来说非常困难（table-maker’s dilemma）。
  • 因此，sin 在不同平台、CPU（例如有无 FMA）、库以及编译器选项之间可能不同。
  • 一些生态系统会提供自己的数学库，以改善跨平台一致性。

表格的历史与实际用途

  • 更早的软件和游戏（例如 Pentium 之前的 PC、主机、复古 demo）通常会使用预计算的三角函数表；有时由辅助代码生成，甚至直接使用印刷出来的表格。
  • 在现代硬件上，内存和缓存成本往往超过大型 LUT 的收益；直接计算有时比查表更快。