Fibonacci Algorithms

What is a fibonacci number?

Take the sequence of numbers which

Starts with 0, 1;
every subsequent number is the sum of the previous two

This sequence is called the Fibonacci sequence, and at first glance appears to be a total useless thing. It does have uses, however, one in population growth and another of demonstrating how very efficient algorithms can sometimes be implemented...

For the population growth illustration, we pretend there is a colony of worms in which each worm which is at least a day old can divide to form another worm every day. The dividing process occurs overnight.

We start off with one worm (yes, this a fairly contrived example, but it is for simple illustration only). The worm is old enough to divide (on Monday) into two worms, one (born on Tuesday) of which is too young to reproduce until the next day (Wednesday). On Tuesday, the original worm reproduces again so that by Wednesday, there are 3 worms, two of which can reproduce. They do so and their children are born on Thursday, at which time the one young worm also becomes old enough to reproduce. We have:

day	Mon	Tue	Wed	Thu	Fri	Sat
old worms	1	1	2	3	5	8
young worms	0	1	1	2	3	5
total worms	1	2	3	5	8	13

On each of three worm-count rows in the table, the fibonacci sequence occurs (starting at different positions). Enough said, except perhaps to note that the series also extend "backward" before 0, though every second number is negative.

The Algorithms

There is a reasonably easy way to calculate the nth fibonacci number. It happens to be the way that is immediately obvious, and without thinking too hard it might appear that it was the only way. It is as follows:

Note: this is correct for integer values of n greater than 0.

function "fibonacci", parameters 'n' (integer > 0):
if n equals 1 return 0;
if n equals 2 return 1;
let a = 0; let b = 1;
while n is greater than 2 do: {
  let c = a + b;
  let a = b; let b = c;
  subtract 1 from n;
} (end of loop)
return b;
(end of function)

This algorithm takes something in the order of n steps to complete. As I said, it appears optimal, certainly better than the following algorithm, which takes something closer to c to-the-power-of n steps to complete (where c is some constant):

function "fibonacci", parameters 'n' (integer > 0):
if n equals 1 return 0;
if n equals 2 return 1;
return fibonacci(n-2) + fibonacci(n-1);
(end of function)

The above algorithm is simple, elegant, and slow and wasteful. It does serve as a good demonstration of how simple changes to an algorithm can dramatically affect the speed at which the task can be carried out, and sometimes also the memory required to perform it. Yet, there is a better demonstration; rather than finding an even worse algorithm, it is possible to find a much better one...

The explanation is rather long winded but is hopefully interesting. I find it so. It was originally discovered by use of matrice-math, which is the way I introduce it here, however I also give it in natural pseudo-language form.

For those who don't know: a matrice is an unruled grid of numbers between two square brackets. for instance,

[4 3]

is a matrice (with only one row). By itself it is fairly useless; however there are rules about matrice operations that mean combining two or more matrices in an expression can give a useful way of expressing an algorithm or mathematical expression. When multiplying two matrices each of size a-by-a, the result is also a matrice of the same size. Each number (i,j) of the new matrice (j is the row, i is the column) is calculated by multiplying each of the numbers in the jth row of the first matrice, left to right, by the respective numbers in the ith column of the second matrice, top to bottom, and summing the products (for a-by-a matrices, there will be a products).

For instance, to multiply a 2-by-2 matrice:

-          -     -          -     -                                         -
| a11  a21 |  X  | b11  b21 |  =  | (a11*b11 + a21*b12) (a11*b21 + a21*b22) |
| a12  a22 |     | b12  b22 |     | (a12*b11 + a22*b12) (a12*b21 + a22*b22) |
-          -     -          -     -                                         _

Two important matrice-multiplication rules are:

Operand order is important: [A]*[B] is not always the same as [B]*[A]
Evaluation order is not important: [A]*[B]*[C] can be evaluated either by multiplying [A]*[B] and then multiplying the result by [C], or by multiplying [B]*[C] and then multiplying [A] by the result.
As a consequence of this latter rule (and as an example of an exception to the former), [A]^n * [A]^m = [A]^(n+m), just as in normal arithmetic.

Now, we have a useful way of describing the fibonacci function:

-      - ^n        -                                -
| 0  1 |      =    | fibonacci(n-1)   fibonacci(n)  |
| 1  1 |           |  fibonacci(n)   fibonacci(n+1) |
-      -           -                                -

That is, the matrice on the left (with the ones and zero) when multiplied by itself n times will yield a matrice which contains various fibonacci numbers, including fibonacci(n).

To put this to use:

function "fibonacci", parameters 'n' (integer > 0):
        -      -
let A = | 0  1 |;
        | 1  1 |
        -      -
while n is greater than 1 do: {
                -      -
  multiply A by | 0  1 |;
                | 1  1 |
                -      -
  subtract 1 from n;
} (end of loop)
return A(1,2);     ** A(2,1) would be equivalent **
(end of function)

In terms of computation, this algorithm is slightly more complex than the one presented near the beginning of this document, though it still executes in the order of n steps (iterations). There is however a refinement which can make the function execute in the order of log-of-n interations.

I hope it is well known that a^2n (a to the power of (2 times n)) can be also expressed as (a^n)^2 and that this second way translates directly into a more time-efficient algorithm for calculating the value than does the first. Rather than multipying a by itself 2n times (2n steps), we can multiply it by itself n times and then multiply the result by itself once (n+1 steps). This can be taken further; for large values of n, the number of steps diminishes drastically if we use ((a^(n/2))^2)^2 (there would be just over a quarter the number of steps as there would for a^n). Upon repeated application, the number of steps requires becomes quite manageable: in fact it is of order log(n).

The same rule applies to matrices. Thus, a recursive function which executes with log-of-n recursions can be created (some caution must be used to avoid raising a matrice to a non-integer power, which is impossible):

function "fibonacci", parameters 'n' (integer > 1);
let A = fibonacci-matrix(n);
return A(2,1);
(end of function)


function "fibonacci-matrix", parameters 'n' (integer > 1):
                   -      -
if n is one return | 0  1 |;
                   | 1  1 |
                   -      -
if n is an odd number do {
  let A = fibonacci-matrix(n/2 - 1);
  square A (multiply it by itself);
                -      -
  multiply A by | 0  1 |;
                | 1  1 |
                -      -
} otherwise do {
  let A = fibonacci-matrix(n/2);
  square A;
} (end-conditional)  
return A;
(end of function)

It's also possible to remove the recursion. I'll go into that a little later.

Doing it without them horrible square brackety things

A matrice is only a notational thing. A single matrice by itself doesn't really have any meaning; it is only by operations that they become useful. Also, the operations between matrices are just normal arithmetic operations expressed in a visually simple way.

The recursive fibonacci function is a case in point. A close examination of the principles and the code would reveal that in fact, using faithful matrice multiplication to solve the problem is sub-optimal. The top right and lower left numbers should always have the same value, yet a standard matrice multiplication routine would calculate their values seperately.

If we cast aside the appearance and look instead at the mechanics, we find that from the matrice expressions, a non-matrice order-of-log-of-n algorithm can be extracted.

firstly:

-      -     -                            -
| 0  1 |  =  | fibonacci(1)  fibonacci(2) |
| 1  1 |     | fibonacci(2)  fibonacci(3) |
-      -     -                            -

... is hardly news. But:

 /  -      - ^n  \  ^2       -      - ^2n
|   | 0  1 |      |      =   | 0  1 |
|   | 1  1 |      |          | 1  1 |
 \  -      -     /           -      -

is more useful - by replacing the A^b matrices with matrices of fibonaccis we get:

-                   -   -                   -   -                     -
| fib(n-1)  fib(n)  | * | fib(n-1)  fib(n)  | = | fib(2n-1)  fib(2n)  |
|  fib(n)  fib(n+1) |   |  fib(n)  fib(n+1) |   |  fib(2n)  fib(2n+1) |
-                   -   -                   -   -                     -

and therefore:

fib(2n) = fib(n-1) * fib(n) + fib(n) * fib(n+1)
fib(2n+1) = fib(n)^2 + fib(n+1)^2
fib(2n-1) = fib(n-1)^2 + fib(n)^2

Which means that, given fib(n-1), fib(n) and fib(n+1), we can calculate without iteration fib(2n-1), fib(2n) and fib(2n+1). The code of the 'fibonacci-matrix' function can be replaced to use and return these three values rather than a matrix. I leave this as an exercise.

It should also be noted that there is another way to get a computer to calculate A^n when n is integer and n's width in bits is equal or less to that of a word. It goes something like this:

function "A-to-n", parameters 'A' (number or matrix), 'n' (integer >= 0):
Let Cum = A;
let Res = 1;
let i = 0;
while i is less than the number of bits width of n do {
  if bit number i of n is set do {
    multiply Res by Cum;
  } (end of conditional)
  multiply Cum by itself;
  let i = i + 1;
} (end of loop)
return Res;
(end of function)

For large numbers, this algorithm should perform roughly as well (if not better) than the method used in "fibonacci-matrix". Also it has the benefit of not being recursive which, apart from generally being a speed improvement in itself, means that it does not use stack space.