This is one of the best algorithms to calculate the nth Fibonacci sequence. It only needs O(log(n)) time to do its job, so it's very efficient. I found it somewhere but don't know how it works!
Can anyone tell me how this algorithm works?
int fib3 (int n) {
int i = 1, j = 0, k = 0, h = 1, t;
while (n > 0) {
if (n % 2) {
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 /= 2;
}
return j;
}
Best Answer
It's called the "matrix form" - take a look at Wikipedia
You can compute next Fibonacci number (k+2) by multiplying matrix on a vector of two previous elements (k + 1 and k). Hence, k + 3 can be computed by multiplying matrix on vector of (k + 2 and k + 1). This equals squared matrix multiplied on (k + 1 and k). So on.
Your code simply squares the matrix, taking into account odd powers.