java - 字节数组上的 Karatsuba 乘法优化

Question

我已经实现了两个字节数组的乘法运算，它运行良好。更准确地说，我需要将一个 64 字节的操作数与一个 32 字节的操作数相乘。

我以最简单的方式实现了它:我做了一个双循环，然后为每个数组中的每个字节计算乘积。所以对于具体的值，需要 64 * 32 = 2048 步。

我尝试使用 Karatsuba 方法对其进行优化。所以我按照以下方式进行:

a 的长度为 64 字节，b 的长度为 32 字节。

我们将 a 拆分为:a = p * 16^(32) + q(所以 p 和 q 的长度均为 32 字节)和计算:a * b = p * b * 16^(32) + q * b(产品是使用我之前描述的函数计算的)。

我得到了正确的结果，但计算时间相同:两个 32 字节数组的 2 次乘法:32 * 32 * 2 = 64 * 32 = 2048。

我的问题如下:要使用 Karatsuba 优化我的乘法，我应该完全递归地编程吗？否则它永远不会更快？

提前谢谢你:)

Answer 1

哇!作为一名程序员，我的第一份工作是为 COBOL 运行时系统优化乘法算法——那是 31 年前的事了。

我认为您会发现有效的技术是将字节组合成更大的单元。当时只有 32 位可用，所以两个字节合并成一个 short，short 相乘得到一个 32 位的 int。但在 Java 中，您有 64 位可用，因此您可以将两个 int 相乘得到一个 long。

因此，您应该通过添加字节来创建一个包含 16 个整数的数组 a1 和一个数组 b1 包含 8 个整数的数组。例如。有时像这样:

a1[0] = (a[0] << 24) + (a[1] << 16) + (a[2] << 8) + a[3]

或者您可以编写一个循环来更简洁地执行此操作。

然后将 a1 和 b1 相乘，需要 128 次运算。

我会担心溢出和有符号与无符号值。最高位之后的数字应该是无符号的，但 Java 没有 unsigned 修饰符。然而，在 Java 8 中有一些对无符号操作的支持:参见 Primitive Data Types .

如果您不能让整数/长整数无符号地工作，您总是可以将 2 或 3 个字节的组组合成整数，并浪费一些最高位来为符号位留出空间。