Math

# 对数

# 简介

对数是高等数学非常重要的概念，人类直到 17 世纪初才发明对数。 恩格斯曾经把对数、解析几何、微积分三大发明称为 17 世纪数学的三大成就。

# 定义

对数是指数运算的逆运算。即假设有 ，则 x 称作以 a 为底的 y 的对数，记作

  • 以 10 为底的对数，可以简写成
  • 以 e 为底的对数，可以简写成
  • 以 2 为底的对数，可以简写成 ，在二分查找里会用到

注意：在 Python 和 JS 里，log 函数默认是以 e 为底的：如 JS 里 Math.log(Math.E) === 1

# 运算法则

名称 公式 证明(TODO)
和差公式
换底公式
次方公式
还原
互换
倒数
链式

这些公式在学校学习的时候很重要，是很多题的解题技巧，善用对数，可以避免天文数字的计算，将乘法运算变为加法运算。

# JS 实现

计算机里使用一些级数公式来计算对数，

参照之前求 和 的实现，大家可以自己尝试编程实现，然后可以对比一下两个公式的效率，在文章下面回复留言。

如果这两个公式都来源于高等数学，如果你不知道这两个公式的推导步骤，即使编程求出结果，也仍然只是工程上的事，今天我主要想讲一个比较直观暴力的方法，但至少能够理解原理。

# 暴力求对数

我们知道对数是指数运算的逆运算，我们可以暴力地用二分法试出来。通过上面的换底公式，我们可以选定一个底。事实上，选择合适的底能降低计算量，为了便于演示，我们就以 10 为底，实现 js 中的 Math.log10 方法。

以 为例，很容易知道，这个数不能大于结果 1000。上次我们已经实现了指数运算，以及绝对值，我们用二分查找试算：

10 ** 1000 过大
10 ** 500 过大
10 ** 250 过大
10 ** 125 过大
10 ** 62.5 过大
10 ** 31.25 过大
10 ** 15.625 过大
10 ** 7.8125 过大
10 ** 3.90625 过大
10 ** 1.953125 小了
   10 ** (1.953125 + (3.90625 - 1.953125) / 2)
   ...

然后是编程实现它，我们要找到所有退出条件：

  • 如果 n == 0，由于没有任何数的次方等于 0（0的0次方数学上没有定义）。我们遵循 IEEE754 的规定返回 -Infinity
  • 如果 n = 1，直接返回 0
  • 幂方结果正好等于 n, 找到了，退出
  • 工程上，我们知道 js 浮点数精度问题，允许小于一定误差，认为两值相等，避免死循环

# 实现

const log10 = (n) => {
  if (n < 0) return NaN
  if (n === 0) return -Infinity
  if (n === 1) return 0
  let ret = n
  let pre = NaN
  while(true) {
    const pow = 10 ** ret
    if (pow > n) {
      pre = ret
      ret /=2
    }
    if (pow === n) break
    if (pow < n) {
      ret += (pre - ret) / 2
    }
    // 防御
    if (Math.abs(pre - ret) < 1e-15) break
  }
  return ret
}