In this thesis, we present and analyse ways of algorithmically computing
Fibonacci numbers. In the first part we describe theoretical background
of computing elements of the Fibonacci sequence. We also describe arbitrary
precision arithmetic that allows us to do mathematical operations on
numbers that are larger than the length of processor registers. We describe
algorithms that are based on the Fibonacci sequence recursive relation, matrix
algorithms, algorithms that calculate Binet’s formula and an algorithm
that uses binomial coefficients. In the second part we present the results of
experimental comparison of the above algorithms which were implemented
in C programming language using GNU MP library for arbitrary precision
arithmetic.
|
