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 typeset structure 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 typeset structureth 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 typeset structure, since then rounding errors will accrue and floating point numbers usually don't have enough precision.

For instance, according to Binet’s formula

F(4) = (((1 + 5^(1/2))/2)^4 - ((1 - 5^(1/2))/2)^4)/(((1 + 5^(1/2))/2) - ((1 - 5^(1/2))/2)) = 1 ... 1 + 5^(1/2))^3 + (1 + 5^(1/2))^2 (1 - 5^(1/2)) + (1 + 5^(1/2)) (1 - 5^(1/2))^2 + (1 - 5^(1/2))^3),

that is

F(4) = 1/8 (16 + 8 5^(1/2) - 4 - 4 5^(1/2) - 4 + 4 5^(1/2) + 16 - 8 5^(1/2)) = 3.

The recurrent formulas

Thus it seems better to use our recurrent definition

F(n) = F(n - 1) + F(n - 2)

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

T(n) >= T(n - 1) + T(n - 2),

and consequently typeset structure. Since the typeset structureth Fibonacci number grows exponentially with typeset structure, this algorithm is exponential. The reason for this bad behavior of the algorithm is the fact that many values are computed repeatedly since both typeset structure and typeset structure 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: typeset structure
begin: typeset structure
for typeset structure to typeset structure
     typeset structure
     typeset structure
     typeset structure
end
return typeset structure

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 typeset structure, that is typeset structure.  

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

F(n + 1) = (F(n) + L(n))/2,          L(n + 1) = (5 F(n) + L(n))/2,

F(2 n) = F(n) L(n),        L(2 n) = L^2(n) - 2 (-1)^n .

For instance to compute typeset structure we can proceed as follows:

typeset structure

typeset structure   and    typeset structure

typeset structure   and    typeset structure

typeset structure   and    typeset structure

typeset structure   and    typeset structure

typeset structure   and    typeset structure

typeset structure   and    typeset structure

typeset structure   and    typeset structure

Since typeset structure we get backwards

                                                                                               ...  2 = 28143753123}, {100, 12586269025 * 28143753123 = 354224848179261915075,  }}], TraditionalForm]

Thus typeset structure.

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

To compute additional examples go to .

An algorithm using only Fibonacci numbers can be based on identities

F(2 n - 1) = F^2(n) + F^2(n - 1),

F(2 n) = F^2(n) + 2 F(n) F(n - 1) .

In this case

typeset structure

typeset structure   and    typeset structure

typeset structure   and    typeset structure

typeset structure   and    typeset structure

typeset structure   and    typeset structure

typeset structure   and    typeset structure.

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
typeset structure,
we have

(F(n + 2)   F(n + 1)) = (1   1)^( n + 1) .   F(n + 1)   F(n)         1   0

(F(n + 2)   F(n + 1)) = (1   1)^( n + 1) .   F(n + 1)   F(n)         1   0(1)

If we would like to compute typeset structure then typeset structure and consequently

(F(102)   F(101)) = [[[[[ (1   1)^( 2) * (1   1)]^( 2)]^( 2)]^( 2) * (1   1)]^( 2)]  &nbs ...            1   0                           1   0     573147844013817084101   354224848179261915075

Another possibility is to use the above formula for typeset structure. Then

(F(101)   F(100)) = [[[[[ (1   1)^( 2) * (1   1)]^( 2)]^( 2)]^( 2) * (1   1)]^( 2)]  &nbs ...                     1   0                           354224848179261915075    218922995834555169026

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).

typeset structure,
that is

(F(n + 1)) = (1   1)^n (1/0) .   F(n)         1   0(2)

Back to Fibonacci Numbers

Cite this web-page as:

Štefan Porubský: Computing Fibonacci Numbers.

Page created  .