algorithm - 唐叶乘数

Question

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

Answer 1

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

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