我将两个 n 位正整数与一个 n 位 Karatsuba 乘数相乘。但大多数时候，子问题仍然需要处理两个 n 位数。那么我是否应该再次递归地使用 n 位 Karatsuba 算法来解决子问题？这种方法有冗余吗？它会以任何方式影响计算时间 (O(n^1.5)) 吗？
最佳答案
是的，您必须使用相同的方法。对于足够小的数字，仍然使用其他一些方法，因为添加数字的开销可能太大。
但这不是真的，您需要再次乘以 n 位数字，您将需要乘以 n/2 位数字。这就是该方法的重点。
关于algorithm - 唐叶倍增器，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14280798/