Recently I was trying to implement Karatsuba multiplication for large numbers. Then I tried comparing my implementation with the Java BigInteger implementation. I could not follow this line of code:
// result = p1 * 2^(32*2*half) + (p3 - p1 - p2) * 2^(32*half) + p2
BigInteger result = p1.shiftLeft(32*half).add(p3.subtract(p1).subtract(p2)).shiftLeft(32*half).add(p2);
According to Karatsuba algorithm, result = (p1 * 10 ^ (2*half) ) + ( (p3 -p1 - p2) * 10 ^ (half)) + (p2)
Since the implementation used int[], I believe 32 is the number of bits in Java integer.
But I didn't understand the part that involves shifting the bits to the left. Can you someone help me understand what is going on here?
Arithmetic shift
Arithmetic shifts can be useful as efficient ways to perform multiplication or division of signed integers by powers of two. Shifting left by
n
bits on a signed or unsigned binary number has the effect of multiplying it by2^n
. Shifting right byn
bits on a two's complement signed binary number has the effect of dividing it by2^n
, but it always rounds down (towards negative infinity).