0

我正在为在线课程在 Scala（我的选择）中实现Karatsuba 乘法。考虑到该算法旨在将大数相乘，我选择了BigInt由 Java BigInteger支持的类型。我想有效地实现该算法，该算法使用以 10 为底的算法从 Wikipedia 复制如下：

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而不是位移来实现。因此，我的问题不是重复的。

4

1 回答 1

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 乘法Karatsuba 乘法。

于 2018-11-04T21:25:29.453 回答