Dennis Hackethal’s Blog

My blog about philosophy, coding, and anything else that interests me.

Published · 2-minute read

A Better Way to Generate the Fibonacci Sequence

The Fibonacci sequence is well-known 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 nth 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)))

In other words, for any n greater than 1, we compute the nth 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 nth 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 sub-invocations, 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 non-recursive, indeed non-iterative, 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 floating-point arithmetic introduced through the use of the golden ratio, which is an irrational, ie floating-point, number. Note also that the actual performance of Binet’s formula depends on how the language/runtime handles floating-point operations and large-number 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 built-in 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.

  1. 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 floating-point arithmetic. We round the resulting number, but when you raise phi 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. 


There is 1 reference to this post in:

What people are saying

What are your thoughts?

You are responding to comment #. Clear


Markdown supported. cmd + enter to comment. Your comment will appear upon approval. You are responsible for what you write. Terms, privacy policy
This small puzzle helps protect the blog against automated spam.