Multiplication of two n-bit integers

Yo yo yo sup I’m back! – and ready to rock and roll. If you’re reading this, some general advice is to stop now and go do something useful, this post was not written with you in mind. Truth be told, you’ve probs arrived here by accident. If you’re not reading this, congrats! You’ve come to the right place.

To multiply A and B

To multiply integers

You want to divide,

Split into two or three parts,

Or four or more, you decide.

 

First put them in binary

Then make even splits:

A1 and B1 are easy,

Just write each as it is;

 

Now we must consider

What powers of 2

We must divide the other parts by

So they’re integers size n/(2^p)

 

Now multiply all out

A, B rewritten as above

Replace opposite multiplications

With pairs and minuses to spread da love.

 

Now all is done

We can find T(n) w.r.t. n/p

And solve the recursive relationship:

It’s quicker, you see!

Advertisements

You can add a comment in the box below.

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