In today’s lecture we studied a divide and conquer algorithm for multiplying two -bit integers. The slides have been uploaded.

Next lecture, we will finish the algorithm for integer multiplication and move on to the problem of counting inversions. The latter will be from Sec 5.3 in the book.

Here are the links to the student posts for the lecture:

Below the fold is a re-derivation of the value of an -bit number in terms of it’s two “halves.” (Again, sorry for the silly mistake in the lecture today.)

Let

.

Note that this implies that the value of the -bit string is given by

from which by dividing up the sum into two smaller sums we get

Now note that in the first sum above all the exponents of are at least , which means we can re-write the above as

In the first sum above, if we substitute by , we get

If we define

then the above expression for can be re-written as

.

The rest of the stuff we talked about then just follows from the above expression (and “expanding” out the multiplication of and in terms of the “smaller” multiplications– ).

### Like this:

Like Loading...

*Related*

## Leave a Reply