Programming Praxis

One of the first functions taught to programmers who are just learning about recursion is the function to compute the fibonacci numbers. The naive function takes exponential time, as each recursive call must compute the values of smaller fibonacci numbers, so programmers are next taught how to remove the recursion by explicitly storing state information, giving a linear-time iterative algorithm. The upshot is that programming students are left with the impression that recursion is bad and iteration is good.

It is actually possible to improve the performance with a logarithmic-time algorithm. Consider the matrices

Each time the matrix is multiplied by itself, the number in the lower left-hand corner is the next fibonacci number; for instance, F₄=3 (F₀=0 is a special case). Of course, powering can be done using a binary square-and-multiply algorithm, as in the ipow and expm functions of the Standard Prelude, giving a logarithmic algorithm for computing the nth fibonacci number.

Your task is to write the three fibonacci functions — exponential, linear, and logarithmic — described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2