Multiplication.md

Multiplication & Big O

Addition In a Loop

It's easy to write the code for this algorithm:

def multiplication(a, b):
  product = 0
  for _ in range(b):
    product += a

  return product

The only assumption you have to make is that the += operation is a constant time operation.

• What is the definition of n?
• Whats the Big O of this algorithm?

Grade School Algorithm

This one is trickier to map to exactly the algorithm we perform on the white board or paper, but I think this is a pretty fair representation:

def multiplication(a, b):
    product = 0
    outer_multiplier = 1

    for top_digit in digits(a):
        inner_multiplier = 1

        for bottom_digit in digits(b):
            current_multiplier = outer_multiplier * inner_multiplier
            this_part = top_digit * bottom_digit * current_multiplier
            product += this_part
            inner_multiplier *= 10

        outer_multiplier *= 10

    return product

There are a ton of things that make this implementation more confusing. First of all -- we have to know how to extract digits from a number. Here are two ways:

def digits(n):
    while n:
      digit = n % 10
      n = n / 10
      yield digit

def digits_two(n):
    return [int(digit) for digit in str(n)]

Another thing is, we rely on two special forms of multiplication inside the multiplication function. We have to be able to multiply by powers of 10 (1, 10, 100, 1000 ...) and we have to be able to multiply single digits.

Lets wave our magic wand and assume these two things can be done in constant time for this analysis. Single digit multiplication could use a lookup table, for example.

• What is the definition of n?
  • Is this the same n that we focused on for the loop addition version?
  • If not, can you reformulate the Big O so that we can compare "apples to apples"?
• Whats the Big O of this algorithm?
  • Does using digits vs digits_two change the Big O time or space result?
• We made some assumptions, are those assumptions safe?

Russian Peasant

Although this algorithm is not particularly intuitive to most people, it's actually much easier to implement in Python than our grade school version. Check it out:

def multiplication(a, b):
    current_halving = a  # These two vars are just for readability
    current_doubling = b

    product = 0
    while current_halving >= 1:
        if(current_halving % 2 == 1):
            product += current_doubling

        current_doubling = current_doubling << 1
        current_halving = current_halving >> 1

    return product

• How/why do these lines work?

  current_doubling = current_doubling << 1
  current_halving = current_halving >> 1
  

• Whats the definition of n?
  • Can you define n such that we can once again compare "apples to apples"?
• Whats the Big O of this algorithm?

Lattice

Can you write code that multiplies things "the lattice way", and determine how fast or slow it is?