# Binary Multiplication - Multiplication of $n$-digit bin numbers ## Algorithm - Trivial algorithm requires $O(n^2)$ operations. - [[divide-and-conquer|Divide and Conquer]] algorithm: divides the $n$-bit number into two $n/2$-bit numbers $ \begin{cases} x = a2^{n/2} + b \\ y = c2^{n/2} + d \end{cases} \Rightarrow xy = ac2^n + (ad + bc)2^{n/2} + bd $ The [[recurrence]] relationship is $ \begin{cases} T(n) = 4T(n/2) + hn \\ T(1) = k \end{cases} $ in which $h$, $k$ are positive constants. If [[parallelism|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{aligned} T(n) = \; & 4T(n/2) + hn \\ = \; & 4^2 T(n/2^2) + 2hn + hn \\ = \; & 4^3 T(n/2^3) + 2^2hn + 2hn + hn \\ & \cdots \\ = \; & 4^{2^i} T(n/2^i) + 2^{i-1}hn + 2^{i-2}hn + \cdots + hn \end{aligned} $ The recursion stops when $ T(1) = T(n/2^i) \Longrightarrow n/2^i \le 1 \Longrightarrow \lg n \le i $ That is, [[recursion]] stops when $i$ gets below $\lg n$.