Fast Integer Multiplication

Summary

Multiplying is expensive, but addition/subtraction are cheap. Using some clever algebra tricks, we can reduce the number of multiplications that are needed which will decrease the asymptotic runtime of certain algorithms.

Contents

• Multiplying Complex Numbers
• Easy Multiply
  • Psuedocode
• Fast Mutliply
  • Psuedocode
    • Runtime

Multiplying Complex Numbers

Multiplication is expensive, adding/subtracting are cheap.

Given two complex numbers, $a + bi$ and $c + di$:

$(a + bi)(c + di) = ac + bd(i^2) + (bc + ad)$

$\phantom{(a + bi)(c + di)} = ac + bd(-1) + (bc + ad)$

$\phantom{(a + bi)(c + di)} = ac - bd + (bc + ad)$

We need 4 real number multiplications:

• ac
• bd
• bc
• ad

Can we get by using only 3 mulitiplications?

We can compute $(bc + ad)$ without computing $bc$ or $ad$

If we notice:

$(a + b)(c + d) = ac + bd + (bc + ad)$

We see the $ac$ and $bd$ terms that we want in our previous example. We can then solve for the $(bc + ad)$ term:

$(bc + ad) = (a+b)(c+d) - ac - bd$

So we can substitute this in for our original equation:

$(a + bi)(c + di) = ac - bd + (bc + ad)$

$\phantom{(a + bi)(c + di)} = ac - bd + (a+b)(c+d) - ac - bd$

Which gets us down to 3 multiplication operations!

Easy Multiply

Input: n-bit integers x and y, assume n is power of 2

Goa: Compute $z= xy$

Start by breaking each input into 2 halves (n/2 bits)

$x = 2^{n/2}x_L + x_R$

$y = 2^{n/2}y_L + y_R$

$xy = \left(2^{n/2}x_L + x_R \right)\left(2^{n/2}y_L + y_R \right)$

$\phantom{xy} = 2^n x_L y_L + 2^{n/2}\left( x_L y_R + x_R y_L \right) + x_R y_R$

We have 4 products of $n/2$ numbers which we can recursively compute:

• $x_L y_L$
• $x_L y_R$
• $x_R y_L$
• $x_R y_R$

Can we get down to 3?

Psuedocode

EasyMultiply(x,y):
  # xl = first n/2 bits of x
  # xr = last n/2 bits of x
  binary = bin(x)[2:]
  n = len(binary)
  xl = binary[:int(n/2)]
  xl = binary[int(n/2):]

  # O(n) time to compute
  binary = bin(y)[2:]
  yl = binary[:int(n/2)]
  yl = binary[int(n/2):]
  
  # Each takes T(n/2) time to compute
  A = EasyMultiply(xl,yl)
  B = EasyMultiply(xr,yr)
  C = EasyMultiply(xl,yr)
  D = EasyMultiply(xr,yl)

  # Shifts are O(n) and O(n/2) respectively
  Z = (2**n)*A + (2**(n/2))(C + D) + B

  return Z

Runtime is $T(n) = O\left( n + 4T\left(\frac{n}{2}\right) \right)$ or $O\left(n^2\right)$

Fast Mutliply

Given:

$\left( x_L + x_R \right) \left( y_L + y_R \right) = x_L y_L + x_R y_R + \left( x_L y_R + x_R y_L \right)$

$\left( x_L y_R + x_R y_L \right) = \left( x_L + x_R \right) \left( y_L + y_R \right) - x_L y_L - x_R y_R$

Then:

$xy = \left(2^{n/2}x_L + x_R \right)\left(2^{n/2}y_L + y_R \right)$

$\phantom{xy} = 2^n x_L y_L + 2^{n/2}\left( x_L y_R + x_R y_L \right) + x_R y_R$

$\phantom{xy} = 2^n x_L y_L + 2^{n/2}\left( \left( x_L + x_R \right) \left( y_L + y_R \right) - x_L y_L - x_R y_R \right) + x_R y_R$

$\phantom{xy} = 2^n A + 2^{n/2}\left( C - A - B \right) + B$

Psuedocode

FastMultiply(x,y):
  # xl = first n/2 bits of x
  # xr = last n/2 bits of x
  binary = bin(x)[2:]
  n = len(binary)
  xl = binary[:int(n/2)]
  xl = binary[int(n/2):]

  # O(n) time to compute
  binary = bin(y)[2:]
  yl = binary[:int(n/2)]
  yl = binary[int(n/2):]
  
  # Each takes T(n/2) time to compute
  A = FastMultiply(xl,yl)
  B = FastMultiply(xr,yr)
  C = FastMultiply(xl + xr, yl+yr)

  # Shifts are O(n) and O(n/2) respectively
  Z = (2**n)*A + (2**(n/2))(C - A - B) + B

  return Z

Runtime

$T(n) = 3T\left( \frac{n}{2} \right) + O(n)$

$\phantom{T(n)} \le cn + 3T\left( \frac{n}{2} \right)$

$\phantom{T(n)} \le cn + 3T\left( c\frac{n}{2} + 3T\left( \frac{n}{2^2} \right) \right)$

$\phantom{T(n)} \le cn \left( 1 + \frac{3}{2} \right) + 3^2\left( c\frac{n}{2^2} + 3T\left( \frac{n}{2^3} \right) \right)$

$\phantom{T(n)} \le cn \left( 1 + \frac{3}{2} + \left( \frac{3}{2} \right)^2 + \cdots + \left( \frac{3}{2} \right)^{\log_2{n}} \right)$

Since it is an increasing geometric series, it is on the order of the last term.

$\phantom{T(n)} = O\left( 3^{\log_2{n}} \right)$

$\phantom{T(n)} \approx O\left( 3^{1.59} \right)$