Divide & Conquer Applications

Fast Multiplication of Integers

A logical multiplication algorithm will take $\Theta(n^2)$ time to complete. We can do better by doing a fast multiplication.

Consider that we have two numbers, $I$ and $J$, to multiply together.
Pad the numbers with zeros, at the beginning, so that the length of each number $n$ is a power of two.
Split the numbers into high and low bits like so:
\[\begin{aligned} I &= I_h2^{\frac n 2}+I_l\\ J &= J_h2^{\frac n 2}+j_l \end{aligned}\]
We multiply the high bit by an integer power of two in order to left shift the high bit back into place. This is important as each left shift only takes $O(1)$ time.
Compute recursively the product of the above equations like so:
\[\begin{aligned} I \times J &= (I_h2^{\frac n 2}+I_l)(J_h2^{\frac n 2}+j_l)\\ &= I_hJ_h2^n+\left((I_h-I_l)(J_l-J_h)+I_jJ_h+I_lJ_l\right)2^{\frac n 2} + I_lJ_l\\ &= I_hJ_h2^n+I_lJ_h2^{\frac n 2}+I_hJ_l2^{\frac n 2}+I_lJ_l \end{aligned}\]
Each multiplication that isn’t a bit-shift, should be put into the final equation again.

The recurrence relation describing this operation is:

\[T(n)=3T\left(\frac n 2\right)+cn\]

using the master method we can calculate that:

\[\Theta\left(n^{\log_23}\right)=O\left(n^{1.585}\right)\]

For the following calculation:

\[\pmatrix{A & B\\C & D}\pmatrix{E & F\\G & H}=\pmatrix{I&J\\K&L}\]

we can use the Strassen algorithm to find the solution:

Find the following seven matrix products:
\[\begin{aligned} S_1 &= A(F-H)\\ S_2 &= (A+B)H\\ S_3 &= (C+D)E\\ S_4 &= D(G-E)\\ S_5 &= (A + D)(E+H)\\ S_6 &= (B-D)(G+H)\\ S_7 &= (C-A)(E+F) \end{aligned}\]
This is one less multiplication than you would usually do when calculating a matrix product.
Find $I, J, K$ & $L$ using the following:
\[\begin{aligned} I &= S_4 + S_5 +S_6 - S_2\\\ J &= S_1 + S_2\\ K &= S_3 + S_4\\ L &= S_1 + S_5 + S_7 - S_3 \end{aligned}\]

The recurrence relation describing this operation is:

\[T(n) = 7T\left(\frac n 2\right) + bn^2\]

Using the master method we can find that this operation takes:

\[O\left(n^{\log_27}\right)=O\left(n^{2.808}\right)\]

This is faster than the usual time of $O\left(n^3\right)$.