图姆-库克算法
维基百科,自由的 encyclopedia
图姆-库克算法(英语:Toom–Cook),有时也被称为Toom-3算法,由安德鲁·图姆命名,他提出了这种算法的基本原理,而斯蒂芬·库克则最先用简洁的形式描述并改进了这种算法,将其作为大整数的乘法算法。
![]() | 此条目需要精通或熟悉数学的编者参与及协助编辑。 (2020年12月31日) |
图姆-库克算法的原理是:对于给定的两个大整数和
,将
和
分成
个较小的部分,每个部分的长度为
,并对这些部分执行运算。随着
的增长,可以组合许多乘法子运算,从而降低算法的整体复杂度,然后再次使用图姆-库克算法递归计算乘法子运算,依此类推。Toom-3和图姆-库克两个术语有时会被错误的混用,但事实上Toom-3只是图姆-库克算法在
时的特例。
Toom-3将9次乘法降低至仅需5次,使其在的时间里运行。通常,Toom-
的时间复杂度为
,其中
。
是在乘法子运算上花费的时间,
则是花费在对小常数进行的加法和乘法运算上的时间[1]。著名的Karatsuba算法实际上是图姆-库克算法的特例,在Karatsuba算法中,原始乘数被拆分成两个较小的数,而原本的4次乘法运算缩减为3次,使之在
的时间内完成运算。Toom-1等价于普通的长乘法,具有
的复杂度。
尽管可以通过增加来使指数
任意接近1,但函数
增长速度非常快[1][2]。混合级别图姆-库克算法的增长率直到2005年仍然是一个广为研究的开放性问题[3]。根据高德纳所描述算法的一种实现,其复杂度可降低至
[4]。
由于工作时的开销,当乘数包括较小的数时,图姆-库克算法会比长乘法更慢,因此它适用于中等规模的乘法。对于更大规模的数据,则有渐进更快的史恩哈格·施特拉森算法(复杂度为)。
这一算法由安德鲁·图姆1963年首次描述,并在斯蒂芬·库克1966年的博士学位论文中得到渐进等效的改进[5]。