4 ms·
Does this work in practice for large values of n? You will be limited by numerical error in phi.
by nimithryn 6y ago
Does this work in practice for large values of n? You will be limited by numerical error in phi.
- WJW 6y agoThe 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.
- nimithryn 6y agoYou’ll still need to compute the digits of Phi though, and then exponentiate that. My intuition is that using ints is still faster.
- OskarS 6y agoIt 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).