Finding Fibonacci numbers using linear algebra | Hacker News Reader

Finding Fibonacci numbers using linear algebra

gitlab.com

32 pointskodemartin12 comments

This is really a derivation of the Binet formula for Fibonacci numbers: that u_n = (phi^n - (-phi)^n) / sqrt(5), where phi is the golden ratio (1 + sqrt(5))/2.

So the phi number is an eigenvalue?

A similar neat O(log(n)) solution https://kukuruku.co/post/the-nth-fibonacci-number-in-olog-n/

The first chapter of SICP also has a similar (but not identical) O(log(n)) algorithm in the excercises. Fun stuff.

n^th Fibonacci number requires O(n) bits. So, saying the solution is O(log(n)) is kinda not true. I mean there cannot be a o(n) algorithm for computing decimal representation of n^th fibonacci number.

As always, it depends on your computational model. People are awful at specifying a model, in other words it's unclear what's even being stated.

You can compute the nth fibonacci number in O(lg n) additions and multiplies. That indeed doesn't turn out to be a good model for how long it takes on an actual computer though.

And even if the model is sufficiently specified, the constant factors and lower terms hidden in the O-notationen can be deciding in practice, and are yet usually left out.

The author incorrectly states that the k-th Fibonacci number can be computed in O(1) time. Actually the algorithm he describes runs in O(k) time.

What he states is that if n <= k, then we run in O(1) time, which is correct, because array lookup is O(1):

    return fibonacci[k]

This is the canonical benefit of memoization, further clarified by this quote: "This solution has an O(k) space and time complexity for the first query."

In reality, array lookup is not O(1). It's orders of magnitude faster to do random lookups in an array that fits in L1 cache than one that doesn't. The cache hierachy makes array lookups O(log(n)) or possibly even O(sqrt(n)).

This kind of pedantry doesn't add anything to the discussion. We all know big-O notation is a theoretical abstraction.

I think you overestimate the number of programmers that know this. In my experience, < 50% of programmers know that random array lookups are not constant time in practice.

I mean they would be able to deduce it, but they just never made the connection.

Reply on news.ycombinator.com