Applying Fibonacci Fast Doubling Identities So I sort of understand of how these identities came about from reading this article. 


*

*$F_{2n+1} = F_{n}^2 + F_{n+1}^2$

*$F_{2n} = 2F_{n+1}F_{n}-F_{n}^2 $  


But I don't understand how to apply them. I can certainly derive these identities myself and calculate them, but once I have them how do I use them to calculate the nth Fibonacci number? Why is there a branch statement for even and odd? I tried to look up more information, but there wasn't all that much on it with the exception of some academic papers which are written so esoterically and are way beyond me.  

Suppose you want to calculate $F(n)$ for a given $n$. Here are the key ideas:


*

*Start with $k=0$.

*Keep track of the pair $(F(k), F(k+1))$.

*Either take one step forward ($k' = k + 1$) or take a doubling step ($k' = 2k$).


Actual example - let's calculate $F(5)$ using these ideas:


*

*Start with the known $k = 0: (F(k), F(k+1)) = (0, 1)$.

*Take one step forward.

*$k = 1: (F(k), F(k+1)) = (1, 1)$.

*Take a doubling step.

*$k = 2: (F(k), F(k+1)) = (1, 2)$.

*Take a doubling step.

*$k = 4: (F(k), F(k+1)) = (3, 5)$.

*Take one step forward.

*$k = 5: (F(k), F(k+1)) = (5, 8)$. 


So now we have found that $F(5) = 5$.
Further reading - math and code: https://www.nayuki.io/page/fast-fibonacci-algorithms
