# How this Fibonacci exponentiation by squaring algorithm works?

This is one of the best algorithms to calculate the nth Fibonacci sequence. it needs O(log(n)) time to do its job, so it's so efficient. I found it somewhere but don't know how it works! Can anyone tell me how this algorithm works? thanks. Here's the code:

``````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;
}
``````
• Why is this O(n)? It looks O(logn) to me because of the `n /= 2`. – jliv902 Feb 7 '14 at 21:05
• @jliv902 yeah you're right. Sorry, I knew that it's O(log(n)) but I don't know why I wrote O(n)! I'm sorry. I just edited it. thanks for mentioning that :) – Rasool Feb 7 '14 at 21:11
• See en.wikipedia.org/wiki/Exponentiation_by_squaring, and nayuki.eigenstate.org/page/fast-fibonacci-algorithms under the `Matrix exponentiation (medium)` heading. – Robert Harvey Feb 7 '14 at 21:23
• Thanks @RobertHarvey, I saw that link but I didn't understand. Could you please tell me what exactly it does? step-by-step. Thanks a lot :) – Rasool Feb 7 '14 at 21:31
• Well, the code probably corresponds to the math. You don't understand the math? – Robert Harvey Feb 7 '14 at 21:32