Dennis Hackethal’s Blog
My blog about philosophy, coding, and anything else that interests me.
A Better Way to Generate the Fibonacci Sequence
The Fibonacci sequence is wellknown in math and engineering. It starts with 0
and 1
; each subsequent number is defined as the sum of the preceding two. Thus, the sequence looks like this:
0 1 1 2 3 5 8 13 21 ...
Traditionally, implementations of the Fibonacci sequence are recursive. For example, to compute the n
th number of the sequence (n
starting at 0
), you could write the following Clojure code:
(defn fibonacci [n]
(if (> n 1)
(+ (fibonacci (dec n)) (fibonacci ( n 2)))
n))
In other words, for any n
greater than 1
, we compute the n
th number using the preceding two numbers; for any n
less than or equal to 1
, we simply return n
since the first two Fibonacci numbers coincide with their indices.
One problem with this approach is that it consumes the stack, meaning the attempt to compute the n
th number for a sufficiently large n
will result in a stack overflow. Also, the function calls branch out exponentially – the first invocation results in two subinvocations, each of which calls itself twice over, and so on. Therefore, computing only the 40th number already takes several seconds. Lastly, the two recursive calls duplicate a lot of work: computing the number at index n  1
already computes the number at n  2
, yet the latter step is repeated regardless.
Popular approaches to these problems include the use of memoization to avoid redundant computations; you could also use a loop instead of recursion to avoid stack overflows. Both approaches greatly improve performance, reducing time complexity from exponential to linear. But I recently learned about an approach you may not have heard of: it is nonrecursive, indeed noniterative, reducing time complexity to O(1).
It’s called Binet’s formula (proof). It computes each number directly using the golden ratio, denoted by phi
, bypassing the need for iterative computation:
(defn fibonacci' [n]
(let [phi (/ (+ 1 (Math/sqrt 5)) 2)]
(Math/round (/ ( (Math/pow phi n) (Math/pow ( 1 phi) n)) (Math/sqrt 5)))))
(Rounding counteracts the imprecision of floatingpoint arithmetic introduced through the use of the golden ratio, which is an irrational, ie floatingpoint, number. Note also that the actual performance of Binet’s formula depends on how the language/runtime handles floatingpoint operations and largenumber arithmetic.)
The reason Binet’s formula can compute Fibonacci numbers directly, ie without having to compute preceding numbers, is that it takes advantage of a fascinating underlying connection between the Fibonacci sequence and the golden ratio. I’m not a mathematician, but I understand that, as n
increases, F(n + 1)/F(n)
converges to the golden ratio (where F
denotes the Fibonacci function). For instance, 5/3
is 1.666...
, which is somewhat close to the golden ratio of approximately 1.61803
. When we look at the next pair of numbers in the sequence, 8/5
equals 1.6
, inching closer to the golden ratio. 13/8
is 1.625
, which is closer yet again, and so on. This pattern continues as we progress in the sequence.
Using Binet’s formula, calculating even the 40th number is lightning fast:^{1}
(fibonacci' 40)
; => 102334155
To generate the sequence for the first x
numbers, we can leverage Clojure’s builtin support for sequences:
(>> (range) (map fibonacci') (take x))
Next time you’re in a coding interview, you may wow the interviewer with this improved approach.

On my computer, Binet’s formula works well up to the 75th number, which is
2111485077978050
. For any number greater than that, the formula starts to break down and produces wrong results. This is due to the limitations of floatingpoint arithmetic. We round the resulting number, but when you raisephi
to sufficiently large powers, some fidelity is lost and small initial errors are inevitably amplified before that final step. In those cases, memoized/iterative approaches may be preferable since they rely solely on integer arithmetic. Binet’s formula has its allure due to its O(1) complexity, but optimal use depends on context. ↩
What people are saying