cubbi.com: Algorithms for the calculation of Fibonacci Numbers languages: [english] [русский]
serious stuff
  www.cubbi.com
personal
programming
  fibonacci numbers
    algorithms
    benchmarks
    forth examples
    postscript examples
    muf examples
    joy examples
    j examples
    scheme examples
    hope examples
    ocaml examples
    haskell examples
    prolog examples
    c++ examples
    java examples
    assembly language examples
    fortran examples
    c examples
    sh examples
    awk examples
    perl examples
    tcl examples
  asmix
  hacker test
  resume
science
martial arts
fun stuff
  www.cubbi.org
                                                    

ALGORITHM 1: EXPONENTIAL COMPLEXITY
This algorithm blindly implements the original definition for Fibonacci numbers. It is terribly inefficient, which makes it great for educational purposes. It is also an easy and fun way to test the efficiency of your compiler - check my Fibonacci benchmarks!
Complexity:
O(exp n) speed
O(exp n) space
  • ALGORITHM 1A: BINARY RECURSION.
    1. If n equals 0 or 1, return 1
    2. Recursively calculate F(n-1)
    3. Recursively calculate F(n-2)
    4. Return the sum of the results from steps 2 and 3
benchmark curves for 1A
Execution time (seconds) vs. Fibonacci number calculated
ALGORITHM 2: LINEAR COMPLEXITY
The biggest problem with ALGORITHM 1 is that it spends time re-calculating already calculated Fibonacci numbers. The obvious way to correct that is to calculate each F(n-i) only once, remembering the previous two Fibonacci numbers at any given time. To achieve this, we can use any of the following equivalent algorithms.
Fixed precision complexity
O(n) speed
O(1) space
Arbitrary precision complexity
O(n2) speed
O(n) space
  • ALGORITHM 2a: Data Structure.
    The previously calculated Fibonacci Numbers may be stored in a data structure. Note that this algorithm actually remembers more data than needed (all previous Fibonacci numbers rather than the previous two), so it takes O(n) space for fixed length numbers and O(n2) space for arbitrary precision. However, if the program needs more than one Fibonacci number and is going to call this function again, keeping everything already calculated in a data structure helps to reduce time for all subsequent calls.
    • ALGORITHM 2a-1: Infinite list.
      1. Construct an Infinite list F with F[0] equal 1 and F[1] equal 1
      2. Define F[i] as the sum of F[n-1] and F[n-2].
      3. Return the value of F[n]
    • ALGORITHM 2a-2: Infinite list with exceptions.
      1. Construct an array F with F[0] equal 1 and F[1] equal 1
      2. Define an out of bounds exception handler which will calculate F[n] as the sum of F[n-1] and F[n-2]
      3. Return the value of F[n]
    • ALGORITHM 2a-3: Simple list
      1. Create a list/array/vector/whatever F with the elements F[0] and F[1] equal 1
      2. Calculate the elements F[2..n] according to the formula F[i]=F[i-1]+F[i-2]
      3. Return F[n]
 Benchmark curves for 2A
Execution time (seconds) vs. Fibonacci number calculated
  • ALGORITHM 2b: Simple Recursion.
    Here the two previous Fibonacci numbers are stored as parameters to a recursive function.
    Note that if your compiler does not recognize tail recursion, this algorithm takes O(n) space.
    1. Define a recursive function λ(n1,n2,n) such as
    1a. λ(n1,n2,n) returns n1, if n<2
    1b. λ(n1,n2,n) return the result of λ(n1+n2,n1,n-1), if n>1
    2. Return the result of λ(1,1,n)
Benchmark curves for 2B
Execution time (seconds) vs. Fibonacci number calculated
  • ALGORITHM 2c: Non-recursive Loop.
    Here the two previous Fibonacci numbers are stored in writable variables
    1. Assign value 1 to variable n1 and value 1 to variable n2
    2. Assign the value of n1+n2 to variable n1 and assign the old value of n1 to n2
    3. Repeat step 2 n times.
    4. Return the value of variable n1
Benchmark curves for 2C
Execution time (seconds) vs. Fibonacci number calculated
ALGORITHM 3: LOGARITHM COMPLEXITY
All these algorithms are equivalent, although the equivalency is not as obvious as with ALGORITHM 2.
Fixed precision complexity:
O(log n) speed
O(log n) space
Arbitrary precision complexity:
O(n log n) speed
O(n) space
  • ALGORITHM 3a: Matrix Equation.
    This is the most mathematically elegant way to calculate a Fibonacci number. 
    | F(n)   F(n-1) |     | 1  1 | ^ n
|               |  =  |      |
| F(n-1) F(n-2) |     | 1  0 |
    Raising a matrix to the power of n requires only O(log n) matrix multiplications. However not many programming languages support matrix arithmetics, which makes most of the examples featuring this algorithm rather bulky.
benchmark curves for 3A
Execution time (seconds) vs. Fibonacci number calculated
  • ALGORITHM 3b: Fast Recursion.
    This algorithm can be easily derived from the fact that, from definition, F(n+m)=F(n)F(m) + F(n-1)F(m-1), which gives 
      if n mod 2 = 0,   F(n) = F(n/2)^2 + F(n/2-1)^2
  if n mod 2 = 1,   F(n) = F((n-1)/2)*F((n-1)/2+1) + F((n-1)/2)*F((n-1)/2-1)
    The same equations can also be derived from the matrix equation used in ALGORITHM 3A. If you do that, you will notice that this algorithm is faster than than 3A because it does not repeat calculations of the same numbers (top right and bottom left corners of the matrix in 3A are always the same).
    1. Define a recursive function λ(n) such as
    1a. λ(n) returns a pair of numbers (1,1) if n equals 0 or 1 1b. λ(n) returns a pair of numbers (2,1) if n equals 2 1c. if n is even, λ(n) calls λ(n/2-1) to obtain a pair of numbers (f1,f2) and returns a pair of numbers ( (f1+f2)*(f1+f2) + f1*f1 , (f1+f2)*f1 + f1*f2 )
    1d. if n is odd, λ(n) calls λ((n-1)/2) to obtain a pair of numbers (f1,f2) and returns a pair of numbers ( f1*(f1+f2) + f1*f2, f1*f1 + f2*f2 )
    2. Return the first element of the result of λ(n)
 benchmark curves for 3b
Execution time (seconds) vs. Fibonacci number calculated
  • ALGORITHM 3c: Binet's Formula
    In 1843, Jacques Philippe Marie Binet discovered this formula 
               1    / /1+sqrt(5)\^n+1 /1-sqrt(5)\^n+1 \
F(n) =  ------- | |---------|  -  |---------|     |
        sqrt(5) \ \    2    /     \    2    /     /
    Evaluation of Binet's formula, just as evaluation of the formula in ALGORITHM 3A, involves raising an algebraic object to the power of n, which requires O(log n) multiplications. It is slower than both 3A and 3B due to the extra work required by the use of irrational numbers and division. However, this formula is invaluable if you want to extend Fibonacci numbers to non-integer or even complex arguments.
n/a
Execution time (seconds) vs. Fibonacci number calculated
 
[Made by Cubbi] http://cubbi.com/fibonacci/algorithms.html
Page maintained by Sergey Zubkov
Last revision: $Date: 2006/03/02 17:02:52 $
[Valid CSS!]
[Valid ISO-HTML!] 		[Powered by Linux]