Tuesday, June 14, 2011

Fibonacci number in O(1) time!

It takes O(Exponential) time if you use recusion...
takes O(n) if you use loop with two variable
can it be solved in O(log(n))?

More better, it can be solved in O(1) time ?!!!
#include  stdio.h
#include  math.h  //please add smaller and larger symbol

unsigned long long fib(int n)
{
    double x = sqrt(5)/5;
    double f1 = x * pow((1 + sqrt(5)) / 2, n);
    double f2 = -x * pow((1 - sqrt(5)) / 2, n);

    return (unsigned long long)(f1 + f2);
}

int main()
{
    int n;
    printf("Find nth Fibonacci number, n = ");
    scanf("%d",&n);
    printf("%dth Fibonacci number: %llu\n",n,fib(n));
    return 0;
}

Unsigned long long type can represent largest number which has <=20 digits. For  larger number, use gmp library or use higher level language.

This algorithm use golden ratio.

No comments: