Saturday 8 August 2015

Quickly find fibonacci numbers(using matrix property).
 
 Divide_Conquer_Fib(n) {
       i = h = 1;
       j = k = 0;
      while (n > 0) {
               if (n%2 == 1) { // if n is odd
                   t = j*h;
                    j = i*h + j*k + t;
                    i = i*k + t;
               }
       t = h*h;
       h = 2*k*h + t;
       k = k*k + t;
       n = (int) n/2;
     }
return j;
}

No comments:

Post a Comment