图姆-库克算法 图姆库克算法英語ToomCook有时也被称为Toom算法由安德鲁图姆命名他提出了这种算法的基本原理而斯蒂芬库克则最先用简洁的形式描述并改进了这种算法将其作为大整数的乘法算法 图姆库克算法的原理是对于给定的两个大整数 a displaystyle a 和 b displaystyle b 将 a displaystyle a 和 b displaystyle b 分成 k displaystyle k 个较小的部分每个部分的长度为 l displaystyle l 并对这些部分执行运算随着 k displaystyle k 的增长可以组合许多乘法子运算从而降低算法的整体复杂度然后再次使用图姆库克算法递归计算乘法子运算依此类推Toom和图姆库克两个术语有时会被错误的混用但事实上Toom只是图姆库克算法在 k   displaystyle k 时的特例 Toom将次乘法降低至仅需次使其在 Θ  n log      log       Θ  n   displaystyle Theta nloglogapprox Theta n 的时间里运行通常Toom k displaystyle k 的时间复杂度为 Θ  c  k  n e  displaystyle Theta ckne 其中 e  log    k     log   k  displaystyle elogklogk  n e displaystyle ne 是在乘法子运算上花费的时间 c displaystyle c 则是花费在对小常数进行的加法和乘法运算上的时间著名的Karatsuba算法实际上是图姆库克算法的特例在Karatsuba算法中原始乘数被拆分成两个较小的数而原本的次乘法运算缩减为次使之在 Θ  n log      log       Θ  n   displaystyle Theta nloglogapprox Theta n 的时间内完成运算Toom等价于普通的长乘法具有 Θ  n   displaystyle Theta n 的复杂度 尽管可以通过增加 k displaystyle k 来使指数 e displaystyle e 任意接近但函数 c displaystyle c 增长速度非常快混合级别图姆库克算法的增长率直到年仍然是一个广为研究的开放性问题根据高德纳所描述算法的一种实现其复杂度可降低至 Θ  n   log  n log  n  displaystyle Theta nsqrt log nlog n  由于工作时的开销当乘数包括较小的数时图姆库克算法会比长乘法更慢因此它适用于中等规模的乘法对于更大规模的数据则有渐进更快的史恩哈格施特拉森算法复杂度为 Θ  n log  n log  log  n  displaystyle Theta nlog nlog log n  这一算法由安德鲁图姆年首次描述并在斯蒂芬库克年的博士学位论文中得到渐进等效的改进