Week 3 - Fast Integer multiplication

Multiplying -bit integers problem

Given -bit integers and what is ?

Naïve approaches will do this in time but you can do it faster with divide and conquer.

Gauss’s trick (aside)

Suppose have two complex numbers and where you want to compute the product in the fastest way possible.

Multiplication of real numbers uses whereas addition/subtraction takes . So if you want to do it faster - it would be best to avoid multiplication.

Looking at the expansion it may look like you need to calculate 4 multiplications. However, note the following This tells us from computing , and we can in fact get all the components we need to work out the complex multiple:

Naïve divide and conquer approach

Suppose we have and which are -bit numbers. We cut and in half so then there multiple is At which point we have broken the problem into sub-problems. We can then turn this into a recursive algorithm.

EasyMultiply(x,y):
Input: n=2^k-bit integers x & y
Output xy
if k = 1:
	return xy
else:
	X_L = 1st 2^(k-1)-bits of x, X_R = Last 2^(k-1)-bits of x
	Y_L = 1st 2^(k-1)-bits of y, Y_R = Last 2^(k-1)-bits of y
	A = EasyMultiply(X_L, Y_L), B = EasyMultiply(X_R, Y_L)
	C = EasyMultiply(X_L, Y_R), D = EasyMultiply(X_R, Y_R)
	return 2^nA + 2^(2^k-1)(B + C) + D

To analyse the run time of this algorithm not the split and shift operations take time, just the same as addition. So dividing and and computing the addition of the multiplied components are both operations. However, if you let the run time of the algorithm be then the sub multiplications take . This gives

Better approach

This time we combine Gauss’s trick with the divide and conquer approach to speed up this algorithm.

Suppose we have and which are -bit numbers. We cut and in half so then there multiple is Which we now compute using With the substitution At which point we have broken the problem into sub-problems. We can then turn this into a recursive algorithm.

EasyMultiply(x,y):
Input: n=2^k-bit integers x & y
Output xy
if k = 1:
	return xy
else:
	X_L = 1st 2^(k-1)-bits of x, X_R = Last 2^(k-1)-bits of x
	Y_L = 1st 2^(k-1)-bits of y, Y_R = Last 2^(k-1)-bits of y
	A = EasyMultiply(X_L, Y_L), B = EasyMultiply(X_R, Y_R)
	C = EasyMultiply(X_L + X_R, Y_L + Y_R)
	return 2^nA + 2^(2^k-1)(C - A - B) + B

This works slightly faster with .