This is an old revision of the document!
Table of Contents
5.5. Integer Multiplication
The Problem
We need an efficient way to multiply two integers. The widely used algorithm costs O(n²) time.
Our goal: improve on this quadratic running time.
Designing the Algorithm
The basic idea is to break up the product into partial sums.
The recurrence relation of the algorithm: T(n) ≤ 4T(n/2) + cn
Algorithm
Recursive-Multiply(x,y):
Write x = x1*2^(n/2) + x0
y = y1*2^(n/2) + y0
Compute x1 + x0 and y1 + y0
p = Recursive-Multiply(x1 + x0,y1 + y0)
x1 y1 = Recursive-Multiply(x1y1)
x0y0 = Recursive-Multiply(x0y0
Return x1y1.(2^n) + (p - x1y1 -
x0y0).(2^n/2) + x0 y0
