# 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