Fast multiplication algorithm

Question 1

Which assumption of Carl Friedrich Gaus helped reduced the time complexity of numbers multiplication, and how?

Answer 1

He noticed that in order to multiply two complex numbers:

(a + bi)(c + di) = ac - bd + (bc + ad)i

it is possible to have only three multiplications:

ac, bd and (a + b)(c + d), since

bc + ad = (a + b)(c + d) - ac - bd

It helps because x * y can be written as in the image attached.

Question 2

Explain why the run time is T(n) = 3T(n/2) + O(n)

and why is it O(n^1.59)

Answer 2

Computing 2^n/2 and comuting the additions takes O(n).

and having 3 multiplication on n/2 bits numbers results with:

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

the depth of the tree is log_2(3). so we have:

O(n^log_2(3)) = O(n^1.59)

Question 3

Why the naive recursive algorithm for matrix multiplication takes T(n) = 8T(n/2) + O(n^2)

Answer 3

We can see that there are 8 mul operations of size n/2 and 4 addition of n^2/4-size bit numbers.

Question 4

What is the big buzz around Strassen’s algorithm?

Answer 4

He managed to have a matrix multiplication recursion with only 7 multiplication calls. Thus reducting the time to O(n^log_2(7))