On May 18, 2:04 am, Wolfram Hinderer <wolfram.hinde...@googlemail.com> wrote: > On 17 Mai, 20:56, geremy condra <debat...@gmail.com> wrote: > > > > > 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 ;). > > I think you can write it even more funny > > def fib(n): > return round(((.5 + .5 * 5 ** .5) ** n - (.5 - .5 * 5 ** .5) ** > n) * 5 ** -.5) > > ;-)
VOW! Tour de Force - Thanks [I am going to trouble some class of students with that :-) ] -- http://mail.python.org/mailman/listinfo/python-list
