Explanation
Yet another algorithm for the Fibonacci sequence?
Yes, this is the second of a series of mathematical articles I'm writing and the Fibonacci sequence could not miss.
However, I'll employ different approaches for his calculating:
- How to computing the entire sequence;
- How to get a particular element by it's position;
- How to implement the iterative, recursive and functional paradigmas.
Introduction
Note the numerical sequence below:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,144, 233, ...
Note that, with the exception of first two terms, all other may be calculated using the sum of the previous two terms according to the following formulas, where M is a one-dimensional array:
Formula #1
M(1) = 1;
M(2) = 1;
M(n) = M(n-1) + M(n-2), for n > 2.
It's possible to describe this formula in a recursive way:
Formula #2
F(1) = 1;
F(2) = 1;
F(n) = F(n-1) + F(n-2), for n > 2.
There's too the Binet's formula, that permits calculating a element by it's position in the sequence:
Formula #3
Binet formula, for n> = 0.
But ultimately, why these numbers are so important? Apparently, it is something of no practical utility.
Below, Let's answer that question ...
A bit of history
Leonardo of Pisa, also known as Fibonacci (son of Bonaccio) lived in Italy during the twelfth century.
Son of a great merchant, spent much of his life traveling and studying mathematics with the Arabs, which resulted in the publication of some books on algebra and arithmetic, of which we are particularly interested in the work entitled "Liber Abbaci" which features the famous problem of the rabbits:
"How many pairs of rabbits will be produced in a year, beginning with a single pair if, in every month, each pair produces a new pair which becomes productive from the second month?"
Leonardo made the calculations in accordance with the table below:
Continuing the reasoning, it shows that we'll have 144 pairs in 12 months.
Later, other mathematicians studied the sequence and they found that it was present in other natural phenomena. Among them, we highlight the following areas of science in which it is used:
- The reflection of light rays;
- In the study of certain plants and animals;
- In geometry, the calculation of the golden section
The Binet's formula, described in Formula #3 was first published by Leonhard Euler in 1765, but was forgotten until rediscovered by the French mathematician Jackes Binet in 1843.
As a final observation on the life of Fibonacci, we can say that was the european mathematician who more disclosed the algebra in his time, contributing immensely to its popularity...
Background
To test the algorithms presented here, i suggest the following tools:
C / C++ Language
Pascal Language
Haskell Language
Using the code
No doubt, the simplest and quickest way to process the Fibonacci Numbers is through the Binet's formula, especially when we want only one element.
To obtain the entire sequence, the most commonly used method is the iterative, due to the fact only perform sum operations.
Let us now consider the implementation of the algorithms for the iterative, recursive and functional methods in C, Pascal and Haskell respectively ...
Algorithm for computing the entire sequence
Iterative Method (Formula #1)
// Purpose: Computing the fibonacci numbers in a Iterative way
// Language: C
// Author: Jose Cintra (jose.cintra@html-apps.info)
main() {
unsigned long int n, current = 1, last = 0, penult = 1, count;
printf("The Fibonacci Numbers\n");
printf("\nEnter the number of elements: ");
scanf("%d",&n);
for (count = 1; count <= n; count++) {
current = last + penult;
penult = last;
last = current;
printf("%d ",current);
}
}
Points of interest:
Notice the values in that the three main variables were initialized. Thus all the elements can be calculated without the need for conditional structures that are slower.
Algorithm to get a particular element by it's position
Recursive Method (Formula #2)
{
Purpose: Get a Fibonacci number in a recursive way
Linguagem: Pascal
Author: Jose Cintra (jose.cintra@html-apps.info)
}
var
index : integer;
function Fibo(index : integer) : integer;
begin
if index < 3 then
Fibo := 1
else
Fibo := Fibo(index - 1) + Fibo(index - 2);
end;
begin
writeln('The Fibonacci Numbers');
write('Enter the element''s position: ');
readln(index);
writeln('The element in this position is: ',Fibo(index));
end.
Functional Method (Formula #1)
Purpose: Get a Fibonacci number in a functional way
Linguagem: Haskell
Author: Jose Cintra (jose.cintra@html-apps.info)
fibo :: Int -> Int
fibolist :: [Int]
fibolist = 0 : 1 : zipWith (+) fibolist (tail fibolist)
fibo n = fibolist!!n
Binet's Formula (Formula #3)
// Purpose: Get a Fibonacci number through the Binet's Formula
// Linguagem: C++
// Author: Jose Cintra (jose.cintra@html-apps.info)
#include <iostream>
#include <stdlib.h>
#include <math.h>
using namespace std;
int main() {
int i,f;
cout << "The Fibonacci Numbers\n";
cout << "Enter the element's position: ";
cin >> i;
f = round((pow((1+sqrt(5))/2,i)-pow((1-sqrt(5))/2,i))/ sqrt(5));
cout << "The element in this position is: " << f;
}
Conclusion
This is it!
As always, a point to be considered when we implement algorithms in conventional languages is that the values of the Fibonacci numbers tend to grow rapidly, causing overflow of the result. The solution is to adopt a library or language that supports arbitrary precision numbers. Functional languages, mostly, do not have this deficiency.
Hope this helps. Questions and comments are welcome.
Download the source code here
See you soon..
References
http://en.wikipedia.org/wiki/Fibonacci
http://en.wikipedia.org/wiki/Fibonacci_number
