Karatsuba Fast Multiplication Algorithm

The Karatsuba algorithm is a fast multiplication algorithm. It was discovered by Anatoly Karatsuba in 1960 and published in 1962. It reduces the multiplication of two n-digit numbers to at most  single-digit multiplications in general (and exactly  when n is a power of 2). It is therefore faster than the classical algorithm, which requires n² single-digit products. For example, the Karatsuba algorithm requires 3¹⁰ = 59,049 single-digit multiplications to multiply two 1024-digit numbers (n = 1024 = 2¹⁰), whereas the classical algorithm requires (2¹⁰)² = 1,048,576.

The Karatsuba algorithm was the first multiplication algorithm asymptotically faster than the quadratic "grade school" algorithm. The Toom–Cook algorithm is a faster generalization of Karatsuba's method, and the Schönhage–Strassen algorithm is even faster, for sufficiently large n. Source: https://en.wikipedia.org/wiki/Karatsuba_algorithm

Pseudocode:

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))
  N = M/2

  // split the digit sequences about the middle
  high1, low1 = split_at(num1, N)
  high2, low2 = split_at(num2, N)

  // 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^(2*N))+((z1-z2-z0)*10^(N))+(z0)

Implementation:

public static BigInteger karatsuba(BigInteger x, BigInteger y) {

  // cutoff to brute force
  int M = Math.max(x.bitLength(), y.bitLength());
  if (M <= 2000) return x.multiply(y); // optimize this parameter
  
  // number of bits divided by 2, rounded up
  int N = (M / 2) + (M % 2);
  
  // x = a + 2^N b, y = c + 2^N d
  // x = low1 + 2^N high1, y = low2 + 2^N high2
  BigInteger high1 = x.shiftRight(N);
  BigInteger low1 = x.subtract(high1.shiftLeft(N));
  BigInteger high2 = y.shiftRight(N);
  BigInteger low2 = y.subtract(high2.shiftLeft(N));
  
  // compute sub-expressions
  BigInteger z0 = karatsuba(low1, low2);
  BigInteger z1 = karatsuba(low1.add(high1), low2.add(high2));
  BigInteger z2 = karatsuba(high1, high2);
  
  return z0.add(z1.subtract(z0).subtract(z2).shiftLeft(N)).add(z2.shiftLeft(2*N));
}

Source: http://introcs.cs.princeton.edu/java/99crypto/Karatsuba.java.html