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.  

Here is (to my mind) a clean way of both presenting and computing with these identities, although you will have to know how to multiply matrices. (This is one of the most useful things you could possibly learn how to do anyway, so it's well worth doing if you haven't already.)  
Start with the matrix $M = \left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right]$. It's a nice exercise to prove by induction that
$$M^k = \left[ \begin{array}{cc} F_{k+1} & F_k \\ F_k & F_{k-1} \end{array} \right]$$
where my convention is that $F_0 = 0, F_1 = 1$ and hence that $F_{-1} = 1$ (no, really). Then both doubling formulas together are equivalent to the single doubling formula
$$M^{2k} = M^k M^k.$$
To compute $F_{k+1}$ for a very large $k$, the way you use this version of the doubling formula is to compute $M^k$ using binary exponentiation, then read off the top left entry. 
Example. Let's compute $F_9$ this way. This is the top left entry of the matrix $M^8$, which we will compute by repeatedly squaring:
$$M^2 = \left[ \begin{array}{cc} 2 & 1 \\ 1 & 1 \end{array} \right]$$
$$M^4 = \left[ \begin{array}{cc} 2 & 1 \\ 1 & 1 \end{array} \right]^2 = \left[ \begin{array}{cc} 5 & 3 \\ 3 & 2 \end{array} \right]$$
$$M^8 = \left[ \begin{array}{cc} 5 & 3 \\ 3 & 2 \end{array} \right]^2 = \left[ \begin{array}{cc} 34 & 21 \\ 21 & 13 \end{array} \right].$$
Hence $F_9 = 34$. 
Exercise. Show that this answer is equivalent to Nayuki Minase's answer by first computing that $M^2 = M + 1$ and then showing by induction that this implies
$$M^k = F_k M + F_{k-1}.$$
Hence keeping track of the entries of $M^k$ is equivalent to keeping track of the pair $(F_k, F_{k-1})$. 
