Binary Multiplication

• Multiplication of $n$-digit bin numbers

Algorithm

• Trivial algorithm requires $O(n^2)$ operations.
• Divide and Conquer algorithm: divides the $n$-bit number into two $n/2$-bit numbers

$$\{\begin{array}{l}x=a{2}^{n/2}+b\\ y=c{2}^{n/2}+d\end{array}\Rightarrow xy=ac{2}^n+(ad+bc)2^{n/2}+bd$$

The recurrence relationship is

$$\{\begin{array}{l}T(n)=4T(n/2)+hn\\ T(1)=k\end{array}$$

in which $h$, $k$ are positive constants.

If parallel execution is available, we have $T(n)=T(n/2)+hn$.

We can further improve this, based on the fact that

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

Such that, only three recursive operations are needed.

Iterative Solution

Iteratively derive

$$\begin{array}{rl}T(n)=& 4T(n/2)+hn\\ =& 4^{2}T(n/2^2)+2hn+hn\\ =& 4^{3}T(n/2^3)+2^{2}hn+2hn+hn\\ & \cdots \\ =& 4^{2^i}T(n/2^i)+2^{i-1}hn+2^{i-2}hn+\cdots +hn\end{array}$$

The recursion stops when

$$T(1)=T(n/2^i)⟹n/2^i\le 1⟹\lg n\le i$$

That is, recursion stops when $i$ gets below $\lg n$.