algorithm - 唐叶倍增器

Question

我将两个 n 位正整数与一个 n 位 Karatsuba 乘数相乘。但大多数时候，子问题仍然需要处理两个 n 位数。那么我是否应该再次递归地使用 n 位 Karatsuba 算法来解决子问题？这种方法有冗余吗？它会以任何方式影响计算时间 (O(n^1.5)) 吗？

Answer 1

是的，您必须使用相同的方法。对于足够小的数字，仍然使用其他一些方法，因为添加数字的开销可能太大。

但这不是真的，您需要再次乘以 n 位数字，您将需要乘以 n/2 位数字。这就是该方法的重点。