algorithm - 对数是如何编程的？

Question

他们只是使用与线性搜索相同的机制找出来，还是以某种方式缩小范围，类似于二进制搜索。

Answer 1

在任何体面的数学库中实现诸如自然对数之类的函数将使误差保持在 ulp（最低精度单位）以下。数学库函数的实现者的目标是找到一些最佳近似值，以尽可能少的计算达到所需的精度。泰勒级数通常是一个糟糕的选择，因为需要太多项才能达到所需的精度。

选择的典型武器是将所有可表示实数的范围缩小到某个非常小的区域，然后使用一些最佳近似值，在这个狭窄范围内产生所需函数的精确近似值。这种最佳近似选择的典型武器是多项式或有理多项式（两个多项式的比率）。该实现仅包含多项式系数。这些系数是通过一些优化技术构建的，例如 Remes Exchange 算法。

在自然对数的情况下，有一种简单的方法可以减小范围。实数几乎普遍用尾数和指数表示：x = m *2 ^p，其中p是整数，m介于 1 和 2 之间。因此 log( x ) = log( m )+ p *log( 2）。后一项，p*log(2) 只是乘以已知常数。因此，问题归结为找到 1 和 2 之间（或 1/2 和 1 之间）数字的对数。通过使用 √2 在 [1,2) 的中间对数，可以进一步缩小范围。因此，所需要的只是一种计算 1 到 √2 之间数字的对数的方法。这通常使用有理多项式来完成。二阶多项式多项式与三阶多项式的比率对此非常有效。