15 December 2010

C program to find fibonacci series using only one variable !!!

Problem:
Generating Fibonacci series using only one variable.

There are many ways to achieve this. I have given three ways to do this in the following methods.

Method #1:
We can have a simple function to do this.
F(n) = [(x^n) – ((1 – x)^n)]/ sqrt(5);
Where x = (1 + sqrt(5))/2 = 1.6180339887
view raw fib1.c hosted with ❤ by GitHub

Method #2:
The following recursive function would do the job.
int fib(n)
{
return (n>2) ? n : fib(n-1)+fib(n-2);
}
view raw fib2.c hosted with ❤ by GitHub

Method #3:
The following one works great as well!
#include <stdio.h>
#include <stdlib.h>
int main (void)
{
unsigned long i = 1;
printf ("0\n");
while (((i & 0xffff0000) >> 16) + (i & 0xffff) <= 0xffff) {
printf ("%d\n", i & 0xffff);
i = ((i & 0xffff) << 16) | ((i >> 16) + (i & 0xffff));
}
return 0;
}
view raw fib3.c hosted with ❤ by GitHub

Cheers!!
Jack

4 comments:

Unknown said...

can u plz explain hw dis code is working??????????

Prabhu Jayaraman said...

The logic is to store both (n-2)th value in MSB & (n-1)th value in LSB of a single variable.

So, the iterations will take place as like,

i = (0,1) => 0000 0000 0000 0000 | 0000 0000 0000 0001
= (1,1) => 0000 0000 0000 0001 | 0000 0000 0000 0001
= (1,2) => 0000 0000 0000 0001 | 0000 0000 0000 0010
= (2,3) => 0000 0000 0000 0010 | 0000 0000 0000 0011

The while loop just checks the limit of an integer.

BragBoy said...

Thank you jack for a nice explanation!!

Mantu Kumar said...

Amazing code. Where did this come from?? I have never seen fibonacci series printed in this manner. Its awesome.
Please visit this : Best c compiler for windows