动机
把两个数各拆成高位和低位两半,似乎需要四次规模更小的乘法:高位乘高位、高位乘低位、低位乘高位、低位乘低位。Karatsuba 的观察是:只需多做一次乘法,就能得到两个交叉乘积之和。递归乘积由四个减为三个,渐近指数因此改变。
这个算术恒等式本身很短,但严谨的复杂度证明必须考虑加法产生的进位,以及输入长度不均匀的情形。我们分析一个刻意补零的实现,使其递归对每个数位长度都有定义,并且其运算次数不依赖于高位数字是否恰好为零。
定义
数位拆分与三个乘积
定义 1.6.1
(拆分与三个乘积)
固定基数 。考虑用至多 个 进制数位表示的非负整数 ,必要时在高位补零。当 大于某个固定的基础情形阈值时,令 ,并写成
其中 ,且 。定义
展开可得 ,因此
算法只递归地计算 ,再用加法、减法和数位移位恢复乘积。对于非负输入,虽然 由减法得到,它仍然是非负的。有符号整数可以先对绝对值做乘法,再单独恢复符号。
概念视角代数
二次多项式的三次求值
设 。则 , 是首项系数,。二次多项式由三个值确定,而 就是插值一步。乘积为 。
定理
定理 1.6.2
(三乘积恒等式的正确性)
对每个基数 以及按上述方式拆分的每一对非负输入,三个递归乘积加上重组公式所得的结果等于普通的整数乘积 。
定理 1.6.3
(补零后的运算次数)
对下面的实现,固定基数下的数位运算次数为 。特别地,其上界在渐近意义上小于直接小学竖式乘法的 数位运算上界。
最后一个命题比较的是固定基数数位运算模型中两个指定的算法,它并不是对所有可能的乘法算法的下界。
证明思路或证明
正确性与补零
证明
(恒等式为何精确、递归为何终止)
展开 得到 。减去 和 后,剩下两个交叉乘积。代入上面给出的重组恒等式,便还原出 的普通展开。
每一半至多有 位,但像 这样的和可能因进位而需要 位。为了得到简单统一的分析,我们把全部三个递归调用的参数都补零到 位,即使某个参数的有效位数更少。当规模至多为八时使用直接乘法。当 时,子问题规模 严格小于 ,所以递归会终止。
补零不改变被相乘的整数。重组过程使用移位 或 个数位,以及 位量的加法或减法,这些都可以在 次固定基数数位运算内完成。对补零后的规模作归纳,递归调用返回三个精确的乘积,因此该恒等式对每个输入都证明了正确性。
证明透视
一个乘积同时编码两个交叉项
和的乘积包含全部四个两两乘积。去掉已经算出的低位乘低位与高位乘高位两项后,恰好剩下两个交叉项之和,而这正是重组所需要的全部信息。
检查数位长度与进位
每一半都小于 ,所以两半之和小于 。因此,即使基数为二,它也能放进 个 进制数位中。把每个递归参数都补零到这一长度,就使三次调用保持统一。这是对表示长度的上界,并不断言最高位非零。
中间乘积也只有 位。两个至多 位的数之积小于 。在重组中,交叉项的值等于 ,且非负。从 中减去 和 ,可以借助普通的借位传播,在线性多个数位上完成;只要以任意顺序减去这两个已知的非负乘积,就不需要出现负的中间值。
乘以 意味着把数位表示移位 个位置,或者等价地,把它对齐到输出缓冲区中相应的偏移处。这不是再做一次与一般整数的递归乘法。把三个对齐后的贡献相加,所需工作量与它们总表示长度成线性关系,进位按通常的数位加法算法处理。
比较两个递推式
直接的四乘积拆分在理想的等规模分析中具有 形式的递推式,从而得到二次的数位运算量。Karatsuba 把分支因子降为三,于是子问题个数按 增长,而它们的规模大约按 缩小。第 层的线性工作量总和大致按 增长,在 的量级上由最深的几层主导。
精确的取整递推式并不是对每个整数 都恰好等于 。和的操作数可能有进位,补零后的规模为 。把规模平移三个单位,可以得到一个干净的折半不等式,同时避免把真实的实现替换成另一个理想化的递推式。有限的基础情形阈值随后处理最小的那些情形,因为在这些情形中仅凭平移后的表达式并不能描述一个有意义的拆分。
取整规模下的上界
证明
(取整规模下的上界)
令 为补零算法数位工作量的上界。当 时,
对某个固定常数 成立,且规模至多为八时工作量为常数。其中加上的一用来计入可能的进位。定义平移后的规模 。若子问题规模为 ,则
因此,经过 层递归后,每个节点的规模至多为 。第 层至多有 个节点。令 ,则每条路径在深度 处都已到达基础阈值:其规模至多为八。非递归工作量的总和以下式的常数倍为界:
两个几何和都是 。事实上,,且 。常数规模的叶子也被同一个界所涵盖。这就证明了上界,其中已包含取整与进位补零。
几何和的估计
对 ,深度的取法满足 。因此 至多是 的某个常数倍。类似地, 至多是下式的某个常数倍:
各层代价之和分别是公比为 与 的几何级数,因此每个和都与其最后一项相差一个常数因子。对数的取整只改变这个常数。该证明同时计入了与规模成正比的重组工作量,以及每个递归节点的常数贡献。
顺序实现可以在每个递归乘积返回之后重用临时存储。沿着一条活动的递归路径,补零后的规模按平移折半的界递减,所以它们的规模之和为 。每个活动层使用常数个线性大小的缓冲区,于是除输入和输出之外,辅助数位存储为 。若并行地运行三个递归调用,或保留额外的副本,则存储的核算会改变,需要另行分析。
这一补零实现的下界
证明
(补零实现的匹配下界)
对 ,补零算法总是进行三次递归调用,每次的规模为 ,即使某些高位数字为零也是如此。对充分大的 ,令 。深度小于 的每个节点规模至少为 ,因此都不是基础情形。递归树在深度 处至少含有 个节点。
如果每个节点至少执行一次数位运算,这就给出了所指定的补零实现的一个匹配下界。补零的约定很重要:跳过零子乘积的实现,在某些特殊输入上可以做更少的工作。上界依然成立,但这种针对具体输入的下界论证就不能原封不动地适用了。
反例模式
输入之和可能多出一位
在十进制中,两个三位数,例如 与 ,其和 是四位数。若把每个和都当作三位输入,而不设进位或补零规则,则递归规模的论证是不完整的。
指数比较的含义
因为 ,取以二为底的对数得 。因此,随着 增大, 趋于零。这就是所述上界优于标准固定循环小学竖式算法的二次运算次数的含义。对于小输入,递归和临时缓冲区可能带来更大的常数代价,这也是实际实现要使用基础情形的原因之一。
当两个输入都补零到 位且循环遍历每一对数位时,标准的逐位方法要形成 个单独的数位乘积。在固定基数下,每个这样的数位乘积与进位更新的局部代价是有界的;累加移位后的各行,得到 次数位运算。这是对这一特定直接方法的分析,并不是整数乘法的普遍下界。
Karatsuba 基础阈值取八,同样是一种实现上的约定。只要阈值是固定的、足够大的常数,并且当 超过阈值时 ,就会得到相同的渐近指数。阈值的取值只改变有限的常数,以及需要逐一检验的基础情形,而不改变“三个分支与折半规模”之间的几何比较。实际实现可以通过测量来选择阈值,而证明只要求它是一个与输入长度无关的固定常数。
输出至多有 个 进制数位,因为 蕴含 。中间缓冲区可能因补零而含有多余的前导零,但它们的长度仍与 成线性关系。这一关于输出规模的观察支持了上述线性重组与存储的核算,但它本身并不能证明次二次的运行时间。
例题详解
例题 1.6.4
(一个十进制乘法)
在 处拆分 与 :,,,。三个乘积为 ,,。因此 ,重组得到 。
例题 1.6.5
(为什么和的乘积有用)
对 ,两个交叉乘积为 与 。不分别计算它们,而是使用 。恢复出的和为 。
例题 1.6.6
(奇数数位长度)
对 ,拆分使用 个低位数位,以及至多四个高位数位。低位部分与补零后的高位部分之和可能需要六位,所以每个递归调用都安全地补零到 位。这小于九,满足在基础阈值之上继续推进的要求。
例题 1.6.7
(零输入)
若 ,而 是任意非负输入,该算术恒等式返回零。所指定的补零实现仍可能进行全部三次递归调用;其 运算次数描述的是这个实现,而不是检测到零就提前退出的某种优化。
常见错误
常见错误
(只用一个交叉乘积)
中间系数是两个交叉乘积的和。若只用其中一个交叉乘积代替,就会得到错误的乘法。三乘积技巧之所以有效,是因为和的乘积同时包含了两个交叉项。
常见错误
(忽略操作数之和的进位)
进位会使和的操作数比一半多出一位。忽略这一点,可能得到对该实现并不成立的递归界。平移规模不等式明确地处理了这多出的一位。
常见错误
(把指数当成普遍的界)
是补零算法在所述模型下的运算次数。它并不是断言别的算法不能更快地完成乘法,也不是断言对任意精度的值,所有机器级运算的代价都相同。
总结
Karatsuba 乘法用三个乘积加线性重组取代了四个半规模乘积。对和的操作数补零处理了进位,而平移规模的递归树论证控制了取整。对于所指定的始终递归的实现,所得的固定基数数位运算次数为 。
练习
快速检查
(展开 。)
把和的乘积乘开再消项。
解答 · 答案
展开并消去后得到 。
快速检查
(当 时,补零实现所用的递归参数规模是多少?)
先算 ,再加上进位的一位。
解答 · 答案
,所以递归参数规模为六位。
快速检查
(为什么两个 位输入之和可能需要 位?)
想想把最大的数位相加。
解答 · 答案
它们相加可能在最高位产生进位。在十进制中, 就是一个例子。
快速检查
(为什么本章的下界不能自动适用于遇到零操作数就立即返回的实现?)
下界的证明计数的是哪一个对象?
解答 · 答案
该证明计数的是一棵完整的、三分支且补零的递归树。提前检查零的做法对某些输入可以去掉所有这些调用,因此被计数的那棵树在该实现中不一定存在。