# 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.