Thursday, October 12, 2006

Playing with Fibonacci Number

Fibonacci number is defined simply by the following equations:

y(1) = 1
y(2) = 1
y(k) = y(k-1)+y(k-2) for all k > 2

Hence we will have a sequence like this: 1, 1, 2, 3, 5, 8, 13,... ad infinitum

The Challenge
To code a complete program fib(n) that will generate the first n-th Fibonacci number as compact as possible on the source code level. This is in contrary with the the common code optimization which depend a lot on the hardware and compiler. What I am striving to do here is to accomplish this task with the minimum number of statements.

But first question you, my dear reader may ask is "What is this for?". Answer: nothing, just for the hack of it due to boredom. Subsequent question could be "This is not fair to compare language X against language Y because X is for some A purpose and Y is for some B purpose, etc.", well, I will do this in a way as fair as I could make it, but in the real programming world, you seldom get the tool which is truly apt for the problem in hand. Don't believe me? Join a large company and see.

Any language can be used, including assembly language (bless you though).

You may assume the input parameter n is a positive integer > 2 (to avoid the corner cases) and is always valid and sane.

To kick start this, let's have our first foray in C.

To compile: 'gcc -o fib fib.c'.

#include <>

int main()
{
int i = 0;
for(i=1; i<10; i++)
printf("Fib %d is %d\n", i, fib(i));
return 0;
}/* main */

int fib (int n)
{
if (n <= 2) return 1;
else return fib(n-1) + fib(n-2);

}/* fib */

3 comments:

The Soothsayer said...

Have you tried using a very, very large number for your loop? Say INT_MAX?

Cuppa Chai said...
This comment has been removed by a blog administrator.
Cuppa Chai said...

My implementation isn't efficient, as for each number n, it recalculates all previous numbers. So under Cygwin, the calculation is basically stopped at n=45. That is an interesting question on how to balance aesthetic beauty of the code and practicality of implementation. No, not claiming my current implementation is beautiful though, just a generalized comment from there on.