问题标签 [karatsuba]

我正在尝试比较两种算法及其 Big Oh 效率。我试图找到一个算法比另一种算法更有效的 n 值。任何有用的例子或资源都会有很大的帮助。

我一直在 Wikipedia 上研究 Karatsuba 的算法 ，我停在这让我感到困惑的部分。为什么这个算法会溢出，我不明白他为解决这个问题所采取的步骤。这是我的问题的截图

我正在尝试实现递归 Karatsuba 算法以将两个多项式（相同程度）相乘。我的代码仍然不适用于度数大于 1 的多项式。谁能向我解释我在函数中做错了什么？它应该适用于偶数和奇数个系数。

多项式存储在一个数组中long。每个元素代表一个系数，因此1 2 3 4表示1 + 2x + 3x^2 + 4x^3和参数size是系数的数量。

我的主要问题是这个函数不能计算正确的结果。

我正在尝试在 C++ 中使用 OpenACC 并行化 Karatsuba 算法的迭代版本。我想问一下如何矢量化 inner for loop。我的编译器显示了我关于该循环的这条消息：

这里是两个嵌套循环的代码：

实际上，我不确定是否可以对其进行矢量化。但如果是的话，我无法意识到我做错了什么。谢谢

在将两个二进制值相乘时，我试图找出一个关于 Karatsuba 算法的问题。我正在尝试乘以：

我需要弄清楚使用 Karatsuba 算法时完成了哪些子问题。我知道算法是

但是每个值代表什么？如何从二进制值转到xH,yH,xL,and yL？谢谢。

我将 CUDA 用于迭代 Karatsuba 算法，我想问一下，为什么计算出来的一条线总是不同的。

首先，我实现了这个函数，它总是正确地计算结果：

现在我想使用 2D 网格并使用 CUDA 进行 for 循环，所以我将函数更改为：

我这样调用这个函数：

结果总是错误的，总是不同的。我不明白为什么第二个实现是错误的并且总是计算错误的结果。我看不出有任何与数据依赖相关的逻辑问题。有谁知道我该如何解决这个问题？

我正在尝试实现递归 Karatsuba 算法。我成功编写了一个乘法递归算法，但它计算了 ad 和 bc。但是，对于这个程序，我尝试记下每个中间值，即 ac、bd、total、sum。许多值并没有作为预期值出现。我无法弄清楚我的代码在哪里搞砸了。我仍然是一名业余程序员，我已经花了几个小时尝试调试，但现在我别无选择，只能在这里发布我的大代码：

我写了这个按位 Karatsuba 乘法算法。它不使用字符串或math.pow. 它只是分而治之的递归，按位运算和加法：

它对正数绝对有效，但显然 -29*31 不等于 381。

解决问题的最简单方法是什么？

我的第一个想法是用 使数字为正(~(-29)+1) = 29，将它是否为负存储在布尔值中，并在我的 return 语句中处理该布尔值，但是有更好的（可能是按位）解决方案吗？

提前致谢

之前我发布了一个关于这个主题的问题，并且得到了很好的回答。在 python 类中实现归并排序功能，错误然而，关于类中的递归，我仍然有一些东西让我无法理解。在上面的链接问题中，如果我self.在递归子例程中添加前缀，我会得到与下面类输出中产生的完全相同的错误（本文中的第三个代码块）。我理解为什么会发生这种情况；object.karatsuba()仅self作为其输入，但编码的方法还要求 2，因此出现错误。

请查看以下代码，然后在第三个代码块之后查看我对解决方案的直觉。

例如：我有一个不想在课堂上工作的 karatsuba 乘法的工作实现。标准的课堂乘法在课堂上效果很好，但是......

这是类外的工作代码：

这是在第 39 行失败的类中的代码：

错误的类版本生成以下输出：

我最初的直觉是遵循顶部链接问题中概述的解决方案，如下所示：

这克服了位置参数错误，但是我遇到了一个新问题：

在这一点上，我被困住了。

我想在 python 中实现 Karatsuba 乘法。

但是当数字很大时，我会得到正确的答案。

谁能告诉我我的代码哪里错了？</p>

当 x 很大时，Karatsuba 乘法实现是不正确的。

这里的结果比较：