字节数组上的Karatsuba乘法优化

Question

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

我采用最简单的方法：使用双重循环，计算每个数组中每个字节的乘积。所以对于特定的值，需要2048步（即64 * 32）。

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

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

我们将a拆分为：a = p * 16^(32) + q (因此p和q都有32字节长度)，并计算：a * b = p * b * 16^(32) + q * b（使用之前描述的函数计算乘积）。

我得到了正确的结果，但计算时间与以前相同：2个32字节数组的乘积：32 * 32 * 2 = 64 * 32 = 2048。

我的问题是：为了使用Karatsuba优化我的乘法，我应该完全递归编程吗？换句话说，其他方式永远不会更快？

谢谢您的帮助 :)

- Raoul722

---

为什么不使用BigInteger来表示大数？ - isnot2bad

我用Java编写它在我的电脑上进行测试，但目标是将其转换为Java Card。 - Raoul722

通常情况下，您应该以递归方式编程，直到您获得足够小的子问题，解决它们的迭代速度比递归更快（即对于 Karatsuba 来说，额外加法的成本将大于从中受益的少一次乘法）。 对于Karatsuba乘法，截止点可能应该是三或四位数字，但这取决于您的实现（有关应用于不同问题的示例，请查看Timsort）。 - Hadi Khan

很多时候，别人无法告诉你如何找到最优解决方案。相反，你应该熟悉Java的性能分析工具...然后仔细测量正在发生的事情。当然，需要递归的解决方案可能比避免额外方法调用的解决方案更昂贵。即时编译器在这里也可以发挥作用。长话短说：要衡量，不要假设。而且：除非处理“实时”性能要求...代码的可读性通常比拥有100％性能最大化的解决方案更重要。 - GhostCat

请查看此处 https://dev59.com/i-o6XIcBkEYKwwoYLhXh 以获取一些想法。 - Spektre

Answer 1

哇！我作为程序员的第一份工作之一就是优化COBOL运行时系统的乘法算法，那是31年前。

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

因此，您应该通过添加字节创建一个16个int的数组a1和8个int的数组b1。例如，类似于这样：

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

或者您可以编写一个循环来更简洁地完成这个任务。

然后将a1和b1相乘，这应该需要128次操作。

我会担心溢出和有符号 vs. 无符号值的问题。最高位之后的数字应该是无符号的，但Java没有无符号修饰符。然而，在Java 8中，有一些支持无符号操作的功能：请参见原始数据类型。

如果您无法将int / long设置为无符号工作，则始终可以将2或3个字节的组合成int，并浪费一些顶部位来为您留出符号位的空间。

- rghome

---

恐怕问题涉及JavaCard实现，特别是在字节上使用Karatsuba算法。 - Joop Eggen

好的，谢谢。如果有兴趣，我会留下我的回答。这对于想要优化字节数组算术操作的人可能会有用。 - rghome

实际上，我想将其适配为JavaCard实现，因此它并不匹配。无论如何，这是一个不错的方法，感谢您的提示！ :) - Raoul722

Answer 2

是的，Karatsuba算法只有在递归执行时才有效。但请记住：如果要乘以大数（通常假设两个数字具有相同的长度），Karatsuba并不总是比采用O(n^2)的简单算法更快。对于小输入（可以是1，也可以是15，具体取决于您的CPU），简单算法可能更快，因此最佳使用Karatsuba的方法是：

1. 如果size > MIN_SIZE_FOR_KARATSUBA（必须通过实验找到），则进行分割并递归调用Karatsuba。
2. 如果size <= MIN_SIZE_FOR_KARATSUBA，则仅使用简单算法将它们相乘。

此外，在乘法中不要将数组拆分为字节，而是将它们存储在1000进制或类似的整数中，因为您很容易会溢出。

Karatsuba算法的最佳实现在此链接中描述。通常Karatsuba需要O(n log n)的内存，但通过一些技巧，这里只需要O(n)的内存。

如果您不想多次使用函数调用（因为函数调用是编程中最慢的操作之一），则可以使用循环并自己实现堆栈，就像我的实现中一样。

- Chan Kha Vu