Lesson 8

Now let's consider the function for multiplying two \(n\)-bit numbers: \[\operatorname{MULT}_{n} \colon \{0,1\}^{2n}\to \{0,1\}^{2n}.\] It can be computed with a circuit of size \(O(n^{2})\).

Theorem. \[\operatorname{size}(\operatorname{MULT}_{n})=O(n^{2}).\]

Proof. Once again, our circuit will model the column multiplication method. The product of two numbers \(x=(x_{n-1}, x_{n-2}, \dotsc, x_{0})\) and \(y=(y_{n-1}, y_{n-2}, \dotsc, y_{0})\) is \[\sum_{0 \le i, j \le n-1}2^{i+j}x_{i}y_{j}.\] First, we compute all pairwise bitwise products: \(x_{i} \land y_{j}\) for all \(0 \le i, j \le n-1\). This will take exactly \(n^{2}\) gates. After that, we need to sum all these pairwise products with their corresponding weights. We will do this sequentially, moving from the least significant bits to the most significant. Specifically, while there are at least three bits to sum for the current digit, we apply a FA block — this will replace the three bits in this digit with one bit in the same digit and one bit in the next digit. If there are only two bits left in the current digit, we will apply a Half Adder. In any case, we can ensure that only one bit remains in the current digit. Thus, at the end, there will be exactly one bit in each of the \(2n\) digits. All this addition will take no more than \(5n^{2}\) gates: each application of the FA block requires five gates, and the total number of bits decreases by one (hence, the number of FA's is at most \(n^{2}-2n\)); HA blocks are applied no more than \(2n\) times.◼