Main Index
Number Theory
Sequences
Recurrent sequences
Linear recurrent sequences
Binary recurrent sequences
Lucas’ sequences
Fibonacci Numbers
Subject Index
comment on the page
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.
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
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 .
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 .
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.
(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) |
Cite this web-page as:
Štefan Porubský: Computing Fibonacci Numbers.