Posted by: atri | November 16, 2010

## Lect 32: Multiplying two integers

In today’s lecture we studied a divide and conquer algorithm for multiplying two $n$-bit integers. The slides have been uploaded.

Next lecture, we will finish the algorithm for integer multiplication and move on to the problem of counting inversions. The latter will be from Sec 5.3 in the book.

Here are the links to the student posts for the lecture:

Below the fold is a re-derivation of the value of an $n$-bit number in terms of it’s two “halves.” (Again, sorry for the silly mistake in the lecture today.)

Let

$a=(a_{n-1},a_{n-2},\dots,a_1,a_0)$.

Note that this implies that the value of the $n$-bit string $a$ is given by

$a=\sum_{i=0}^{n-1} a_i\cdot 2^i,$

from which by dividing up the sum into two smaller sums we get

$a=\sum_{i=\lfloor n/2\rfloor}^{n-1} a_i\cdot 2^i +\sum_{i=0}^{\lfloor n/2\rfloor-1} a_i\cdot 2^i.$

Now note that in the first sum above all the exponents of $2$ are at least $\lfloor n/2\rfloor$, which means we can re-write the above as

$a=2^{\lfloor n/2\rfloor}\sum_{i=\lfloor n/2\rfloor}^{n-1} a_i\cdot 2^{i-\lfloor n/2\rfloor} +\sum_{i=0}^{\lfloor n/2\rfloor-1} a_i\cdot 2^i.$

In the first sum above, if we substitute $i$ by $j+\lfloor n/2\rfloor$, we get

$a=2^{\lfloor n/2\rfloor}\sum_{j=0}^{n-\lfloor n/2\rfloor -1} a_{j+\lfloor n/2\rfloor}\cdot 2^{j} +\sum_{i=0}^{\lfloor n/2\rfloor-1} a_i\cdot 2^i.$

If we define

$a^1=\left(a_{n-1},\dots,a_{\lfloor n/2\rfloor}\right)\text{ and } a^0=\left(a_{\lfloor n/2\rfloor -1},\dots, 0\right),$

then the above expression for $a$ can be re-written as

$a= 2^{\lfloor n/2\rfloor}\cdot a^1+a^0$.

The rest of the stuff we talked about then just follows from the above expression (and “expanding” out the multiplication of $a$ and $b$ in terms of the “smaller” multiplications– $a^1\cdot b^1, a^1\cdot b^0,a^0\cdot b^1,a^0\cdot b^0$).