问题标签 [karatsuba]

我正在为在线课程在 Scala（我的选择）中实现Karatsuba 乘法。考虑到该算法旨在将大数相乘，我选择了BigInt由 Java BigInteger支持的类型。我想有效地实现该算法，该算法使用以 10 为底的算法从 Wikipedia 复制如下：

鉴于它BigInteger在内部表示为int[]，如果我可以根据m2进行计算int[]，我可以使用位移来提取数字的下半部分和上半部分。同样，最后一步也可以通过位移来实现。

然而，说起来容易做起来难，因为我似乎无法理解逻辑。例如，如果最大数为999，则二进制表示为1111100111，下半部分为99 = 1100011，上半部分为9 = 1001。如何获得上述拆分？

注意：有一个现有问题显示了如何在 上使用算术BigInteger而不是位移来实现。因此，我的问题不是重复的。

我正在尝试使用 Haskell 中的分而治之方法编写 Karatsuba 算法。我用合并排序算法做到了，但在这里无法弄清楚，在这一点上有点尴尬。

我的主要功能如下所示：

我测试它的值1234和5678: dz test end divide combine [1234, 5678,2]。

所以我必须编写,test和end函数。dividecombine

这很简单。我只是检查我想要相乘的两个数字是否至少有 4 位数字。如果不是，我只使用简单的乘法和进位m值。我知道 Karatsuba 对于更大的数字效果更好，但这仅用于测试目的。

有人告诉我这个combine函数应该只做最后的乘法。所以我想它应该得到三个数字作为输入（每个都有它们的m值），然后还做必要的减法（z-x-y），因为我不能在divide.

但这是错误的。我收到一个错误：

我认为这是combine函数参数的问题，但我不知道如何解决。我还认为，如何协同工作可能存在问题，combine因为在之前的一次迭代中，乘法的最终结果是错误的。divide

我正在实现一个 Karatsuba 算法，并且遇到了这个异常。

一些相关代码（如果需要，我可以发布更多）：

从主要：

来自唐叶：

从那里我将 r_ 数组加载到 r[] 以返回到 main。 这是用于加载 A[] 和 B[]的示例输入。我正在使用数组进行多项式乘法，这些值是系数。

我对这个异常不是很熟悉，但据我了解，ArrayIndexOutOfBoundsException: 0意味着当数组边界中不存在该索引时，我正在尝试使用索引 0 访问数组。

我的困惑是，对于 A[] 和 B[]，我验证了输入得到了正确的数字，所以它被初始化并且具有最高程度的值。对于 A_hi 和 B_hi，我初始化了数组，并一一加载值。我用这一行检查了哪些值被加载到 A_hi[] 和 B_hi[] 中：

这导致了这个输出——所以这些值是按照我的意图加载的。

那么我使用未正确初始化的 0 访问哪个数组？或者还有其他我不理解的问题？

这是完整的错误列表

Karatsuba算法的实现，方法只算小数为真，但大答案不正确，有什么问题？

我正在研究一个数字相乘的 Karatsuba 算法的实现，但与大多数使用字符串作为主要数据结构而不是 BigNumbers 或 longs 的实现不同。我已经为这个问题编写了一个递归解决方案，它似乎适用于所有 n < 6，但由于某种原因，它无法适用于大于 6 的奇数 ns，尽管所有基本情况都有效。这是程序的 karatsuba 部分，在调试过程中留下了一些痕迹。这里使用的所有方法都应该按预期工作，我对它们进行了彻底的测试。对于值 factor1 = "180" 和 factor2 = "109"，输出正确的结果。对于值 factor1 = "1111" 和 factor2 = "1111"，输出正确的结果。对于 factor1 = "2348711" 和 factor2 = "8579294" 程序应输出“20150282190034”时输出“20358060808034”。我试过回溯逻辑，但我找不到它到底哪里出错了。如果有人对某些地方可能无法正常工作有任何见解，我们将不胜感激。

我正在尝试在 c 中实现 kartsuba 的算法，我遵循了Wikipedia 上的伪代码，但问题是我并不总是得到正确的结果。

这是实现：

这是slice函数，它用于将一个数字分成 2：

这add是用于添加 2 个数字的函数：

PS：出于好奇，我在许多实现中看到使用 max (size(num1),size(num2)) 而不是 min，这样可以吗？它会改变什么吗？

我想在 python 中实现 Karatsuba 乘法算法。但它不能完全工作。

该代码不适用于大于 999 的 x 或 y 值。对于低于 1000 的输入，程序显示正确的结果。它还在基本情况下显示正确的结果。

我认为在计算 a、b、c 和 d 时存在一些错误。

我正在尝试在 python 中为两个相同次数的多项式创建一个Karatsuba 算法，它应该返回结果系数的数组。

我在cMid = karatsuba(tA, tB). 有人有意见吗？我会非常感激！

这段代码没有通过所有的测试用例，有人可以帮忙吗？我只通过了直截了当的测试，然后它就失去了精度。

对于第一个测试用例，'test_easy_cases' 都通过了其他两种情况，我得到错误，例如AssertionError: 6592652 != 7006652

我没有明白我的代码有什么问题。我应该如何解决 Karatsuba 乘法中的递归错误？

错误信息 -