An earlier post described how to compute Fibonacci numbers in a single arithmetic expression.

FarÃ© Rideau, the author of a page of Fibonacci computations in Lisp, suggested in a private email a simple and efficient variant, that I believe is novel.

For \(X\) large enough, \(\mathrm{Fib}_n = (X^{n+1}\ \mathrm{mod}\ (X^2-X-1))\ \mathrm{mod}\ X\).

That means you can compute Fibonacci numbers efficiently with a simple program:

```
for n in range(1, 21):
X = 1<<(n+2)
print(pow(X, n+1, X*X-X-1) % X)
```

This blog post describes how this method works, gives a few ways to think about it, easily infers the fast Fibonacci doubling formulas, provides a nice alternative to Binet's formula relating the golden ratio and Fibonacci numbers, and expands the method to generalized Fibonacci recurrences, including a near one-line solution to the problem of counting how many ways to reach the end-square of a 100-square game using a single six-sided dice.