algorithm - Karatsuba 乘法的基本案例

Question

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

Answer 1

如果您在帖子中包含源代码，您可能会很快得到一个中肯的答案。
如果您使用诸如BigInteger.divideAndRemainder(dividend, divisor)“拆分”您的数字之类的东西，您就不会冒险编写类似的代码

long d = y / m;
long c = y - (d * N);

（使用与除数不同的乘数）。
请注意，10两位数的乘积并不总是适合 Java 的long.

Answer 2

少于 10 位的数字可以本地相乘 ( x*y)，因为结果总是适合有符号的 64 位整数。

但是，使用long数据类型并没有多大意义，因为大多数不会溢出的数字组合只会被本地评估。您必须更改为BitInteger或类似的东西，并使用更大的数字才能从算法中获得任何收益。

至于为什么它的下限失败N，我不确定。该算法必须能够将两个数字分成两个大小相似的部分。我猜在某些情况下它会以零或负数结束。

Answer 3

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

老实说，您链接的代码似乎不是算法的非常合理的实现。它与longs 一起工作，在任何合理的系统上，它已经可以在 O(1) 时间内相乘，并且它们的基本情况是在数字小于 10 ¹⁰时停止，这意味着对于 64 位数字，递归总是在 a 之后终止一小步。更好的实现可能会使用类似BigInteger可以支持任意精度乘法的类型。在这一点上，选择最佳基本情况是性能调整的问题。使基本情况的数字数量太小，并且处理较小数字的递归将比仅仅做一个简单的乘法花费更多的时间。将基数设置得太高，您将开始看到减速，因为递归步骤可以更好地处理案例，而不是使用幼稚的乘法来获得支出。