fibonacci series what Iam is missing ?
Ian Kelly
ian.g.kelly at gmail.com
Tue Mar 24 01:20:08 EDT 2015
On Mon, Mar 23, 2015 at 4:53 PM, Terry Reedy <tjreedy at 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]
More information about the Python-list
mailing list