Main Index Number Theory Sequences Recurrent sequences Linear recurrent sequences Binary recurrent sequences Lucas’ sequences Fibonacci Numbers
Subject Index
comment on the page

Computing Fibonacci Numbers

An effective computation of the value of is often dependent on a clever application of one or several relationships between Fibonacci numbers or between them and related sequences.

Binet’s formula application

To compute th Fibonacci number using Binet’s formula or some versions thereof  depending on computation of powers of the golden mean is not very practical especially for larger values of , since then rounding errors will accrue and floating point numbers usually don't have enough precision.

For instance, according to Binet’s formula

that is

The recurrent formulas

Thus it seems better to use our recurrent definition

and to computes the Fibonacci numbers "from the bottom up", starting with the two values 0 and 1. If is the computing time for the th Fibonacci number using this approach and assuming that we get

and consequently . Since the th Fibonacci number grows exponentially with , this algorithm is exponential. The reason for this bad behavior of the algorithm is the fact that many values are computed repeatedly since both and are called and computed independently of each other.  

If we “slightly” improve the algorithm and also use the memory during the computation in such a way  that we repeatedly replace the first number by the second, and the second number by the sum of the two then we can significantly improve the necessary computing time. Consider the program scheme

variables:
begin:
for to
     
     
     
end
return

In this way the values of two consecutive terms of the Fibonacci sequence are always stored in the memory. The computing time is obviously proportional to , that is .  

Doubling formula application

We also can use an auxiliary sequence of the so-called Lucas numbers and the relations between its terms and Fibonacci numbers to reduce further the amount of the necessary computation

For instance to compute we can proceed as follows:

   and    

   and    

   and    

   and    

   and    

   and    

   and    

Since we get backwards

Thus .

The complexity of this algorithm is similarly to the powering algorithm proportional to .

To compute additional examples go to .

An algorithm using only Fibonacci numbers can be based on identities

In this case

   and    

   and    

   and    

   and    

   and    .

The matrix powering algorithm

For huge values of arguments an even faster way to calculate Fibonacci numbers can be used. It uses the matrix representation and employs exponentiation by squaring.

Since
,
we have

(1)

If we would like to compute then and consequently

Another possibility is to use the above formula for . Then

This procedure gives us three consecutive terms of the Fibonacci sequence. If we need to compute only one or two of them we can “one half” of the above formula  (1).

,
that is

(2)

Back to Fibonacci Numbers

Cite this web-page as: