On Thu, May 19, 2011 at 3:47 PM, 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 >> def fib(n): >> numerator = (φ**n) - (1 - φ)**n >> denominator = sqrt(5) >> return round(numerator/denominator) > > 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.
Great point, and something I should have paid attention to. Thanks. Geremy Condra -- http://mail.python.org/mailman/listinfo/python-list