DC1: Fast Integer Multiplication

Question 1

What is Gauss’ clever idea for reducing the number of multiplications needed to multiply two complex numbers?

Answer 1

Multiplying two complex numbers looks like:
(a + bi)(c + di) = ac - bd + (ad + cb)i

Because (a + b)(c + d) = ac + bd + (ad + cb),
(ad + cb) = (a + b)(c + d) - ac - bd.

This requires only THREE multiplications, and we can use those three to get everything we need to solve the original problem.

i.e., we compute (a + b)(c + d), ac, and bd, use subtraction to get (ad + cb), then plug what we need into the original.

Question 2

Describe the input and goal of the n-bit multiplication problem.

Answer 2

Input: Two n-bit integers x and y. Assume n is a power of 2 for simplicity.
Goal: Compute z = xy

Our running time will be computed in terms of n, the bit size of the integers.

Question 3

What is the pseudocode for the naive D&C solution to n-bit multiplication?

Answer 3

EasyMultiply(x, y):
input: x and y are n-bit integers, where n = 2^k for some integer k > 0
output: z = xy

x_L = First n/2 bits of x
x_R = Last n/2 bits of x
y_L = First n/2 bits of x
y_R = Last n/2 bits of x

A = EasyMultiply(x_L, y_L)
B = EasyMultiply(x_R, y_R)
C = EasyMultiply(x_L, y_R)
D = EasyMultiply(x_R, y_L)

z = 2^n * A + 2^(n/2) * (C + D) + B

return(z)

Note that 2^n * A = (2^(n/2) * x_L) * (2^(n/2) * y_L), so the 2^(n/2) comes from bitshifting n^2 places just like in 2^(n/2) * (C + D). Basically these are all the multiplications that include a left component.

Question 4

What is the recursion and running time for the naive approach to n-bit integer multiplication?

Answer 4

T(n) = 4T(n/2) + O(n) = O(n^2)

Question 5

What is the pseudocode for the faster approach to multiplying integers?

Answer 5

FastMultiply(x, y):
input: x and y are n-bit integers, where n = 2^k for some integer k > 0
output: z = xy

x_L = First n/2 bits of x
x_R = Last n/2 bits of x
y_L = First n/2 bits of x
y_R = Last n/2 bits of x

A = FastMultiply(x_L, y_L)
B = FastMultiply(x_R, y_R)
C = FastMultiply(x_L + x_R, y_L + y_R)

z = 2^n * A + 2^(n/2) * (C - A - B) + B

return(z)

Question 6

What is the recursion and running time for the faster integer multiplication algorithm?

Answer 6

T(n) = 3T(n/2)+ O(n) = O(n^log_2 3)