PDF of Eric’s handwritten notes are here.

In this lecture we’ll present a cute application of divide and conquer to multiply large integers faster than the naive algorithm.

**Multiplication problem: **Given 2 -bit numbers and (where is large). Compute .

**Naive Algorithm: **A naive algorithm for multiplying two numbers and creates an array of intermediate sums, each representing the product of by a single digit of . This algorithm takes time.

**An Idea of Gauss: **Suppose we want to multiply two complex numbers and . In our setting, we assume that multiplication is expensive, but adding/substracting is cheap. Consider the desired product

.

Gauss noticed that although the product seems to involve 4 multiplications , it can be done with just 3 multiplications. The key observation is that we don’t need to compute and individually. In fact, their sum can be written as

.

Therefore, we only need 3 multiplications: and .

**Divide and Conquer Approach for Multiplication:**

Input: 2 -bit numbers and . Assume for convenience that is a power of 2.

Output: .

Recall that in a divide and conquer algorithm, the strategy is

- Breaking the problem into smaller subproblems of the same type,
- Solving these subproblems recursively,
- Combining these solutions.

Here, we break each input number into 2 halves. Let and be the first bits and last bits of respectively. Similarly, let and be the first bits and last bits of . and can be represented as

.

Example: For , we have , and .

The product of and can be rewritten as

.

**Easy Multiplication: **An easy idea is to recursively compute , and get by adding and multiplying by powers of 2 (which is equivalent to left-shifting). This idea leads to the following algorithm:

EasyMultiply()

- Let be the first bits of and be the last bits of . Let be the first bits of and be the last bits of .
- = EasyMultiply().
- = EasyMultiply().
- = EasyMultiply().
- = EasyMultiply().
- Return .

Let be the worst case running time for input of size . Steps 1 and 6 of the algorithm take time. Steps 2 to 5 make recursive calls to multiply 4 pairs of -bit numbers. Therefore, we get the recurrence

which solves to . In other words, our new algorithm has no progress in efficiency compared with the naive one.

**Fast Multiplication:** This is where Gauss’s idea comes into the picture. Although the expression of involves 4 -bit multiplications, can we do it using only 3 subproblems? It turns out the same trick can be applied here. Since

,

we only need 3 multiplications: , and . The pseudo-code of the resulting algorithm is as follows:

FastMultiply()

- Let be the first bits of and be the last bits of . Let be the first bits of and be the last bits of .
- = FastMultiply().
- = FastMultiply().
- = FastMultiply().
- Return .

The worst case running time improves to

.

**Notes:**

It turns out that we can do even better than FastMultiply. There exists an algorithm for multiplying two -bit numbers that runs in time for any . Note that the constant in the bigO notation depends on and can be huge if is small. Furthermore, based on another important divide and conquer algorithm called Fast Fourier Transform, we can multiply two -bit numbers in .

A similar divide and conquer idea can be applied to matrix multiplication. Specifically, an input matrix of size can be divided into 4 blocks of matrices. This approach leads to an algorithm with running time , which is an improvement on the running time of the naive algorithm. The best known algorithm for matrix multiplication runs in time , and it is unknown whether a quadratic running time algorithm exists or not.

**Solving Recurrence Relations: **Consider the recurrence relation where . For some constant ,

.

Let , we have

.

Note that the first term can be written as .

For the geometric sum , we consider 3 cases:

- If the ratio i.e. , this geometric series is decreasing. Therefore, the sum is given by the first term, which is . In this case, .
- If the ratio i.e. , this geometric series is increasing. Therefore, the sum is given by the last term, which is , or equivalently . In this case, .
- If the ratio i.e. , all terms in the series are equal to 1. Since there are terms in the series, .

The above closed-form solutions of are captured in the following theorem:

*[Master Theorem] If for some constants , then *