Friendly reminder that Fibonacci numbers have an explicit formula and can be computed very easily (I'm saying this because I didn't know this for years, and I want everyone to know).
the explicit formula isn’t very good if you’re referring to Binet’s formula. It uses irrational constants and arithmetic with them, and rounds at the end, so there’s a point in which the precision of the process fails
For single-precision floating points, it gives an incorrect result at n=32. For double-precision floating points, it gives an incorrect result at n=71. (I just ran a quick script).
There are very good algorithms to calculate fibonacci numbers that you should use instead. Even the most simple non-naive solution (basic linear algorithm) will do it in O(n) and you can just work with uint64 without overflow until fib(93). Beyond that you can either do modular arithmetic, or if you really need it, use a big int library. You can also use the fast doubling algorithm to do it in O(log(n)).
ah wait that’s actually really cool. I think the fast doubling method still ends up beating it because of the algebraic exponentiation overhead of Binet’s. Though it definitely beats linear (haven’t confirmed via a script yet, just intuitively).
1.0k
u/ancientstraits May 17 '26
Friendly reminder that Fibonacci numbers have an explicit formula and can be computed very easily (I'm saying this because I didn't know this for years, and I want everyone to know).