问题标签 [karatsuba]

我试图对 Karatsuba 算法进行一些更改。我不想将每个数字分成 2 个字符串，而是将其分成 3 个。

例如：

普通 Karatsuba -> 第一个数字将进入 A 和 B。第二个数字将进入 C 和 D。

为了通过递归调用来实现它，大多数代码都执行以下操作：

最后...

我要实现的 Karatsuba -> 第一个数字将进入 A、B 和 C。第二个数字将进入 D、E 和 F。

但是我不知道如何通过递归调用来实现这样的事情，因为它似乎比常见的方式复杂得多。

请帮忙。

1. 我正在尝试创建一个 Bool Array 类，它接受一串整数并将它们转换为 bool 数组。一旦我有 2 个布尔数组变量，我就会执行 Karatsuba 乘法。

以下是实际错误的来源。

这些是我的私有变量。

我使用 GDB 找出错误发生的位置，它指向了这个特定的函数调用。然后，我使用 print 语句来确定没有运行的确切行是 make_unique 行。

现在有趣的是，假设我要将 5000 位数字乘以 5000 位数字。它首先转换为 bool 数组。然后相乘，乘法完美地发生并返回另一个 bool 数组。

然而，在 13000 位的情况下，将它们相乘时，我特别得到错误：malloc(): invalid size (unsorted) 错误。

现在，我不希望有人对此进行调试，但我正在寻找 std::make_unique<bool []>(x), 可能中断的原因？

谢谢

编辑：我刚刚使用了 valgrind，我似乎得到了很多 ==14286== Invalid read of size 1 ==14286== Invalid write of size 1 ，但到目前为止我得到的输出一直很好。我什至尝试将其用于 1 和 1 之间的简单乘法。而且我在使用 valgrind 时遇到了很多错误，但我认为它只是运行顺利。编辑：

我认为到目前为止导致错误的原因是这个特定的功能。请注意，else 语句基本上是重复使用的代码（我知道我也可以不使用 if 语句），但是使用下面的代码我得到了 valgrind 错误，我将在下面复制粘贴。

Valgrind 错误

我正在运行的代码调用 + 重载

所以，现在我想我需要弄清楚为什么 + 重载给了我这些特定的错误..

卡拉丘巴算法：https ://en.wikipedia.org/wiki/Karatsuba_algorithm

RecursionError: 获取对象的 str 时超出了最大递归深度

我已经在Python中实现了Karachuba算法并根据输入值适当地返回它，但我不知道为什么会出现递归错误。

所以我正在开发一个类“bignum”来处理任何大小的整数。问题是我做了两个不同的函数来乘以 bignums。一种是标准乘法，另一种是基于 karatsuba 算法。我有一个小程序来对我的实现进行测试，这样我就可以判断它是否工作。到目前为止，使用标准乘法，一切都运行得很好，但是当我切换到 Karatsuba 乘法时，一旦输入开始很长，我的程序就会因为堆栈溢出而因分段错误而崩溃。然而，这似乎不是条目有多大的问题，因为有更大的输入可以正确计算，尽管其中一些确实会崩溃。如果有人可以看一下并给我一些有关如何继续的线索，我将不胜感激。

在这里，我发布了最小的可重现示例。我尽可能多地取出代码。

主要的：

bignum.cc 类：

bignum.h：

生成文件：

我使用的其他一些库，queue.h：

堆栈.h：

调试.h：

最后但并非最不重要的一点是，破坏程序的输入：

((((4)-(5) (((((3+9-(4) (-1)))-((4)-1-(-4) 0)))-((6+5 (0 )+(-5)) ((-4)-(-7) (-7) (-8))))+((((8) (0) (0)+3)+((-3) +6 8+(6)))-0+(-3))) ((1 (-8) (-6)-(-6)) ((((-2) (-4)-2 (- 5))+(-2) (4))-(((3)-(5)-(-4)+(-1)) (2)+(-5)))))) (((( 6)-(4) (3)-(9))+(((((-4) (-2) 0-(-6)) 1+(-7))-(1+(-3) ( -7) (-9)))-((((-3)-8+1-(-8)) (0+(8)+(0)+(-4))) 1+7))) +1 (3))) ((-3)+(4) ((((3+0+(-3)+(-1))) (((-1) (-2)+((0)- (-3)+(8)+(-7)))+(((-3)+(3)+(6)-8)+(1) (6))))-(-4) 8)(((8)-(-8) (((0)+(-9)+((3)+(0) (9) (-1)))-((4-(-9) 0 2) -((-6) (-8)-(-7) (4)))))-(((((6)+7+(-3) 5) ((9)+(1)-3* (5)))-(((-2)-(-1)-4-0)+((8)-6-(-3) (-3))))+0-(5)))) ))-((((((((8) (7)-(2)-(-9))+((9) (-8) (4)-0)))-(((5)+ (4) (4)+(3)) ((8) (-1)+6+8)))-((((-1)-(-9)+(9) (0))-(0 -(-2)+(-2)+(-3)))+(0) 0))+(-7)+(2)) (((1-(-4)-(((2)- (-7)-(-9) (-3))-(-7) (4)))+(((5+(4)-1+(-2))+((4)-(-7 )+(-6)-5))-((-2)+6+(0)+(-4))))+((((8+(-5)-(1)+(0)) -((4)+(-2) (-6)-0)) ((-9) (6)-((-4) 3+(-7)+0)))+((((-8) )+(-9)-(-5) 0) ((-7)(5)-(2)-(-5)))-4+(-6)))))+((-9)+(-8)+(2) (-4)))-((( (((-2)-(0)+(-1) (-4)) ((((-1) (7)-1 (-1))+(-3) (4)) (8)- 5))-((-7) (-9)-(((5 (2) (-4)-2) (2*(-8) (0)-8))+(((5)+( -3) (-4) (-9)) ((-2)-(-2)-2+(-9))))))+7+(4))+((-9)+5- (3+0+(((((-1)+(-2) (8) (-9))-((-5)-(-4)-(-3)-3)) (((- 7)+(-1)+(-3)+(-3)) 0 (3)))-((((0) (7)-(8)-(0)) (6+(-9) -0+(4)))-(5) (6)))))))

有人可以解释一下一般的步幅技巧是什么吗？在实现多项式表示为系数数组的多项式乘法算法时，如何使用它？跨步技巧如何使实施更高效？

是不是更适合 AVX/AVX2 向量指令的东西？我们可以在任何类型的编码平台中使用它吗？哪些平台或情况更适合使用此技巧？

编辑：在“数组的步幅”维基百科链接中它说：

许多语言（包括 C 和 C++）允许填充结构以更好地利用机器的字长和/或高速缓存行大小。例如：

在上面的代码片段中，如果 C 代码是为 32 位架构编译的，那么 myArray 的步长很可能是 8 个字节，而不是 5 个（4 个字节用于 int 加上 1 个用于 char），并且编译器已针对最短处理时间而不是最低内存使用量进行了优化（通常是这种情况）。

有人可以解释一下如何使代码运行得更快吗？

我正在尝试在 Python 中实现 Karatsuba 乘法。不幸的是，我的代码在 64 位测试用例（我正在研究的课程）上失败了，因为我开始为我的高斯计算产生负数。我在下面包含了我的代码，并想知道是否有人能够提供一些我可能缺少的指导。

此外，我有意将这些大数字存储为字符串，因为这项任务的全部目的是挑战自己调用递归。我相信 Python 能够自动处理这些大数字，但它会打败这项任务的整个具有挑战性的部分。

输入均为 64 位数字。

我知道 Karatuba 的算法和其他更有效的方法来将两个大型多项式或整数相乘。

我也知道 Karatsuba 有一个“中间产品”版本，它只计算产品的中间位（或数字）更有效。

但是有没有一种有效的方法来计算一个产品的最重要的一半？

例如，如果我有两个 n 位（n 位）数字（或 GF(2)[x] 中的多项式）a并且b，我如何有效地计算 n 个最高有效位p = a*b（比计算所有 2n 位（或 2n -1 位) 的p)

我正在构建一个处理不同基数的程序，我想通过使用并行编程来优化它，但我对所有这些都是新手。

现在，我正在尝试实现一个并行的 Karatsuba 乘法算法：

调用 Parallel.Invoke() 时它不会显示任何错误，但在返回时会显示：

使用未分配的局部变量 'L' [NumberX] csharp(CS0165)

...对于 L 和所有其他人。

就我而言，如何使 Karatsuba 的递归调用并行工作？

我花了一段时间尝试在 Python 中实现 Karatsuba 的算法，但当我尝试将两个更大的数字（超过 ~10^15）相乘时，我的结果开始变得不准确。我不知道为什么。

附带问题：我的基本情况是否有一种方法是“x 和 y 都（而不是其中一个）严格小于（而不是小于）10”

例子 ：

返回：

代替：

我一直在尝试使用字符串来实现整数乘法问题。较小数字的乘积总是正确的，但对于较大的数字，结果是错误的。
谁能告诉我代码的哪一部分导致了问题？

一个: 3141592653589793238462643383279502884197169399375105820974944592

b: 2718281828459045235360287471352662497757247093699959574966967627

答案：8539734222646569768352026223696548756537378365658178539814559622482948999279606844390394705148206869490910283679048366582723

正确答案：853973422267356706546355086954657449503488853576511496187960112706774304489320484861787507221624907301337489587184280658273