sturlamolden wrote: > def fibo(n): > while 1: > try: > return fibo.seq[n] > except AttributeError: > fibo.seq = [0, 1, 1] > except IndexError: > fibo.seq.append( fibo.seq[-2] + fibo.seq[-1] )
I really like this formulation. However, its memory consumption is proportional to the input number. On a system with one gigabyte of RAM, it computes the Fibonacci number of 100000 in about four seconds. However, trying to compute 200000, the machine swaps madly, and the Python interpreter DOSes the Linux kernel solid, making the system unresponsive. :-| If all that cache is not reused, building it may be avoided by appending the following two lines to the above function: fibo.seq.pop(0) n -= 1 With this addition, the above system manages to compute the Fibonacci number of 1000000 (one million) in about 190 seconds. :-) > This is 6 orders of magnitude faster than Congiano's benchmark. That > is a speed up by a factor of a million. That's really besides the point. Nice OT, anyway. ;-) -- Nicola Larosa - http://www.tekNico.net/ AtomPub sits in a very strange place, as it has the potential to disrupt half a dozen or more industry sectors, such as, Enterprise Content Management, Blogging, Digital/Desktop Publishing and Archiving, Mobile Web, EAI/WS-* messaging, Social Networks, Online Productivity tools. -- Bill de hÓra, July 2007 -- http://mail.python.org/mailman/listinfo/python-list