On Mon, Mar 23, 2015 at 4:53 PM, Terry Reedy <tjre...@udel.edu> wrote: > Iteration with caching, using a mutable default arg to keep the cache > private and the function self-contained. This should be faster. > > def fib(n, _cache=[0,1]): > '''Return fibonacci(n). > > _cache is initialized with base values and augmented as needed. > ''' > for k in range(len(_cache), n+1): > _cache.append(_cache[k-2] + _cache[k-1]) > return _cache[n] > > print(fib(1), fib(3), fib(6), fib(5)) > # 1 2 8 5
Iteration in log space. On my desktop, this calculates fib(1000) in about 9 us, fib(100000) in about 5 ms, and fib(10000000) in about 7 seconds. def fib(n): assert n >= 0 if n == 0: return 0 a = b = x = 1 c = y = 0 n -= 1 while True: n, r = divmod(n, 2) if r == 1: x, y = x*a + y*b, x*b + y*c if n == 0: return x b, c = a*b + b*c, b*b + c*c a = b + c >>> list(map(fib, range(15))) [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377] -- https://mail.python.org/mailman/listinfo/python-list