整数乘法为什么仍未找到理论极限
整数乘法为什么仍未找到理论极限
整数乘法看起来是最基础的运算之一, 但在算法理论中仍有一个没有解决的问题:
两个长度为 $n$ 的大整数, 最少需要多少计算量才能完成乘法?
目前已知的理论算法可以达到:
\[O(n\log n)\]但数学家尚未证明, 这已经是整数乘法能够达到的最快速度.
1. 什么是算法复杂度
算法复杂度描述的是:
当输入规模增大时, 算法的工作量以什么速度增长.
对于整数乘法, $n$ 通常表示整数的位数.
例如:
\[1234\times5678\]两个整数都是 4 位数, 因此:
\[n=4\]复杂度不是某一次计算实际花费了多少毫秒, 也不是精确的指令数量.
它主要用于比较:
当数字从 4 位增长到 1000 位、10000 位时, 不同算法的工作量增长得有多快.
2. 普通竖式乘法
普通竖式乘法需要让第一个数字的每一位, 与第二个数字的每一位相乘.
对于:
\[1234\times5678\]需要进行以下个位乘法:
1
2
3
4
1×5 1×6 1×7 1×8
2×5 2×6 2×7 2×8
3×5 3×6 3×7 3×8
4×5 4×6 4×7 4×8
一共需要:
\[4\times4=16\]次个位乘法.
如果两个数字都是 $n$ 位, 则个位乘法数量约为:
\[n\times n=n^2\]因此, 普通竖式乘法的复杂度为:
\[O(n^2)\]数字位数扩大 2 倍时, 主要工作量大约扩大 4 倍.
3. Karatsuba 算法的基本思路
Karatsuba 算法的核心思路是:
使用较便宜的加法和减法, 减少较昂贵的大整数乘法次数.
仍以:
\[1234\times5678\]为例.
将两个数字从中间拆开:
\[1234=12\times100+34\] \[5678=56\times100+78\]令:
\[a=12,\quad b=34,\quad c=56,\quad d=78\]原乘法可以写成:
\[(a\times100+b)(c\times100+d)\]直接展开:
\[ac\times10000+(ad+bc)\times100+bd\]普通计算需要完成 4 个乘法:
\[ac,\quad ad,\quad bc,\quad bd\]Karatsuba 使用下面的关系:
\[ad+bc=(a+b)(c+d)-ac-bd\]因此只需要计算 3 个乘法:
\[ac=12\times56\] \[bd=34\times78\] \[(a+b)(c+d)=46\times134\]具体结果为:
\[ac=672\] \[bd=2652\] \[(a+b)(c+d)=6164\]中间部分为:
\[ad+bc=6164-672-2652=2840\]最后重新组合:
\[1234\times5678 = 672\times10000 + 2840\times100 + 2652\]得到:
\[1234\times5678=7006652\]Karatsuba 并没有消除乘法, 而是把 4 个较小乘法减少成了 3 个.
4. 什么叫递归拆分
上面的 3 个乘法仍然可能很大:
\[12\times56\] \[34\times78\] \[46\times134\]Karatsuba 不一定直接计算它们, 而是继续使用同样的方法拆分.
例如:
\[12\times56\]可以继续写成:
\[12=1\times10+2\] \[56=5\times10+6\]此时只需要计算:
\[1\times5\] \[2\times6\] \[(1+2)(5+6)\]然后再将结果组合起来.
这种在算法内部再次调用相同算法的方式, 称为递归.
其结构可以近似理解为:
1
2
3
4
5
6
7
8
9
10
11
12
13
4 位 × 4 位
├── 约一半长度的乘法
│ ├── 更小的乘法
│ ├── 更小的乘法
│ └── 更小的乘法
├── 约一半长度的乘法
│ ├── 更小的乘法
│ ├── 更小的乘法
│ └── 更小的乘法
└── 约一半长度的乘法
├── 更小的乘法
├── 更小的乘法
└── 更小的乘法
普通乘法每拆分一层, 会产生 4 个主要子乘法.
Karatsuba 每拆分一层, 只产生 3 个主要子乘法.
递归层数越多, 两者之间的差距越明显.
5. Karatsuba 的复杂度
忽略进位、数字长度不完全一致等细节, Karatsuba 的计算过程可以近似写成:
\[T(n)=3T\left(\frac{n}{2}\right)+O(n)\]含义是:
- 将两个 $n$ 位整数拆成长度约为 $\frac{n}{2}$ 的部分.
- 产生 3 个规模约为原来一半的子乘法.
- 额外执行一些线性数量的加法、减法和结果组合.
假设:
\[n=2^k\]每拆分一次, 数字长度减半.
从 $n$ 位拆到 1 位, 需要的层数为:
\[k=\log_2 n\]每一层的子问题数量乘以 3, 所以最底层的子问题数量约为:
\[3^k\]代入:
\[k=\log_2 n\]得到:
\[3^{\log_2 n}\]这个式子可以改写为:
\[n^{\log_2 3}\]而:
\[\log_2 3\approx1.585\]因此:
\[3^{\log_2 n} = n^{\log_2 3} \approx n^{1.585}\]所以 Karatsuba 算法的复杂度为:
\[O(n^{1.585})\]更准确地写是:
\[O(n^{\log_2 3})\]6. $\log_2 3$ 是什么意思
表达式:
\[\log_2 3\]读作:
以 2 为底, 3 的对数.
它表示:
2 的多少次方等于 3?
也就是求 $x$:
\[2^x=3\]因为:
\[2^1=2\] \[2^2=4\]所以:
\[1<\log_2 3<2\]其近似值为:
\[\log_2 3\approx1.585\]即:
\[2^{1.585}\approx3\]对数可以理解为指数运算的逆运算:
\[2^x=3 \Longleftrightarrow x=\log_2 3\]7. 为什么 $3^{\log_2 n}=n^{\log_2 3}$
根据对数定义:
\[3=2^{\log_2 3}\]因此:
\[3^{\log_2 n} = \left(2^{\log_2 3}\right)^{\log_2 n}\]使用幂的乘方公式:
\[(a^x)^y=a^{xy}\]得到:
\[3^{\log_2 n} = 2^{(\log_2 3)(\log_2 n)}\]乘法可以交换顺序:
\[(\log_2 3)(\log_2 n) = (\log_2 n)(\log_2 3)\]因此:
\[3^{\log_2 n} = 2^{(\log_2 n)(\log_2 3)}\]重新组合:
\[3^{\log_2 n} = \left(2^{\log_2 n}\right)^{\log_2 3}\]由于:
\[2^{\log_2 n}=n\]所以:
\[3^{\log_2 n}=n^{\log_2 3}\]这通常不是需要单独记忆的定理, 而是由对数定义和指数运算性质推导出的结果.
8. 什么是 $n\log n$
表达式:
\[n\log n\]表示:
\[n\times\log n\]它不是:
\[n^{\log n}\]例如, 将算法中的 $\log n$ 暂时理解为 $\log_2 n$.
当:
\[n=8\]有:
\[\log_2 8=3\]所以当 $n=8$ 时:
\[n\log_2 n = 8\times3 = 24\]可以近似理解为:
- 有 8 个数据需要处理.
- 算法存在 3 个处理层级.
- 总工作量约为 $8\times3$.
例如, 将 8 不断除以 2:
1
2
3
4
8
4
2
1
需要进行 3 次减半, 因为:
\[2^3=8\]所以:
\[\log_2 8=3\]9. 为什么 $\log n$ 不写底数
严格来说, 对数应当写明底数:
\[\log_2 n\] \[\log_{10}n\] \[\ln n\]但在算法复杂度中, 经常统一写成:
\[\log n\]原因是不同固定底数的对数只相差一个固定倍数.
根据换底公式:
\[\log_a n = \frac{\log_b n}{\log_b a}\]例如:
\[\log_2 n = \frac{\log_{10}n}{\log_{10}2}\]其中:
\[\frac{1}{\log_{10}2}\]是一个固定常数, 约等于:
\[3.322\]所以:
\[\log_2 n \approx 3.322\log_{10}n\]两种写法只相差一个固定倍数.
大 $O$ 复杂度通常忽略固定倍数, 因此:
\[O(n\log_2 n)\] \[O(n\log_{10}n)\] \[O(n\ln n)\]会统一写成:
\[O(n\log n)\]在计算机算法中, 如果没有特别说明, 可以暂时将 $\log n$ 理解为:
\[\log_2 n\]10. $n\log n$ 的增长速度
下面比较 $n$、$n\log_2 n$ 和 $n^2$:
| $n$ | $n$ | $n\log_2 n$ | $n^2$ |
|---|---|---|---|
| 8 | 8 | 24 | 64 |
| 16 | 16 | 64 | 256 |
| 32 | 32 | 160 | 1024 |
| 64 | 64 | 384 | 4096 |
| 1024 | 1024 | 10240 | 1048576 |
可以看到:
\[n<n\log n<n^2\]因此, $O(n\log n)$ 的增长速度:
- 比 $O(n)$ 快.
- 比 $O(n^2)$ 慢得多.
这里的数值只是用来说明增长趋势, 不代表算法实际执行的精确指令数量.
11. 当前最快的整数乘法算法
整数乘法算法的发展大致如下:
| 算法 | 理论复杂度 |
|---|---|
| 普通竖式乘法 | $O(n^2)$ |
| Karatsuba | $O(n^{1.585})$ |
| 更高级的分治和快速变换算法 | 更低 |
| 当前最快的理论结果 | $O(n\log n)$ |
2019 年, David Harvey 和 Joris van der Hoeven 给出了复杂度为:
\[O(n\log n)\]的整数乘法算法.
不过, 这个算法的实现成本和常数开销极高. 它只有在输入数字大到现实中几乎无法处理时, 才可能表现出理论优势.
因此它目前主要具有理论价值.
实际软件通常会根据整数长度, 在以下算法之间切换:
- 普通竖式乘法.
- Karatsuba.
- Toom-Cook.
- 基于快速傅里叶变换的乘法算法.
算法复杂度更低, 不代表在所有输入规模下都更快.
12. 尚未解决的问题
目前数学家已经证明:
\[O(n\log n)\]的整数乘法算法确实存在.
但是还没有证明:
不可能存在比 $O(n\log n)$ 更快的整数乘法算法.
因此, 当前真正没有解决的问题是:
\[O(n\log n)\]是否已经是整数乘法的理论极限.
总结
普通竖式乘法需要约:
\[n^2\]次基础乘法, 因此复杂度为:
\[O(n^2)\]Karatsuba 每次将问题规模减半, 同时产生 3 个子问题, 所以工作量约为:
\[3^{\log_2 n}\]它等价于:
\[n^{\log_2 3}\]由于:
\[\log_2 3\approx1.585\]因此 Karatsuba 的复杂度为:
\[O(n^{1.585})\]更先进的理论算法可以达到:
\[O(n\log n)\]其中:
\[n\log n\]表示:
\[n\times\log n\]算法复杂度中通常省略对数底数, 因为不同固定底数只会带来固定倍数差异, 不会改变复杂度等级.
参考资料
Mathematicians Still Don’t Know the Fastest Way to Multiply Numbers | Scientific American