iteration - 如何有效且不平凡地实现迭代 Karatsuba？

Question

对于迭代 Karatsuba 是否有任何有效的 C/C++ 实现或算法描述，不使用堆栈/队列来模拟递归 Karatsuba 中的函数堆栈？

假设 F x G = (F_1 + F_2 x^n) x (G_1 + G_2 x^n)，其中 F 和 G 是 (2n-2) 次多项式。

我的直觉是记住当前两个操作数 F_i 和 G_i 的大小和索引。迭代 Karatsuba 从最小操作数的乘法开始。一旦索引为偶数，计算 ((F_1 + F_2) x (G_1 + G_2))，将其与 (F_1 x G_1) 和 (F_2 x G_2) 合并，“大小”加倍，“索引”减半。

问题是（（F_1 + F_2）x（G_1 + G_2））的计算需要另一个（大小，索引）。我想直接将 (F_1 + F_2)/(G_1 + G_2)$ 附加到 F/G 数组的末尾。在那种情况下，计算完成后如何从旧的（大小，索引）中扣除新的（大小，索引）？

标签： iterationkaratsuba