October 06, 2014

Fibonacci Sequence

These days I learned the famous Fibonacci Sequence. Fibonacci Sequence was first discovered by Leonardo Fibonacci(1170 - 1250) to calculate the number of rabbits in a certain circumstance. In mathematics, they are numbers in the following integer sequence:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

And the sequence is related to the Golden ratio. We can see it everywhere in our lives, from architectures like Parthenon, to paintings and designs, as well as in nature.

In the book The Da Vinci Code by Dan Brown, a interesting paragraph is concerned with the Fibonacci Sequence:(And here is a link from Google Books.)

Langdon couldn’t tear his eyes from the glowing purple text scrawled across the parquet floor. Jacques Saunière’s final communication seemed as unlikely a departing message as any Langdon could imagine.

  The message read:

  13-3-2-21-1-1-8-5

  O, Draconian devil!

  Oh, lame saint!

  Although Langdon had not the slightest idea what it meant, he did understand Fache’s instinct that the pentacle had something to do with devil worship.

It is easy to find out that the sequence of numbers is concerned with Fibonacci Sequence. Besides, Leonardo da vinci, the person why the book is named after, has the same forename as Leonado Finbonacci!

The Fibonacci sequence is widely used in algorithms and data structures. In one cases, it was important in Euclid’s algorithm to determine the greatest common divisor(gcd) of two intergers, where we can prove that the worst case input for this algorithm is a pair of consequtive Fibonacci numbers.

To write a program for Fibonacci Sequence, we cannot use the recursion method because much computation is duplicated. However, we can use iterative codes. The most efficient way is to compute Fibonnacci Sequence by using memory. Below is an example of the algorithm, which I took a long time to get understood:

Input: a nonnegative integers n

Output: Fn

Method:

int f[N]
F(n){
	if(f[n] >= 0) return f(n);  //The number is stored in memory once calculated, returned when needed.
	f[n] = F(n-1) + F(n-2);  //Here is the calculation.
	return f[n];
}
int main()
{
	read n;
	f[0] = 0; f[1] = 1;
	for (i = 2; i <= n; i++)
	f[i] = -1  //It is used to determine if f[n] is calculated.
	print f(n)
}

comments powered by Disqus