Friday, April 20, 2012

O(logn) for calculating fibonacci number

O(logn) code for computing fib(n)
 
#include
long int fib(long int n) {
 
    long int a=1, b=0, p=0, q=1, prev_a, prev_p = 0;
    while(n>0) {
        if (n%2 == 0) {
            prev_p = p;
            p = p*p + q*q;
            q = 2*prev_p*q + q*q;
            n /= 2;
        } else {
            prev_a = a;
            a = b*q + a*q + a*p;
            b = b*p + prev_a*q;
            n -= 1;
        }
    }
    return b;
}
int main(int argc, char **argv) {
 
    long int n;
 
    scanf("%ld", &n);
    printf("%ld", fib(n));
        return 0;
 
}
Reference: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_thm_1.19