Divide and Conquer(n-bits integer multiplication)

Yesterday, I watched a Youtube video of a Statistics Introduction class in Harvard. A prof in the video said, “The best way to solve any problem is divide to the small piece of problem and work it out from them and combine later on”.

Yes, I do agree. Bit by Bit.

So the algorithm, I’ll talk about is totally same thing.

You just divide the problem into few pieces and solve and put them back.

There are few interesting problem, we can look at it.

1) Multiply lots of bits

In our computer, we can’t store enormous size of integer due to the limitation of storage problem.

So the program was multiplying two integers and you got 2 integers with huge length, how would you treat them?

You can divide and calculate small amount and store it first, and precede your work till you reach to the end. At last, you can just combine the all little solution in to one piece.

Let’s get to the detail.

Let’s say your computer only store 2 integer like 11, 22, 01 at one time and You want to compute the multiplication of the above.

How would you do that?

First, you break 1101 to 11,01 and 1011 to 10,11 and you have 4 pieces.

And multiply them by units and put them in their position later.

So the formula for doing that is like above.

n is 4 here because it’s 4 bit integer. i.e., 1101 is composed of 4 integers.

You might feel frustrated when you looked at 2^n and 2^(n/2). This is just messy stuff. I know. But just think since x1 actually is 1100 = 11 * 2^2 ( 2 = n / 2 ) and y1 is actually also 10000 = 10 * 2^2

but we treat them as if they are 11 and 10. We need to pay back what we borrowed from them.

Since we borrowed half and half and after the multiplication it became n (b/c n/2 + n/2 = n)

So it became 2^n and x1y0 we only mistreat x1 here and for y1x0 we only mistreat y1 so we need to pay 2^n/2 here.

It’s like that.

Seems darn boring. But there’s an interesting trick with this.

It’s called “Gauss’ trick”.

In the original image

we need to compute 4 things but by using the trick we only need to compute 3 chunks.

So if you have 2 n-bit integers, you need to n^2 multiplication but by using the trick, you need to work less.

That’s sort of saving but not much because you need to manipulate some code more and it just only make one multiplication less.

Well, sounds bit boring. Hmm.

Well. Next page might be more interesting I guess.

In the next problem, you will try to look for the closed pair of dots.

Sounds more fun?



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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

%d bloggers like this: