Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!newsfeed.xs4all.nl!newsfeed1.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <meq5i2$53s$1@ger.gmane.org>
References: <CACT3xuVF-MOVQK5wSorRSAfpAQEXvS7QsqarACVZKXsQ0bxzpQ@mail.gmail.com> <CAPTjJmrRv+DQGpzdY5te-vk_u9p5AzWYQ-6B=m1knPoaXpRmRQ@mail.gmail.com> <55105EF4.2070805@davea.name> <meq5i2$53s$1@ger.gmane.org>
From: Ian Kelly <ian.g.kelly@gmail.com>
Date: Mon, 23 Mar 2015 23:20:08 -0600
Subject: Re: fibonacci series what Iam is missing ?
To: Python <python-list@python.org>
Content-Type: text/plain; charset=UTF-8
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.93.1427174452.10327.python-list@python.org>
Lines: 40
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:87866

On Mon, Mar 23, 2015 at 4:53 PM, Terry Reedy <tjreedy@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]