algorithm - Karatsuba 乘法的基本情况

Question

只是想知道为什么选择 Karatsuba 乘法的基本情况(此处显示:http://www.sanfoundry.com/java-program-karatsuba-multiplication-algorithm/)是“N<= 10”？我发现“N<= 4, 3, 2 ,1 ”不会给我正确的结果。谁能解释一下？

Answer 1

Karatsuba 的算法可以正确处理任何“足够大”的基本情况，其中“足够大”意味着“足够大，以至于当它被分成更小的子问题时，这些子问题确实更小并产生正确的答案。”从这个意义上讲，Karatsuba 没有“一个”基本案例，而是基本案例可能是什么样子的一般规则。

老实说，您链接的代码似乎不是该算法的非常合理的实现。它适用于 long，它已经可以在任何合理的系统上以 O(1) 的时间相乘，并且它们的基本情况是当数字小于 10¹⁰，这意味着对于 64 位数字，递归总是在一步之后终止。更好的实现可能会使用类似 BigInteger 类型的东西，它可以支持任意精度乘法。在这一点上，选择最佳的基本情况是性能调整的问题。使基本情况的数字太小，并且处理较小数字的递归将比仅进行简单的乘法花费更多的时间。使基数过高，您将开始看到速度变慢，因为递归步骤可以更好地处理案例，而不是使用朴素的乘法。