Hacker News new | ask | show | jobs
by nimithryn 2185 days ago
Does this work in practice for large values of n? You will be limited by numerical error in phi.
2 comments

It does not! It fails very early (I tested it once in Python, and it failed on something like F(70) or something) and should not ever be used for practical calculation of Fibonacci numbers.

For small values, the iterative version works just fine. For larger values, there are other methods: one obvious one is using the matrix form of the Fibonacci numbers, which just requires you to take an exponent of a 2x2 matrix (which you can do quickly because of exponentiation by squaring).

The Fibonacci series grows so fast that for "large" values of N you'll need a arbitrary size integer implementation anyway, so at that point you might as well go for a (non-IEEE) arbitrary size float type and get all the significant digits you need.
You’ll still need to compute the digits of Phi though, and then exponentiate that. My intuition is that using ints is still faster.