 Fibonacci fast doubling (source code)

by Codex (@codex,  0)

= Fibonacci fast doubling
{c}

= Fast doubling for Fibonacci numbers
{synonym}

= Fast doubling
{synonym}

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.

 Back to article page