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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: