On Saturday, March 26, 2011 11:49:02 AM UTC-4, Steven D'Aprano wrote: > > > > def fib(n): > > phi = (5 ** 0.5 + 1) / 2 > > f = (phi ** n - (1 - phi) ** n) / 5 ** 0.5 > > return int(f) > > Have you tried it? > > Unfortunately, with floating point rounding error, that rapidly becomes > inaccurate. It gives: > > >>> fib(72) > 498454011879265 > > compared to the correct value of 498454011879264 (an error of 1) and > rapidly gets worse. It's true that the above formula is correct for real > numbers, but floats are not reals. Unless you have an infinite number of > decimal places, it will be inaccurate.
That's true. If you need more than double precision, obviously it's time to defer to the experts. Here's an O(n) algorithm: http://www.gnu.org/software/gmp/manual/html_node/Fibonacci-Numbers-Algorithm.html This library is wrapped by the gmpy extension module: http://code.google.com/p/gmpy I was just shocked to see 200 MB of memory used up like chump change, and I immediately looked for an alternative. In practice, I prefer to rely on libraries created by specialists who have carefully worked out the best trade-offs for typical use, and puzzled through the algorithms needed to compute that which is so easy to derive on paper (such as my simple little Z-transform derived formula that fails so wonderfully in practice). I'm not a computer scientist; I don't even play one on TV. -- http://mail.python.org/mailman/listinfo/python-list
