Programming Puzzle 1 Solutions Part 3: new naked mole-rats

We've seen an elegant recursive answer and improved part of it by making it take fewer options. Can we now work out a quicker way?

We are using recursion and that is elegant in that there is a clear link from specification to algorithm. However, the recursive solution is slow because it computes the same Fibonacci numbers over and over again. A faster way is to build up the answer iteratively from the lowest values.

To compute the next value we are always going to want to add the previous two so we need to keep the last two values. The first two values are both 1 so we can set that up to start.

        previous = 1
        latest = 1

We then need to repeatedly calculate the new values from the existing ones. The previous value will become the one that was the latest one, and we will get a new latest value. The new value though is obtained by adding the latest and previous values. That means we need to make a copy of the previous value before we over-write it with the old latest value. We can then compute the new value, and finally copy the saved value into previous

                temp = latest
                latest = latest + previous
                previous = temp

We do this in a loop, running up until we get to the year of interest:

        for i in range(0,year) :
                temp = latest
                latest = latest + previous
                previous = temp

When the loop finishes the latest value will be the number we are after, so we return it.

def nakedMoleRat(year):
        previous = 1
        latest = 1
        for i in range(0,year) :
                temp = latest
                latest = latest + previous
                previous = temp
        return latest

We can cut out a few assignments here by doing a parallel assignment (and hope the compiler makes use of that)

def nakedMoleRat(year):
        previous = 1
        latest = 1
        for i in range(0,year) :
               previous, latest = latest, latest + previous
        return latest

This is a much faster way of computing a Fibonnaci number but we can actually do even better, especially for big numbers, by looking for a divide and conquer method. Can you see a pattern in the sequence that allows the problem size to be halved on each step?

Find out how...