Computing Fibonacci Numbers

The State of the Art

The current best algorithm for computing $F(n)$ can be summarized succinctly using the following three equations:

$$\begin{aligned} F(2n + 1) &= 4 F(n)^2 - F(n - 1)^2 + 2(-1)^n \\ F(2n - 1) &= F(n)^2 + F(n - 1)^2 \\ F(2n) &= F(2n + 1) - F(2n - 1) \end{aligned}$$

We can use these three equations to chain our way to any number we want. We start with $F(n - 1)$ and $F(n)$ where $n = 1$: these are just our base case values 0 and 1. Then, we compute all three of $F(2n - 1), F(2n), F(2n + 1)$ using just two squares. We can either take the first two of these, in which case our new index is $2n$, or the last two, in which case our new index is $2n + 1$. Either way, for our new index $n'$, we have $F(n' - 1)$ and $F(n')$, so we can apply these formulas again.

For example, to compute $F(12)$:

• Start with $n = 1$ and our two values $(F(n - 1), F(n)) = (0, 1)$.
• Compute $(F(2), F(3))$: our new $n$ is $2n + 1 = 3$.
• Compute $(F(5), F(6))$: our new $n$ is $2n = 6$.
• Compute $(F(11), F(12))$: our new $n$ is $2n = 12$.¹
• Done!

How did I know whether to go from $n$ to $2n + 1$ or $n$ to $2n$?