颂哈吉-施特拉森算法

颂哈吉-施特拉森算法是一种将两个 n 位整数相乘的算法。该算法基于离散快速傅里叶变换的一个非常快速的变体和有限数环中剩余类和循环算法之间的巧妙切换。

昂哈吉-施特拉森算法以 O ( n ⋅ log ⁡ ( n ) ⋅ log ⁡ ( log ⁡ ( n ) ) )，如果多体积图灵机上的位复杂度，即算法的最大运行时间，被测量为所需的位操作，因为效率测量被选择为输入变量的位长度 n 的函数。与学校已知的运行时间为 O ( n 2 ) 并与 1962 年开发的运行时间为 O ( n log 2 ⁡ ( 3 ) ) 及其改进的变体，具有 O ( n 1 + ε ) 的 Toom-Cook 算法运行时间。

为了将两个整数 a  和 b 相乘，大致使用以下方案：

• 将数字（二进制​​）a和 b  分成适当长度的片段
• 两段序列的快速离散傅立叶变换 (DFT)
• 变换后的片段的分量乘法
• 结果的反变换（逆傅里叶变换）
• 将结果块合并为结果编号

中间步骤要执行的小乘法由昂哈吉-施特拉森算法以递归方式再次执行。

要理解为什么结果是数字 a 和 b 的乘积，

如果你插入 X = 2 ，你会得到数字 a 和 b 的二进制表示。 计算乘积多项式的 c = C ( 2 )

我们确定 A 和 B 的系数元组的傅立叶变换：

a ^ k = ∑ i = 0 2 n − 1 a i ⋅ w i ⋅ k

换句话说，两个多项式在位置 w k  处计算。 如果现在将这些函数值相乘，就得到乘积多项式对应的函数值

C = A ⋅ B 。

要得到多项式 C 本身