如何使用位操作实现唐叶乘法

Question

我正在Scala（我的选择）中为在线课程实施Karatsuba 乘法。考虑到该算法旨在乘以大数，我选择了BigInt由 Java BigInteger支持的类型。我想有效地实现算法，它使用基数 10 算法从维基百科复制如下：procedure karatsuba(num1, num2)  if (num1 < 10) or (num2 < 10)    return num1*num2  /* calculates the size of the numbers */  m = max(size_base10(num1), size_base10(num2))  m2 = floor(m/2)  /* split the digit sequences in the middle */  high1, low1 = split_at(num1, m2)  high2, low2 = split_at(num2, m2)  /* 3 calls made to numbers approximately half the size */  z0 = karatsuba(low1, low2)  z1 = karatsuba((low1 + high1), (low2 + high2))  z2 = karatsuba(high1, high2)  return (z2 * 10 ^ (m2 * 2)) + ((z1 - z2 - z0) * 10 ^ m2) + z0鉴于它BigInteger在内部表示为int[]，如果我可以根据m2进行计算int[]，我可以使用位移来提取数字的低半部分和高半部分。同样，最后一步也可以通过位移来实现。然而，说起来容易做起来难，因为我似乎无法理解逻辑。例如，如果最大数为999，则二进制表示为1111100111，下半部分为99 = 1100011，上半部分为9 = 1001。我如何获得上述分割？注意：有一个现有问题显示了如何在 上使用算术BigInteger而不是位移来实现。因此，我的问题不是重复的。

Answer 1

为了能够使用位移位进行拆分和重组，基数需要是 2 的幂。使用两个本身，如链接的答案，可能是合理的。然后可以直接用 找到输入的“长度”，bitLength分割可以实现为：

// x = a + 2^N b

BigInteger b = x.shiftRight(N);

BigInteger a = x.subtract(b.shiftLeft(N));

以位N为单位的大小在哪里a。

鉴于它BigInteger是用 32 位肢体实现的，使用 2³² 作为基础是有意义的，确保大移位只涉及整个整数的移动，而不是较慢的代码路径，其中BigInteger1 和 31 之间的值移位。这可以通过四舍五入N到 32 的倍数来实现。

这一行中的特定常数，

if (N <= 2000) return x.multiply(y);                // optimize this parameter

鉴于该评论，可能不应该太相信。但是对于性能来说应该有一些限制，否则递归拆分会过深。例如，当数字的大小为 32 或更少时，只进行乘法显然更好，但好的截止值可能要高得多。在这个源中BigInteger，截止值用肢体数而不是位数表示，并设置为 80（因此为 2560 位） - 它还有一个其他阈值，高于该阈值它会切换到 3 路 Toom-Cook 乘法唐叶乘法。