Article 88 - Efficient Fibonacci Computation

Fibonacci computation is a complex branch of mathematic computation, often arising in many computational problem. Computing the Fibonacci numbers is a chore, even for modern computers, and should not be taken lightly.

An amateur algorithm to compute the Fibonacci number is a recursive algorithm. However, at each level of the computation, the computer must backtrack and compute the sequence of all numbers in previous levels. That is at level i, the computer must perform i - 1 computations. Repeat this for each consecutive level and we have arrived at a terrible algorithm.

A function to compute the Fibonacci number recursively.

unsigned long recursiveFibonacci( unsigned int level ){
    if( level == 1 || level == 0 ){
        return 1;
    }

    return recursiveFibonacci( level - 1 ) 
        + recursiveFibonacci( level - 2 );
}

One can re-examine the Fibonacci sequence, how do we compute the current number in the sequence. Assuming the base cases of level 0 and 1, which are Fibonacci numbers 1 and 1, respectively; starting at level 2, we can say that at level i, the Fibonacci number is the sum of the Fibonacci numbers of the previous level and the preivous's previous level.

In other words, the Fibonacci number at level i is the number at level i - 1 aggregated with the number at level i - 2.

Translating that to a computer algorithm suggests that we keep in memory the immediate previous two numbers prior to the current sequence number in question. This gives us the following algorithm.

A function to compute the Fibonacci number iteratively.

unsigned long iterativeFibonacci( unsigned int level ){
    unsigned long previousNumber = 1;
    unsigned long previousPreviousNumber = 1;
    unsigned long currentNumber;

    for( ; level > 1; level-- ){
        currentNumber = previousNumber + previousPreviousNumber;
        previousPreviousNumber = previousNumber;
        previousNumber = currentNumber;
    }

    return previousNumber;
}

Comments (1)

Posted by anonymous - NY e at Tuesday, March 25, 2014 5:26 PM

This is nice and fast

Post a comment

  • Name:
  • Post:
  • Challenge:

Register or login to post comments easier.


Vantasy World Copyright 2011 - 2017. Vantasy World is a project developed by Vantasy Online. Privacy Policy.