我想知道关于 Katatsuba 算法的这个问题。当您应用 Karatsuba 时，您基本上必须在每次循环运行时进行 3 次乘法这些是（假设ab和cd分别是带有数字的 2 位数字a, b, c and d）：

然后我们正在寻找的总和是：

我的问题是：假设我们有两个 3 位数字：abc, def. 我发现我们只需要执行 5 次乘法即可。我还发现了这个 Toom-3 算法，但它使用了我无法理解的多项式。有人可以写下这些乘法以及如何计算有趣的总和吗bd + ae, ce+ bf, cd + be + af

我正在尝试在 C 中实现 Karatsuba 算法。我使用 char 字符串（它们是某个基数中的数字），虽然我认为我已经理解了 Karatsuba 算法的大部分内容，但我不知道应该将字符串拆分到哪里乘。

例如，我应该在哪里切123 * 123，我应该在哪里切123 * 12？
我无法找到适用于这两种计算的解决方案。

我试着把它切成两半，当数字为奇数时把结果放在地板上，但它不起作用，天花板也不起作用。

有什么线索吗？

设 a、b、c 和 d 为字符串的部分。

• 让我们试试 123 * 12

  第一次尝试(a = 1, b = 23, c = 1, d = 2) (失败)

  第二次尝试（a = 12，b = 3，c = 12，d = 0）（失败）

  第三次尝试（a = 12，b = 3，c = 0，d = 12）（成功）

  /li>

• 让我们试试 123 * 123

  第一次尝试(a = 1, b = 23, c = 1, d = 23) (失败)

  第二次尝试（a = 12, b = 3, c = 12, d = 3）（成功）

  第三次尝试（a = 12，b = 3，c = 1，d = 23）（失败）

  /li>

在这里，我不明白我在哪里搞砸了。请注意，我的填充方法在数字末尾添加n 个零，其中n = m * 2并且m等于最长字符串的大小除以 2。

编辑

既然我已经理解b并且d必须具有相同的长度，它几乎每次都有效，但仍然有例外：例如1234*12

在这里，假设我正确拆分了字符串，问题是填充，但我不知道应该如何填充。我在Wikipedia上读到，我应该根据最大字符串的大小来填充（参见几行），应该有另一种解决方案。

我正在尝试实现 Karatsuba 乘法算法。我有点遵循这个 wiki页面中的伪代码。但我总是收到这个错误：

由信号 SIGSEGV 终止（地址边界错误）

当我用其他东西替换导致递归发生的行时：

错误消失了。

这是我的代码：

初学者在这里。我大部分时间都在研究 Karatsuba 算法，只是因为我认为它会很有成效。我在这里看到过类似的问题，但它们是用其他语言编写的，而且看起来异常复杂。以下是我的代码。当它遇到对 ac 的递归调用时，它就一直在递归。就好像它从未达到基本情况一样。如果有人能提供一些关于哪里出了问题的见解，将不胜感激。对于此代码，您应该假设我乘以 2、base-10、四位数字。

我知道公式是 T(n)=3T(n/2)+O(n)，使用主方法我可以得到 T(n)=n^(log3)，以 2 为基数。

但是不使用master方法我仍然不知道如何得到答案。因为我从递归公式得到的结果是 T(n)=3^(logn) ，其中 2 是基数。

如果有人可以帮助我，我将不胜感激！

我发现对于大整数，math.pow 没有成功转换为其整数版本。使用 math.pow 实现时，我得到了一个错误的Karatsuba 乘法。

例如：

我选择了 10 ** a_size，得到了大整数的正确结果。

对于浮点数，请访问Python 中用于浮点数的内置 pow() 和 math.pow() 之间的区别？

请解释为什么 math.pow 会出现这种差异。仅从 23 和更高的 10 次方观察到。

我正在尝试通过递归调用来实现 Karatsuba 乘法。下面的代码应该可以工作，但我一直得到零作为答案。有什么想法吗？

我用 Javascript 实现了 Karatsuba 算法。

当我传递非常大的数字时，它会失败，比如 2 个 64 位的数字。我遇到了最大调用堆栈问题。我还遇到了另一个返回错误结果的实现。

两个 32 位数的数字也可以正常工作。一旦我输入 2 64 位数字，它就会进入非终止递归。这可以工作吗？

我正在做一个 karatsuba 实施，但我有这个错误：

这是我的方法：

我认为这是因为我使用了不同的长度参数，例如 123 和 456789。知道吗？

只是想知道为什么 Karatsuba 乘法的基本情况（此处显示：http: //www.sanfoundry.com/java-program-karatsuba-multiplication-algorithm/）选择为“N<= 10”？我发现 "N<= 4, 3, 2 ,1" 不会给我正确的结果。谁能解释一下？