如何使用位操作实现 Karatsuba 乘法

Question

我正在实施 Karatsuba multiplication in Scala (my choice) for an online course. Considering the algorithm is meant to multiply large numbers, I chose the BigInt type which is backed by 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[]，如果我可以根据 int[] 计算 m2，我可以使用位移来提取数字的上下半部分。同样，最后一步也可以通过位移来实现。

然而，说起来容易做起来难，因为我似乎无法理解其中的逻辑。例如，如果最大数是 999，则二进制表示是 1111100111，下半部分是 99 = 1100011，上半部分是 9 = 1001。我如何获得上述拆分？

注意：有一个 existing question 显示了如何在 BigInteger 上使用算术而不是位移位。因此，我的问题不是重复的。

Answer 1

为了能够使用移位来进行拆分和重组，基数必须是 2 的幂。在链接的答案中使用两个本身可能是合理的。然后可以直接用bitLength找到输入的"length"，拆分可以实现为：

// x = a + 2^N b
BigInteger b = x.shiftRight(N);
BigInteger a = x.subtract(b.shiftLeft(N));

其中 N 是 a 的大小。

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

这一行的具体常量，

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

考虑到该评论，可能不应过于信任。为了性能，应该有 some 绑定，否则递归拆分会太深。例如，当数字的大小为 32 或更小时，只乘法显然更好，但可能一个好的截止值要高得多。在 BigInteger 本身的 this source 中，截止值是用肢数而不是位数表示的，并设置为 80（因此 2560 位）——它还有一个其他阈值，高于该阈值它会切换到3 路 Toom-Cook 乘法而不是 Karatsuba 乘法。

如何使用位操作实现 Karatsuba 乘法

How to implement Karatsuba multiplication using bit manipulation

java

algorithm

bit-manipulation

biginteger

karatsuba