On Tuesday, March 24, 2015 at 11:50:40 AM UTC+5:30, Rustom Mody wrote: > On Tuesday, March 24, 2015 at 10:51:11 AM UTC+5:30, Ian wrote: > > On Mon, Mar 23, 2015 at 4:53 PM, Terry Reedy 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 > > This is rather arcane! > What are the identities used above?
Seems to be close to these (with some spices added!) f₂ₙ = (fₙ)² + 2fₙ₋₁fₙ f₂ₙ₊₁ = (fₙ)² + (fₙ₊₁)² -- https://mail.python.org/mailman/listinfo/python-list