*(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:

and

We want to compute: .

We do this by using the Divide and Conquer technique.

and are divided into parts.

We start with :

and

,

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

Then:

Then value of is , so the original formula for is:

The main idea behind this is shifting the first half () of the binary number, the amount of bits in , so that it can be added to the second half ()

Now :

Now because is the same formula as , we can replace the with

Now to the multiplication. ()

By “plugging” in the formulas:

In this formula, there are shifts ( and respectively) and additions.

To summarize this:

- We start with multiplication over bits.
- Alternatively, we have multiplications over bits + additions + shifts (the input and the output are also bits hence both these operations take time)

To do this recursively:

if else .

The running time of this is

Here is how the algorithm would look:

- if , return
- return

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

We must then compute

Note that

This is where we ended the class.

## Leave a Reply