我试图了解 Karatsuba 乘法算法。我编写了以下代码：

此测试用例不起作用：

但是，如果我使用此答案中的以下代码，则测试用例会产生正确的答案：

这两个函数看起来都在做同样的事情。为什么我的不工作？

我已经在 C++ 中实现了 karatsuba 乘法算法。我想对其进行优化，以便可以将两个 64 位数字相乘。有人可以帮忙吗？谢谢 ：）

给定两个表示为字符串的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，也表示为字符串。

示例 1：

示例 2：

笔记：

num1 和 num2 的长度均 < 110。num1 和 num2 都只包含数字 0-9。num1 和 num2 都不包含任何前导零，除了数字 0 本身。您不得使用任何内置的 BigInteger 库或直接将输入转换为整数。

这个问题有很多不同的方法。其中之一是使用Karatsuba 算法。

应用的伪代码是正确的，但是由于字符串和整数之间的重复转换，代码会受到影响。我能做些什么来改进呢？这是解决这个问题的正确方法吗？提前致谢

这是帮助我的参考链接-https://pythonandr.com/2015/10/13/karatsuba-multiplication-algorithm-python-code/

我正在做斯坦福的算法 MOOC 并且被 Karatsuba 乘法算法编程作业卡住了。
Karatsuba 乘法只是一种用于两个整数相乘的算法，它比通常的乘法渐进地快。

限制

• 我限制自己只使用一位数的乘法和填充数字（最后加零，即乘以 10 到某个幂），所以有 3 个基本情况
• 我还决定将数字转换为字符串并取多个数字，而不是将其除以 10 的幂，但我尝试了另一种方法，它没有帮助
• 我还决定概括该算法，即不要假设 number1 和 number2 具有相似的长度，因此我同时使用 n1 和 n2（参见代码）
• 由于以上几点，我也决定不使用高斯的技巧

我知道，这些限制可能看起来毫无意义，但我将它用作编程练习而不是一些实际的解决方案，因此我主要感兴趣的是发现我的错误而不是找到一些“更简单的解决方案”。

这是我的代码：

所以我决定尝试在 C++ 中实现 Karatsuba 的算法（自从我上辈子的第二次编码课以来就没有使用过这种语言，所以我非常非常生疏）。无论如何，我相信我已经逐行遵循伪代码，但我的算法仍然不断弹出错误答案。

*注意：我在 Mac 上运行并使用以下内容创建要运行的可执行文件c++ -std=c++11 -stdlib=libc++ karatsuba.cpp

任何人，这是起草的代码，请随时对我做错的地方或如何改进 c++ 进行一些标注。

谢谢！

代码：

我为 BigInteger 编写了一个程序，在其中实现了加减法和 Karatsuba，但它给出了错误的结果。经过几次首次亮相后，我无法弄清楚问题所在。这是我的代码：-

和标题：

但是这个代码乘法不起作用。它一直在给出错误的答案。

例如，这是一个驱动程序代码：-

这里是 429 * 429 ：

请帮帮我。提前致谢

所以我想在 Java 中不使用类 BigInteger 来运行 Karatsuba 算法，所以在遵循伪代码和这个问题之后，我得到了以下代码

现在，问题在于它产生了错误的答案，1234*5678 给出了 11686652，应该是 7006652。作为 Java 和算法的初学者，我无法查明这段代码中的确切错误，我也是确实意识到这个程序效率非常低，并且不能用于超过 4 位数字（根据链接的问题）。但这是我在学习了伪代码后直观地想到的。

所以我的问题是，我的代码有什么问题，如何在不使用 BigInteger 方法的情况下执行以下算法？

大家好，我正在尝试提出自己的 Karatsuba 乘法算法实现，其中当一个数字是单个数字时，基本情况是微不足道的乘法。我的代码似乎无法产生正确的答案，我相信这与 z1 的计算方式有关，但我不太明白，请帮帮我。

在 MITOpencourseware（6.006 第 12 课）中进行 MIT 讲座时，我遇到了 4 种乘法算法（将两个 n 位数字相乘）-

1. O(n^2) 复杂度的普通朴素方法
2. Karatsuba 算法 - O(n^1.584)
3. Toom-Cook(Toom3) - O(n^1.465)
4. Schonhage-Strassen - O(nlog(n)log(log(n)))

现在要研究的是，在哪个阈值点（即 n 的值），一种方法作为更好的算法超越了另一种方法。有人提到以上所有内容都在 gmpy 包中。

为了尝试这一点，我参考了以下链接中的 gmpy2 包文档 - https://gmpy2.readthedocs.io/en/latest/intro.html

然而，在浏览本文档的部分内容时，gmpy2 似乎更多的是处理大量数字。特别是，我没有找到实现上述 4 种算法的单独函数。那么 gmpy2 的任何部分是否实现了这些算法，所以我可以根据 n（位数）绘制这些算法的运行时间？

如何实现 Karatsuba 乘法的实现？输入以字符串形式给出。

这是我的代码