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

We've seen an elegant recursive answer and improved part of it by making it take fewer options. We've then seen how an iterative version building up the Fibonacci sequence from the bottom up could avoid repeatedly computing the same values. However, is there an even faster way? You get really fast algorithms using divide and conquer algorithms, where on each step you halve the size of the problem. Is there such a solution to this. We would need to find a pattern relating numbers in the sequence to ones half way down the sequence.

Remember the sequence is:

1  2  3  4  5  6  7   8   9   10  11
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

You would have to be pretty good at pattern matching (or maths) to see it, but there is such a pattern. It is written mathematically as follows:

F(2n) = F(n)*[2F(n+1) - F(n)]
F(2n+1) = F(n+1)**2  + F(n)**2

So depending on whether the position in the sequence you are after is odd or even, the pattern is different. In both cases though you can work out the answer by combining the answer from the Fibonacci numbers halfway down the list. With an odd number you add the squares of the numbers, for example.

Take for example the 8th Fibonacci number. It can be calculated using

F(2*4) = F(4)[2*F(5) - F(4)] = 3 (2*5 - 3) = 3 * 7 = 21

Similarly, the 9th Fibonacci number can be calculated using:

F(2*4 + 1) = F(5)**2 + F(4)**2 = 5*5 + 3*3 = 25 + 9 = 34

When used to calculate large fibonacci numbers this will be much faster than the equivalent simple recursive version we already saw as it wont need to calculate all the intermediate numbers. With each calculation it takes a big jump towards the answer.

Can you turn that recursive specification in to a recursive method to calculate fibonacci sequences, and then use it to work out the naked mole-rat totals?

Find out how...