问题标签 [karatsuba]

几件事：

• 我是一名大学生
• 这不是作业问题（我很好奇 bignum 库是如何工作的）
• 这里所有的代码片段都可以用 gcc -lgmp 编译

这是我的实现，它不断返回错误的答案。我尝试过使用 gdb 并使用 GMP 检查单个操作并标记代码中哪些操作肯定失败，但我还没有设法具体找到问题所在。

除此之外，我无法确定问题出在哪里。

老实说，最糟糕的部分是没有中间值的测试向量。除了维基百科页面示例中的那些（我似乎通过了），我找不到任何东西。

u256是一个 8 的数组uint64_t。我只使用这些整数的低 32 位来进行掩蔽并更容易携带。这个想法是做 Karatsuba 乘法基数 2 ³²。

其余的代码可以在这里找到。

任何帮助，将不胜感激。

编辑：

错误示例：

乘以 2 应该返回

16439926136035242788212517705012640494860769275971090459163708006828967815008

相反，它返回

38696864898835518778416

可以通过编译此代码来运行该特定测试：here

使用 gcc 和 -lgmp

ceil被定义为：

使用这个测试代码，它可以更深入地检查一些东西，我相信我将问题缩小了一些。

它发生在 的m=4乘积上z0 = low1 * low2。相乘的两个值是100000000000和100000000000，预期的结果是10000000000000000000000最终结果是1478053504202008644。运行上面的测试代码将重现这一点。我认为这意味着我的 karatsuba 实现被简单地破坏了，因为组件没有抛出任何错误，而且它在 m=2 乘法上特别失败。我正在检查 m=1 乘法，它们看起来很好。

我正在解决SPOJ 上的FAST MULTIPLICATION。我的解决方案如下所示：

此代码在编码块 IDE 以及其他 IDE 上给出正确的输出。但是这个解决方案在 SPOJ 上被标记为错误的。谁能告诉我我做错了什么？

如果任何一个数字的长度都是偶数，我下面的代码似乎运行良好，但如果两个数字的长度都是奇数（如图片中所示），它会输出错误的结果。我不知道哪里出了问题或如何解决它。

我已经在 Python 中实现了 Karatsuba 乘法。

代码和伪代码如下：

当我对非常大的数字进行乘法运算时，我的代码失败了。

这是一个例子：

我无法找到我的代码到底有什么问题。我已经根据提到的伪代码对所有内容进行了编码。

你能帮我么？

所以我目前在 python 中实现 Karatsuba 的算法，我遇到了一个非常奇怪的问题。我将提供两组代码，我相信它们在理论上都做同样的事情，但提供不同的答案（一个对，一个错）。第一组代码：

第二组代码：

在第一组中，我通过了 n2，其中 n2 = 32，因为 x 和 y 有 64 位。在这种情况下，我得到了 x 和 y 乘积的正确答案。但是，在第二组代码中，我手动找到位数，然后使用整数除法将其除以 2，这也应该给出 32，但给了我错误的答案。任何帮助，将不胜感激。

我正在尝试在这里进行 Karatsuba 乘法。下面的代码适用于两位数的数字（例如 78 * 34），但对于数字大于 2 的数字（例如 5678 * 1234）给出错误的结果。我附上了调试日志。在某一点之后，计算是错误的。有人可以看看并告诉我我对算法的理解是否不正确？

调试日志：

得到2652的结果后，接下来的计算是错误的。

我了解了 Karatsuba 算法，它允许我使用分治法将非常大的数字相乘。

这是我的代码。我编写了一个返回数字长度的函数，然后编写了乘法函数，并使用了该方法进行了 4 次递归调用。

问题是，如果我用一些长度大于 10 的数字调用函数 multiply() ，那么我会收到错误分段错误。问题出在哪里？

我试图快速实现 Karatsuba 乘法。我写了下面的代码，对于一些较小的数字它工作得很好，但是随着数字变大，这个代码无法给出正确的答案。我已经以各种可能的方式进行了调试，但找不到错误。算法方面，我认为我确实正确地编写了代码。并且代码对于较小的数字运行良好。但是对于更大的数字，最终答案是错误的。如果有人可以纠正我所犯的错误，请帮助我

我需要将 karatsuba 算法实现为我的家庭作业的 ac 代码，我进行了研究并提出了以下代码：

ust(x, n) 是获得数 x 幂的函数：

uzunluk(x) 获取给定输入中的位数：

问题是这段代码什么也没打印：D如果有人能发现我犯的错误，我会很高兴。

我尝试了两种方法。第一个是用 0 填充 X 和 Y，使它们的长度相等，例如：

X = 123 , Y = 45678

变成：

X = 000123，Y = 045678

a = 0 , b = 123 , c = 45 , d = 678

但是这个实现的问题是输入时：

X = 100 和 Y = 14

变成：

X = 0100 , Y = 0014

a = 1 , b = 0 , c = 0 , d = 14

交流 = 0

bd = 0

广告 + 公元前 = 14

那么：10^4(0) + 10^2(14) + 0

注意 10^2(14) 正是我们开始的问题，这将导致无限递归

我尝试的第二个解决方案是将 0 填充到右侧，然后将最终答案除以 10^（添加的 0 的数量），但这也会在某些情况下导致无限递归。

我应该怎么办？