Karatsuba 乘法的基本情况
Base case for Karatsuba Multiplication
只是想知道为什么选择 Karatsuba 乘法的基本情况（此处显示：http://www.sanfoundry.com/java-program-karatsuba-multiplication-algorithm/）是 "N<= 10"？我发现 "N<= 4, 3, 2 ,1 " 不会给我正确的结果。谁能解释一下？
少于 10 位的数字可以自然相乘 (x*y)，因为结果总是适合带符号的 64 位整数。
虽然使用 long 数据类型没有多大意义，因为大多数不会溢出的数字组合只会在本机进行评估。您将不得不更改为 BitInteger 或类似的东西，并使用更大的数字来从算法中获得任何收益。
至于为什么下限 N 失败，我不确定。该算法必须能够将两个数字分成两个大小相似的部分。我猜它在某些情况下以零或负数结尾。
Karatsuba 的算法将正确处理任何 "sufficiently large" 基本情况，其中 "sufficiently large" 表示 "large enough that when it's divided into smaller subproblems, those subproblems are indeed smaller and produce the right answer." 从这个意义上说，Karatsuba 没有 "a" 基本情况基本情况的一般规则。
老实说，您链接的代码似乎不是该算法的非常合理的实现。它适用于 longs，它已经可以在任何合理的系统上以 O(1) 时间相乘，并且它们的基本情况是当数字小于 1010[=17= 时停止]，这意味着对于 64 位数字，递归总是在一步之后终止。更好的实现可能会使用类似 BigInteger 类型的东西，它可以支持任意精度乘法。在这一点上，选择最佳的基本情况是性能调整的问题。使基本情况的数字太小，并且处理较小数字的递归将比仅进行简单的乘法花费更多的时间。将基数设置得太高，您将开始看到速度变慢，因为递归步骤可以更好地处理案例，而不是使用朴素的乘法。
如果您在 post 中包含了源代码，您可能会更快地得到切中要害的答案。
如果你使用 BigInteger.divideAndRemainder(dividend, divisor) 之类的东西来 "split" 你的数字，你就不会 运行 编写像
这样的东西的风险
long d = y / m;
long c = y - (d * N);
（使用与除数不同的乘数）。
请注意，两个 10 数字的乘积并不总是适合 Java 的 long.
只是想知道为什么选择 Karatsuba 乘法的基本情况（此处显示：http://www.sanfoundry.com/java-program-karatsuba-multiplication-algorithm/）是 "N<= 10"？我发现 "N<= 4, 3, 2 ,1 " 不会给我正确的结果。谁能解释一下？
少于 10 位的数字可以自然相乘 (x*y)，因为结果总是适合带符号的 64 位整数。
虽然使用 long 数据类型没有多大意义，因为大多数不会溢出的数字组合只会在本机进行评估。您将不得不更改为 BitInteger 或类似的东西，并使用更大的数字来从算法中获得任何收益。
至于为什么下限 N 失败，我不确定。该算法必须能够将两个数字分成两个大小相似的部分。我猜它在某些情况下以零或负数结尾。
Karatsuba 的算法将正确处理任何 "sufficiently large" 基本情况，其中 "sufficiently large" 表示 "large enough that when it's divided into smaller subproblems, those subproblems are indeed smaller and produce the right answer." 从这个意义上说，Karatsuba 没有 "a" 基本情况基本情况的一般规则。
老实说，您链接的代码似乎不是该算法的非常合理的实现。它适用于 longs，它已经可以在任何合理的系统上以 O(1) 时间相乘，并且它们的基本情况是当数字小于 1010[=17= 时停止]，这意味着对于 64 位数字，递归总是在一步之后终止。更好的实现可能会使用类似 BigInteger 类型的东西，它可以支持任意精度乘法。在这一点上，选择最佳的基本情况是性能调整的问题。使基本情况的数字太小，并且处理较小数字的递归将比仅进行简单的乘法花费更多的时间。将基数设置得太高，您将开始看到速度变慢，因为递归步骤可以更好地处理案例，而不是使用朴素的乘法。
如果您在 post 中包含了源代码，您可能会更快地得到切中要害的答案。
如果你使用 BigInteger.divideAndRemainder(dividend, divisor) 之类的东西来 "split" 你的数字，你就不会 运行 编写像
long d = y / m;
long c = y - (d * N);
（使用与除数不同的乘数）。
请注意，两个 10 数字的乘积并不总是适合 Java 的 long.