5.5. Integer Multiplication

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.

The basic idea is to break up the product into partial sums.
The recurrence relation of the algorithm after some analysis: T(n) ≤ 3T(n/2) + cn
Algorithm

Recursive-Multiply(x,y):

Write x = x₁*2^(n/2) + x₀

y = y₁*2^(n/2) + y₀

Compute x₁ + x₀ and y₁ + y₀

p = Recursive-Multiply(x₁ + x₀,y₁ + y₀)

x₁ y₁ = Recursive-Multiply(x₁,y₁)

x₀y₀ = Recursive-Multiply(x₀,y₀)

Return x₁y₁.(2^n) + (p - x₁y₁ -

x₀y₀).(2^n/2) + x₀ y₀

Upon analyzing this algorithm, we find out that the overall running time is O(n^(log(base 3)3)= O(n^1.59).

I give this section 8/10