Karatsuba乘数

Question

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

Answer 1

是的，你必须使用相同的方法。

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