c - 具有 O(n) 内存而不是 O(n log n) 的 Karatsuba 算法

Question

已知具有时间复杂度 ~O(n^log2(3)) 的递归 Karatsuba 乘法算法比具有复杂度 O(n^2) 的简单乘法算法更快).
但是，它比“schoolgrade”算法使用更多的内存空间 - O(n log(n)) 而不是 O(n) 内存，这对于 Controller 或具有少量内存的非常小的计算机。

So, my question is:
Is there a way to achieve an O(n) memory space in the karatsuba algorithm?

PS:我知道使用 FFT 可以实现更快的速度 O(n log(n)) 和更好的内存使用 O(n )，但我只是对 Karatsuba 感到好奇。

Answer 1

Karatsuba 的算法只需要 O(n) 的空间。

(A0 2^n + B0)(A1 2^n + B1)
= A0 A1 2^(2n) + B0 B1 + ((A0+B0)(A1+B1) - A0 A1 - B0 B1)2^n

这是一个粗略的归纳论证。归纳地，假设使用 Karatsuba 算法乘以 n 位数字只需要 cn 空间。 2n位数字相乘，我们可以在cn空间乘A0 A1，然后将答案保存在2n空间，然后在cn空间乘B0 B1，然后将答案保存在2n空间，然后乘( A0+B0)(A1+B1) 在 cn 空间。此时我们最多使用 (c+4)n 空间。然后我们执行减法并将答案记录在 4n 空间中。峰值空间使用量为 (c+4)n，小于 max(c,4)(2n) 空间。所以，只要c>4，如果n位数字相乘需要cn空间，那么2n位数字相乘需要c(2n)空间。这是不精确的，因为 (A0+B0) 和 (A1+B1) 可能有 n+1 个数字而不是 n。因此，严格的归纳论证更加困惑，但可以遵循相同的基本模式来完成。

题目前提错误。 Karatsuba 乘法只需要 O(n) 空间，而不是 Omega(n log n)。某些实现可能需要更多空间，不一定限于 O(n log n)，例如并行计算。

事实上，可以在O(log n) extra bits 中进行Karatsuba 乘法运算超出答案。