代码之家 › 专栏 › 技术社区 › Abhijit Sarkar

如何用位操作实现Karatsuba乘法

karatsuba biginteger bit-manipulation algorithm java

Abhijit Sarkar · 技术社区 · 7 年前

我正在实施 Karatsuba multiplication 在Scala(我的选择)的在线课程。考虑到这个算法是用来乘法的,我选择了 BigInt BigInteger

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 整数[]

然而,说起来容易做起来难,因为我似乎无法理解逻辑。例如,如果最大值为 999 1111100111 ,下半部分是 99 = 1100011 ,上半部分是 9 = 1001

有一个 existing question 这说明了如何在上使用算术实现 大整数

1 回复 | 直到 7 年前

user555045 7 年前

为了能够使用位移位来进行拆分和重组,基极必须是2的幂。使用两个本身,如在链接的答案,可能是合理的。然后输入的“长度”可以直接用 bitLength ,拆分可以实现为:

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

哪里 N a 会有零零碎碎的。

BigInteger 是用32位分支实现的,使用2作为基是有意义的,确保大的移位只涉及整数的移动,而不涉及到更慢的代码路径 大整数 在1和31之间移动一个值。这可以通过四舍五入来实现

这一行的具体常数,

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

考虑到这一点,我们不应该太信任他。对于性能,应该有一些但是,如果不这样做,递归分裂就太深了。例如,当数字的大小为32或更小时,直接乘法显然更好,但一个好的截止值可能要高得多。在里面 this source 大整数 截止线本身是用肢体的数量来表示的,而不是用位来表示的,并且设置为80(所以2560位)-它还有一个阈值,超过这个阈值,它将切换到3路Toom Cook乘法,而不是Karatsuba乘法。