问题标签 [karatsuba]

有人可以帮我分解一下吗？为什么不能在两次乘法中完成？

复数的乘法

如果将计算所需的乘法次数视为其难度的衡量标准，并且这些计算是使用复数执行的，那么很自然地会问需要多少实数乘法来评估复数乘积的实部和虚部。形成复数乘积的自然方式需要四次实数乘法。然而，它可以用三个而不是两个乘法来完成。

定理- 计算两个复数的乘积需要三个实数乘法，即使乘以实数常数不计算在内。

证明草图由于复数乘法的实部和复数部分都不能在一次实数乘法中确定，如果这个计算可以在两次乘法中完成，那么对于 C _i、 W _i、 X _i的某些选择，它将完成， Y _i和 Z _i以下列方式。

这导致 20 个未知数中的 20 个非线性方程，C _i，W _i，X _i，Y _i和 Z _i其中 (i = 1,2,3,4)，它们没有实解，因此没有在两个实数乘法中执行复数乘法的方法

资源：

门罗，伊恩。“40-44。” http://dl.acm.org/。过程。第三届 ACM 计算理论年度研讨会论文集，俄亥俄州，Shaker Heights。埃德。Michael A. Harrison、Ranan B. Banerji 和 Jeffrey D. Ullman。ACM，1971 年 5 月 3 日。网络。2016 年 11 月 26 日。http://dl.acm.org/citation.cfm?doid= 800157.805036。

我对编程比较陌生，并且不希望在运行时间方面对该算法特别有效，而只是尝试复制 Karatsuba 算法并使其工作。

我已经尝试了许多数字和小数字（如 y = 40004009343254，x = 40004001343234）工作正常，当数字大小增加时（如 y = 4000400934325423423，x = 4000400134323432423），算法停止正常工作并返回相似但不正确答案。

任何关于可能出错的线索将不胜感激！

注意：这个线程不是关于效率，而是关于获得正确的结果。也就是说，关于效率的评论也会被考虑和赞赏。

代码：

如何使用 Karatsuba 算法计算两个 64 位数字的乘积，使得只有一位数字参与乘法？

n=位数

由于我们正在处理位级别的复杂性，因此每次加法都需要 O(n) 并且对于每个递归调用，至少有一个加法导致总数为 (n-2000)*n。我在这里做错了什么？

代码来自 - http://introcs.cs.princeton.edu/java/99crypto/Karatsuba.java.html

最近我试图为大数实现 Karatsuba 乘法。然后我尝试将我的实现与 Java BigInteger 实现进行比较。我无法遵循这行代码：

根据 Karatsuba 算法，result = (p1 * 10 ^ (2*half) ) + ( (p3 -p1 - p2) * 10 ^ (half)) + (p2)

由于实现使用了 int[]，我相信 32 是 Java 整数中的位数。

但我不明白涉及将位向左移动的部分。你能帮我理解这里发生了什么吗？

我已经实现了 karatsuba 乘法算法。我想以这种方式改进它，我可以将 2 个 64 位数字相乘，但我不知道该怎么做。我得到一个提示，这两个数字都包含数字的个数，它是 2 的幂，但它什么也没告诉我。你能给出任何其他提示吗？数学提示或算法改进提示。

我正在尝试使用 Java 起诉 BigInteger 来实现 karatsuba 算法，我遵循了所有步骤，但我没有得到正确的结果，是什么让我抓狂。

这是我的代码：

我使用以下条目测试了代码：karatsuba(new BigInteger("1252",new BigInteger("532") , 10)虽然正确的结果是 666064 ，但我得到 2212864 !!!。我调试了，令人惊讶的是，当执行流程到达 return 语句时，程序并没有停止，而是进入了BigInteger t2 = karatsuba(a0, b0, base);语句。

所以我不知道我做错了什么。任何帮助将不胜感激。

我最近将 Karatsuba 乘法作为个人练习。我按照wikipedia 上提供的伪代码用 Python 编写了我的实现：

这是我的python实现：

我的问题是关于z0,z1和z2.
z2移动了m位（其中m是两个相乘数字中最大的长度）。
该算法不是简单地乘以10^(m)，而是使用 *10^(2*m2)* 其中m2是m/2。

我尝试用 m 替换2 * m2并得到不正确的结果。我认为这与数字的分配方式有关，但我不确定发生了什么。

我正在实施 karatsuba 的方法作为练习的一部分。Karatsuba 的方法本身并不难，但其中一部分让我感到困惑。被相乘的两个数字都必须分成两半，即高位和低位。但是我找不到太多关于这种拆分是如何完成的信息。

我注意到大多数 Karatsuba 实现使用字符串来表示巨大的数字，但我正在做一些不同的事情。我将它们表示为一个整数数组，其中每个元素是巨大数字的下 30 位。请注意，这意味着这些数组可能是奇数长度。如果巨大数字的大小不是 30 的倍数，它会得到前导零，因此它仍然可以这样表示。

那么这怎么能分成高半和低半呢？我遇到的主要问题是，由于它可能是奇数长度，这意味着我不能只将数组除以它们的元素。基本上，我怎样才能选择这些 int 数组的前半部分和后半部分，以便我可以继续在 Karatsuba 的方法中递归？

只要我可以检索这些位，我就可以从它们创建两个较小的 int 数组。

这是我的代码：

x 和 y 是因子，n 是较大数字的大小，并被描述为以二进制表示形式写入该数字所需的位数。对于 x 和 y 的某些值，该算法不会返回正确的 x*y 值，因为我无法得到正确的 g。例如，对于

该方法返回 52 而不是 44，因为它将 -3 分配给 g，而不是 -1。

知道如何解决这个问题吗？任何帮助将不胜感激。