Lab: Multiplication

In this lab we will explore the computational complexity of multiplication.

We start with Repeated Addition, as in the lecture notes. We first write a Python program implementing this algorithm.

Timing the program leads to the expected exponential slowdown as the number of bits of m gets large, and no slowdown as n gets large.

Rewriting in C gives a different program. This buys us about a factor of 13x in performance, at the price of C. It also buys us a bad overflow bug. C needs bigger ints.

So we switch algorithms. Grade School Multiplication is as follows:

              aaaaaa
            x bbbbbb
              ------
             ccccccc
            ddddddd
          ...
     + hhhhhhh
      --------------
      iiiiiiiiiiiiii

Note that when the digits are base 10 this is a bit of a pain to implement. If the digits are binary, it's a lot easier: Can test the low bit with \&, divide by 2 with >>, and multiplication by a digit becomes either a copy (when the digit is 1) or 0 (when the digit is 0).

Pseudocode ends up looking like:

    To multiply a positive integer m by a positive
    integer n:
      product ← 0
      while m > 0
          if m is odd
              add n to product
          divide m by 2
          multiply n by 2
      return product

The resulting algorithm is implemented in the Python code. It is independent of n and linear in |m| as expected.