Posted by: atri | November 16, 2009

## Lect 30: Integer Multiplication (post #2)

(Guest post by Andrew Cottrell)

Today in class, we began by reinforcing the strict homework policy. After that, we began to discuss multiplying 2 numbers.

Given two non-negative integers  in binary:

$a = (a_{n-1} ,\dots , a_0)$        and    $b = (b_{n-1} ,\dots , b_0)$

We want to compute:     $c = a \cdot b$.

We do this by using the Divide and Conquer technique.

$a$ and $b$ are divided into $2$ parts.

We start with $a$:

$a = (a_{n-1} ,\dots , a_{\lceil n/2\rceil})| (a_{\lceil n/2\rceil-1} ,\dots, a_0)$
$a^1 = (a_{n-1} ,\dots , a_{\lceil n/2\rceil })$    and         $a^0=(a_{\lceil n/2\rceil -1},\dots,a_0)$
$a = a^1\cdot x + a^0$,

for an $x$ we will determine soon. The sumation formula for a is:

$a=a_0+a_1\cdot 2+a_2\cdot 2^2+\cdots+a_{n-1}\cdot 2^{n-1}$

Then:

$a^1=a_{\lceil n/2\rceil}+\cdots+a_{n-1}\cdot 2^{\lfloor n/2\rfloor -1}$

Then value of $x$ is $2^{\lceil n/2\rceil}$, so the original formula for $a$ is:

$a = a^1 \cdot 2^{\lceil n/2\rceil} + a^0$

The main idea behind this is shifting the first half ($a^1$) of the binary number, the amount of bits in $a^0$, so that it can be added to the second half ($a^0$)
Now $b$:

$b = (b_{n-1} ,\cdots, b^{\lceil n/2\rceil})| (b_{\lceil n/2\rceil -1} ,\dots , b_0)$
$b = b^1\cdot x + b^0$

Now because $b$ is the same formula as $a$, we can replace the $x$ with $2^{\lceil n/2\rceil}$
$b = b^1 \cdot 2^{\lceil n/2\rceil} + b^0$

Now to the multiplication. ($c = a \cdot b$)

By “plugging” in the formulas:

$c=a\cdot b = (a^1\cdot 2^{\lceil n/2\rceil}+a^0)(b^1\cdot 2^{\lceil n/2\rceil}+b^0)$
$= a^1b^1\cdot2^{2\lceil n/2\rceil}+(a^1b^0+a^0b^1)\cdot 2^{\lceil n/2\rceil}+a^0b^0$

In this formula, there are $2$ shifts ($2^{2\lceil n/2\rceil}$ and $2^{\lceil n/2\rceil}$ respectively) and $3$ additions.

To summarize this:

1. We start with $1$ multiplication over $n$ bits.
2. Alternatively, we have $4$ multiplications over $n/2$  bits  + additions  + shifts        (the input and the output are also $O(n)$ bits hence both these operations take $O(n)$ time)

To do this recursively:

$T(n) = c$ if $n=1$ else $= 4T(n/2)+cn$.

The running time of this is $T(n) = O(n^{\log_24}) = O(n^2)$
Here is how the algorithm would look:
$\mathrm{mult}(a,b)$

• if $n = 1$, return $a_0b_0$
• return $\mathrm{mult}(a^1,b^1) \cdot 2^{2\lceil n/2\rceil} + (\mathrm{mult}(a^1,b^0) + \mathrm{mult}(a^0,b^1))2^{\lceil n/2\rceil} + \mathrm{mult}(a^0,b^0)$

The idea to reduce the amount of multiplications is to do more work upfront.

$p = (a^1 + a^0)(b^1 + b^0)$
$p = a^1b^1 + (a^1b^0 + a^0b^1) + a^0b^0$

We must then compute

1. $p$
2. $a^1b^1$
3. $a^0b^0$

Note that

$a\cdot b= a^1b^1\cdot 2^{2\lceil n/2\rceil}+(p-a^1b^1-a^0b^0)\cdot 2^{\lceil n/2\rceil}+a^0b^0$

This is where we ended the class.