On Tue, May 17, 2011 at 10:19 AM, Jussi Piitulainen <jpiit...@ling.helsinki.fi> wrote: > geremy condra writes: > >> or O(1): >> >> φ = (1 + sqrt(5)) / 2 >> def fib(n): >> numerator = (φ**n) - (1 - φ)**n >> denominator = sqrt(5) >> return round(numerator/denominator) >> >> Testing indicates that it's faster somewhere around 7 or so. > > And increasingly inaccurate from 71 on.
Yup. That's floating point for you. For larger values you could just add a linear search at the bottom using the 5f**2 +/- 4 rule, which would still be quite fast out to about 10 times that. The decimal module gets you a tiny bit further, and after that it's time to just use Dijkstra's, like rusi suggested. In any event, I still think this formulation is the most fun ;). Geremy Condra -- http://mail.python.org/mailman/listinfo/python-list
