 Fibonacci fast doubling

The identities $F_{2k}=F_k(2F_{k+1}-F_k)$ and $F_{2k+1}=F_k^2+F_{k+1}^2$ compute $(F_n,F_{n+1})$ recursively from the pair at $\lfloor n/2\rfloor$. Recursion depth is $O(\log n)$, with a constant number of large integer operations per level; the bit cost still depends on operand length.