====== 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 after some analysis: T(n) ≤ 3T(n/2) + cn\\
** Algorithm** \\
\\

>>>>>>>>>>>>>>>>>>>>>>>>> Recursive-Multiply(x,y):\\
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Write x = x<sub>1</sub>*2^(n/2) + x<sub>0</sub>\\
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>       y = y<sub>1</sub>*2^(n/2) + y<sub>0</sub>\\
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Compute x<sub>1</sub> + x<sub>0</sub> and y<sub>1</sub> + y<sub>0</sub>\\
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> p = Recursive-Multiply(x<sub>1</sub> + x<sub>0</sub>,y<sub>1</sub> +  y<sub>0</sub>)\\
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> x<sub>1</sub> y<sub>1</sub> = Recursive-Multiply(x<sub>1</sub>,y<sub>1</sub>)\\
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> x<sub>0</sub>y<sub>0</sub> = Recursive-Multiply(x<sub>0</sub>,y<sub>0</sub>)\\
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Return x<sub>1</sub>y<sub>1</sub>.(2^n) + (p - x<sub>1</sub>y<sub>1</sub> - \\
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> x<sub>0</sub>y<sub>0</sub>).(2^n/2) + x<sub>0</sub> y<sub>0</sub>\\
\\

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