幂与对数

幂

幂是指将一个数(底数)自乘若干次(由指数决定)的运算。其一般形式为 $a^{n}$ ，表示 $a$ 乘以自身 $n$ 次。

如 $1 0^{3} = 10 \times 10 \times 10 = 1000$ 中， $10$ 是底数， $3$ 是指数。

不同指数的幂有特性:

正整数指数

域: $n \in N^{+}$ ¹
定义: $a^{n} = a \times a \times \dots \times a$
性质:
- $a^{m} \times a^{n} = a^{m + n}$
- $(a^{m})^{n} = a^{mn}$
- $a^{n} \times b^{n} = (a + b)^{n}$
- $a^{m} / a^{n} = a^{m - n}$

零指数

域: $n = 0$
定义: $a^{0} = 1 (a \neq = 0)$
注:
- 这是为了保持幂运算的连续性，例: $a^{m} / a^{m} = 1 = a^{0}$ ，确保像这类运算可以正常执行。
- $0^{0}$ 未定义的。(某些情况下等于一 $1$ 但不推荐使用)

负整数指数

域: $n \in Z^{-}$
定义: $a^{n} = \frac{1}{a ^{- n}}$
注:
- 负指数表示倒数。
- 这是为了扩展幂运算的定义域，使其在整数范围内封闭。

分数指数

域: $n = \frac{p}{q} 其中 p, q \in Z, q \neq = 0$
定义: $a^{\frac{p}{q}} = (q a)^{p}$

注: 分数指数的本质是将幂运算延拓到有理数集。这里的推广基于正整数指数的性质: $(a^{m})^{n} = a^{mn}$ :

如果分数指数要满足该性质，我们可以用一个简单的式子: $(a^{\frac{1}{q}})^{q} = a^{(\frac{1}{q} \times q)} = a$ 看前面的一项 $设 x = (a^{\frac{1}{q}}), 则 x^{q} = a ∵ (q a)^{q} = a ∴ x = q a 即 a^{\frac{1}{q}} = x = q a$ 再利用 $(a^{m})^{n} = a^{mn}$ ，不难得到 $a^{\frac{p}{q}} = a^{\frac{1}{q} \times p} = (q a)^{p}$ 。

无理指数

域: $n \in R / Q$
注: 无理指数将幂运算延拓到实数甚至复数集。

定义: 设 $a > 0$ 是一个正实数， $α$ 是一个无理数。选取一个有理数序列 ${r_{n}}$ 使得 $lim_{n \to \infty} r_{n} = α$ ，则无理指数 $a^{α}$ 定义为: $a^{α} = n \to \infty lim a^{r_{n}}$ 这个方法的本质是通过有理数无限逼近一个无理数来进行。我们也可以通过指数函数来进行延拓，此处不再赘述。

编程中使用

一般来讲，我们将设计的幂算法只支持自然数。更广的作用域，在编程中通常不使用。接下来我们开始设计:

从定义出发，我们不难想到只需要对一个基数进行循环n次，每次乘它自身，便可得到:

pub fn power_iter(base: i64, exponent: u32) -> i64 {
    // 下面省略溢出检测
    let mut result = 1;
    for _ in 0..exponent {
        result *= base;
    }
    result
}

它的时间复杂度是 $Θ (n)$ ，对于较大的输入规模，这个算法可能并不特别好。我们还有一种名为快速幂的方法:

fn power_fast(mut base: i64, mut exponent: u32) -> i64 {
    let mut result = 1;
    while exponent > 0 {
        if exponent % 2 == 1 {
            result *= base;
        }
        base *= base;
        exponent /= 2;
    }
    result
}

它采用分治法的策略，时间复杂度是 $Θ (lo g n)$ 。其数学基础是对于输入规模 $n$ ，如果它是偶数，那么 $a^{n} = (a^{2})^{n /2}$ ，如果它是奇数，那么 $a^{n} = a (a^{2})^{(n - 1) /2}$ 。快速幂算法实际上是在利用指数的二进制表示: $13 = 110 1_{2} = 8 + 4 + 1 = 2^{3} + 2^{2} + 2^{0} 3^{13} = 3^{(8 + 4 + 1)} = 3^{8} \times 3^{4} \times 3^{1}$ ²

所以完全可以用位运算:

fn power_fast(mut base: i64, mut exponent: u32) -> i64 {
    let mut result = 1;
    while exponent > 0 {
        if exponent & 1 == 1 {  // 等价于 exponent % 2 == 1
            result *= base;
        }
        base *= base;
        exponent >>= 1;  // 等价于 exponent /= 2
    }
    result
}

利用std中pow可以直接进行幂运算:

let base = 2;
let exponent = 3;
let result = base.pow(exponent); // 2^3 = 8

对数

对数(Logarithm) 是数学中用于简化乘除运算的一种函数，定义为幂运算的逆运算。具体来说，如果满足以下等式: $a^{b} = N (a > 0, a \neq = 1)$ 那 $b$ 就是以 $a$ 为底 $N$ 的对数，记作: $b = lo g_{a} N$ 其中， $a$ 为底数( $a > 1$ )， $N$ 为真数( $N > 0$ )。在上面这两个式子中，我们可以得到对数与指数的关系: $lo g_{a} N = b ⟺ a^{b} = N$ 我们常用几种特殊的对数:

$10$ : 常用对数。 $lo g_{1} 0$ (可以简写为 $l g$ )，用于科学计算和工程。
$e$ : 自然对数。 $lo g_{e}$ (可以简写为 $ln$ )，广泛用于微积分和自然科学。
$2$ : 二进制对数。 $lo g_{2}$ (仅在计算机科学中，我们可以简写为 $lo g$ )，常见于计算机科学和信息论。

性质

对数的运算有很多特殊的性质:

乘法性质

性质：
$lo g_{a} (MN) = lo g_{a} M + lo g_{a} N (M, N > 0)$

证明：
设 $x = lo g_{a} M$ ， $y = lo g_{a} N$ ，则：
$a^{x} = M, a^{y} = N$
两式相乘：
$a^{x} \cdot a^{y} = MN ⟹ a^{x + y} = MN$
取对数得：
$lo g_{a} (MN) = x + y = lo g_{a} M + lo g_{a} N$
证毕。

除法性质

性质：
$lo g_{a} (\frac{M}{N}) = lo g_{a} M - lo g_{a} N (M, N > 0)$

证明：
设 $x = lo g_{a} M$ ， $y = lo g_{a} N$ ，则：
$a^{x} = M, a^{y} = N$
两式相除：
$\frac{a ^{x}}{a ^{y}} = \frac{M}{N} ⟹ a^{x - y} = \frac{M}{N}$
取对数得：
$lo g_{a} (\frac{M}{N}) = x - y = lo g_{a} M - lo g_{a} N$
证毕。

幂运算性质

性质：
$lo g_{a} (M^{k}) = k lo g_{a} M (M > 0, k \in R)$

证明：
设 $x = lo g_{a} M$ ，则：
$a^{x} = M ⟹ (a^{x})^{k} = M^{k} ⟹ a^{k x} = M^{k}$
取对数得：
$lo g_{a} (M^{k}) = k x = k lo g_{a} M$
证毕。

换底公式

性质：
$lo g_{a} N = \frac{lo g _{b} N}{lo g _{b} a} (a, b, N > 0, a, b \neq = 1)$

证明：
设 $x = lo g_{a} N$ ，则：
$a^{x} = N ⟹ lo g_{b} (a^{x}) = lo g_{b} N ⟹ x lo g_{b} a = lo g_{b} N$
解得：
$x = \frac{lo g _{b} N}{lo g _{b} a}$
即：
$lo g_{a} N = \frac{lo g _{b} N}{lo g _{b} a}$
证毕。

特殊值性质

性质1：
$lo g_{a} 1 = 0$
证明：
由 $a^{0} = 1$ ，根据定义：
$lo g_{a} 1 = 0$
证毕。

性质2：
$lo g_{a} a = 1$
证明：
由 $a^{1} = a$ ，根据定义：
$lo g_{a} a = 1$
证毕。

对数将复杂的乘除、幂运算转化为加减乘除，是数学和科学中不可或缺的工具。

在编程中使用

其实在幂那里我们就已经知道了——由于计算机的二进制特性，利用位运算我们可以计算整数以 $2$ 为底的对数:

pub fn log2_bitwise(n: u32) -> u32 {
    // 下面省略数据校验
    31 - n.leading_zeros()
}

位操作法 的核心思想是一个整数的二进制表示中，最高有效位(MSB)的位置即为其以2为底的对数。n.leading_zeros() 返回n的二进制表示中前导零³的个数。u32的二进制长度是32，由于位置编号从0开始(范围是0~31)，所以最高有效位是31 - leading_zeros。对于其他底数，我们也可以使用牛顿迭代法:

pub fn log_newton(x: f64, base: f64, epsilon: f64) -> f64 {
    // 下面省略数据校验
    let mut y = (x.ln() / base.ln()).max(0.0); // 初始猜测
    loop {
        let next_y = y - (base.powf(y) - x) / (base.powf(y) * base.ln());
        if (next_y - y).abs() < epsilon {
            return next_y;
        }
        y = next_y;
    }
}

牛顿迭代法 是一种用于近似求解方程 $f (x) = 0$ 的根的高效数值方法。其主要通过切线逼近逐步修正解的近似值。从一个初始猜测值 $x_{0}$ 开始。用当前点 $(x_{n}, f (x_{n}))$ 的切线（导数）更新 $x_{n + 1}$ : $x_{n + 1} = x_{n} - \frac{f ( x _{n} )}{f ^{'} ( x _{n} )}$ 重复迭代，直到 $∣ x_{n + 1} - x_{n} ∣$ 小于预设精度 $ϵ$ ⁴。

利用std中相关方法可以直接进行对数运算:

// log
let five = 5.0f32;
// log5(5) - 1 == 0
let abs_difference = (five.log(5.0) - 1.0).abs();

// log2
let two = 2.0f32;
// log2(2) - 1 == 0
let abs_difference = (two.log2() - 1.0).abs();

// log10
let ten = 10.0f64;
// log10(10) - 1 == 0
let abs_difference = (ten.log10() - 1.0).abs();

// ln
let one = 1.0_f64;
// e^1
let e = one.exp();
// ln(e) - 1 == 0
let abs_difference = (e.ln() - 1.0).abs();

练习与回答

试证明一个整数的二进制表示中，最高有效位(MSB)的位置即为其以2为底的对数。

证明

命题：对于正整数 $n$ ，其二进制最高有效位的位置 $k$ 满足: $k = ⌊ lo g_{2} n ⌋$

证明：

设 $n$ 的二进制表示为: $n = b_{k} \cdot 2^{k} + b_{k - 1} \cdot 2^{k - 1} + \dots + b_{0} \cdot 2^{0} (b_{k} = 1)$

因为 $b_{k} = 1$ ，所以: $2^{k} \leq n \leq 2^{k + 1} - 1 < 2^{k + 1}$

对不等式取 $lo g_{2}$ : $k \leq lo g_{2} n < k + 1$

因此: $k = ⌊ lo g_{2} n ⌋$

见集合。 $N^{+}$ 有时也用 $Z^{+}$ 。 ↩
$110 1_{2}$ 中的 $_{2}$ 表示二进制形式，同理 $_{16}$ 是十六进制。 ↩
前导零(Leading Zeros) 是指一个数的二进制表示中，从最高位开始连续出现的零，直到遇到第一个1为止。 ↩
$ϵ$ (epsilon) 是希腊字母表的第5个字母。表示任意小的正数，用于量化“无限接近”的概念。计算机科学中向如上迭代算法中也可表示停止阈值，一般用常量(如const EPS = 0.000001)。 ↩

Keyboard shortcuts

算法学习