On Fri, 20 May 2011 09:37:59 +1000, Chris Angelico wrote: > On Fri, May 20, 2011 at 8:47 AM, Steven D'Aprano > <steve+comp.lang.pyt...@pearwood.info> wrote: >> On Tue, 17 May 2011 10:02:21 -0700, geremy condra wrote: >> >>> or O(1): >>> >>> φ = (1 + sqrt(5)) / 2 >>> numerator = (φ**n) - (1 - φ)**n >> >> I'd just like to point out that, strictly speaking, it's only O(1) if >> you assume that exponentiation is O(1). Computer scientists often like >> to make this simplifying assumption, and it might even be true for >> floats, but for long ints and any numeric data types with unlimited >> precision, it won't be. >> >> > Python doesn't have arbitrary precision non-integers, does it? So this > is going to be done with floats.
Sure, which is why the above fib() function will become increasing inaccurate beyond some given n, by memory about n=71 or so. Er, at least the fib() function that *was* above until you deleted most of it :) If you want an *accurate* fib() function using exponentiation of φ, you need arbitrary precision non-integers. Nevertheless, at some point you will hit the limit of floats, which thanks to the exponential growth of the Fibonacci sequence won't take that long: it takes roughly 1475 iterations to exceed the range of Python floats. -- Steven -- http://mail.python.org/mailman/listinfo/python-list