字节数组Karatsuba乘法优化

我已经实现了两个字节数组的乘法，它工作正常。更确切地说，我需要将一个64字节的操作数与一个32字节的操作数相乘。字节数组Karatsuba乘法优化

我实现了它最简单的方法：我做了一个双循环，并计算每个数组中每个字节的产品。因此，对于具体的值，它需要64 * 32 = 2048步骤。

我试图用Karatsuba方法对其进行优化。所以我按照以下方式进行：

a的长度为64字节，而b的长度为32字节。 a = p * 16^(32) + q（所以p和q兼得的32个字节的长度）和计算：a * b = p * b * 16^(32) + q * b（与之前描述了我的函数的产品计算）

我们在分裂a。

我得到正确的结果，但它需要相同的时间来计算：两个32字节数组的乘法：32 * 32 * 2 = 64 * 32 = 2048。

我的问题是以下内容：使用Karatsuba优化我的乘法，我应该完全递归编程吗？以其他方式永远不会更快？

谢谢您提前:) :)

来源

2015-05-04 Raoul722

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

那么，我编程它在Java测试我的电脑，但目的是要切换它在Java卡 – Raoul722

你通常应该递归编程，直到你得到足够小的子问题，迭代解决它们会比递归解决它们更快（即对于Karatsuba而言，额外增加的成本将超过少一倍的收益）。对于Karatsuba乘法，截止点可能应该是三位或四位数字，但它可能会根据您的实现而有所不同（例如，这适用于Timsort的不同问题）。 –

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

如果size > MIN_SIZE_FOR_KARATSUBA（你必须通过实验找到它），然后做分割并递归调用Karatsuba。
如果size <= MIN_SIZE_FOR_KARATSUBA，那么只需乘以简单的算法。

而且也，你的阵列不拆成字节乘法，他们整数存储在基地1000或类似的东西，因为你很容易溢出的类型。

Karatsuba算法的最佳实现描述in this link。通常Karatsuba需要O(n log n)内存，但这里有一些技巧，它只需要O(n)内存。

如果您不想多次使用函数调用（因为函数调用是编程中最慢的操作），那么您可以使用循环并自己实现堆栈，如my implementation中所述。

来源

2015-05-04 10:38:39 FalconUA

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

我认为您会发现有效的技术是将字节组合成更大的单位。那时，只有32位是可用的，所以两个字节被合并成一个短路，并且短路成倍增加到32位整数。但在Java中你有64位可用，所以你可以乘以两个整数得到一个长整数。

所以，你应该使一个阵列的16个整数A1以及通过将字节B中的阵列B1 8整数。例如。有时是这样的：

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

或者你可以写一个循环来更简明地做到这一点。

然后乘以a1和b1，这应该采取128个操作。

我会担心溢出和签名与无符号值。最高位后面的数字应该是无符号的，但Java没有无符号修饰符。但是，在Java 8中，对未签名操作有一些支持：请参阅Primitive Data Types。

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

来源

2015-05-04 09:28:50 rghome

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

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

那么，实际上我想将它适配到JavaCard实现，因此它不匹配它。无论如何，这是一个很好的方式继续，感谢提示！ :) – Raoul722

字节数组Karatsuba乘法优化

回答

相关问题