问题标签 [karatsuba]

我正在尝试在 Python 上实现 Karatsuba 乘法。输入是长度为 2 的两个整数。它们的长度相同。

运行 mult(1234,5678) 这会产生以下错误：

但是，如果我这样做

所以我在最后一行（即mult(a,c), mult(a,d), mult(b,c), mult(b,d)）中进行了 4 次递归，而不是上面的 3 次（即mult(a,c), mult(a+b, c+d), mult(b,d)）。

然后事实证明没问题。

为什么会这样？我怎么能只用 3 次递归呢？

以下是我尝试实现递归 Karatsuba 算法的 python 代码。我没有得到输入 1234、5678 的正确值。加上值 55,15 我收到错误消息。我为此绊倒了几个小时，请您帮忙。谢谢

我得到的错误是

对于迭代 Karatsuba 是否有任何有效的 C/C++ 实现或算法描述，不使用堆栈/队列来模拟递归 Karatsuba 中的函数堆栈？

假设 F x G = (F_1 + F_2 x^n) x (G_1 + G_2 x^n)，其中 F 和 G 是 (2n-2) 次多项式。

我的直觉是记住当前两个操作数 F_i 和 G_i 的大小和索引。迭代 Karatsuba 从最小操作数的乘法开始。一旦索引为偶数，计算 ((F_1 + F_2) x (G_1 + G_2))，将其与 (F_1 x G_1) 和 (F_2 x G_2) 合并，“大小”加倍，“索引”减半。

问题是（（F_1 + F_2）x（G_1 + G_2））的计算需要另一个（大小，索引）。我想直接将 (F_1 + F_2)/(G_1 + G_2)$ 附加到 F/G 数组的末尾。在那种情况下，计算完成后如何从旧的（大小，索引）中扣除新的（大小，索引）？

您能否提供这个 karatsuba 算法的时间复杂度，该算法在 2 个 n 位长的数字上运行：

下面是我对 Karatsuba 乘法算法的 python 实现。此代码似乎适用于大多数输入，但在数字变得太大后开始失败。例如，对于 64 位输入 x = 3141592653589793238462643383279502884197169399375105820974944592 y = 2718281828459045235360287471352662497757247093699959574966967627 ，算法会失败。但是当我只使用前 35 位数字时，该算法有效。谁能解释这个实现的不足之处？

您好我正在尝试在 Javascript 中实现 karatsuba 算法。截至目前，该算法适用于某些情况，例如整数长度为 4 或 8 时。当整数长度为 6 时，它会打印出错误的结果

例如：3141*2718=>8537238（正确结果）

例如：314*271=>84981.37398106341（结果不正确）

Eg: 3141592653589793238462643383279502884197169399375105820974944592 * 2718281828459045235360287471352662497757247093699959574966967627 =>8.539734222673569e+126 (partially correct )

您能否向我解释一下如何正确计算Karatsuba 算法的 O(n) ？

我读过它等于O(n^log_2(3))但我仍然不明白如何得出这个值。

首先，我对输入长度表示为n而不是表示有点困惑n + m，但我想这只是为了缩短。

我知道每个数字都在执行一个操作，这就是它的原因n。但是你能向我解释一下是如何log_2(3)计算的，为什么是O(n^log_2(3))而不是O(n log_n(3))？

我一直在尝试在 C++ 中为两个相同长度的大数实现 Karatsuba 乘法算法。我的代码对于较小的数字（例如 3456*1492）表现正常，但对于较大的数字（例如 64 位数字）则失败。它通常会得到正确的前几个数字，但之后会出错。我正在使用 Boost 多精度库来处理大整数。

我的代码如下：

我已经将我的代码与几个在线实现进行了比较，但我无法找到任何会影响答案的显着差异。类型的精度是否可能存在问题，cpp_int或者我的代码中是否存在问题？

非常感谢你的帮助！

我开始了一门新的算法课程。教授正在尝试用其他规则创建一个乘法算法。

例如，他将我们试图相乘的数字分成两组。x = 3452那么a = 34, b = 52（同样适用于y）。

据他介绍，基本操作将是：

如果给你两个数字，每个数字只有一个数字。然后你只需将它们乘以一个基本操作并返回结果。

如果这些是非常简单的操作，您将如何计算ac、和递归？adbcbd

python不应该有任何溢出问题。那么为什么当输入很大时它会返回负答案？