Path: csiph.com!usenet.pasdenom.info!news.franciliens.net!fdn.fr!usenet-fr.net!nerim.net!novso.com!newsfeed.xs4all.nl!newsfeed3a.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <8a6dcb51-250d-4abc-abc9-68798f07af86@googlegroups.com>
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> <mailman.93.1427174452.10327.python-list@python.org> <8a6dcb51-250d-4abc-abc9-68798f07af86@googlegroups.com>
From: Ian Kelly <ian.g.kelly@gmail.com>
Date: Tue, 24 Mar 2015 08:23:29 -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.103.1427207059.10327.python-list@python.org>
Lines: 62
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:87885

On Tue, Mar 24, 2015 at 12:20 AM, Rustom Mody <rustompmody@gmail.com> wrote:
> On Tuesday, March 24, 2015 at 10:51:11 AM UTC+5:30, Ian wrote:
>> 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?

It's essentially the same matrix recurrence that Gregory Ewing's
solution uses, but without using numpy (which doesn't support
arbitrary precision AFAIK) and with a couple of optimizations.

The Fibonacci recurrence can be expressed using linear algebra as:

F_1 = [ 1 0 ]

T = [ 1 1 ]
    [ 1 0 ]

F_(n+1) = F_n * T

I.e., given that F_n is a vector containing fib(n) and fib(n-1),
multiplying by the transition matrix T results in a new vector
containing fib(n+1) and fib(n). Therefore:

F_n = F_1 * T ** (n-1)

The code above evaluates this expression by multiplying F_1 by powers
of two of T until n-1 is reached. x and y are the two elements of the
result vector, which at the end of the loop are fib(n) and fib(n-1).
a, b, and c are the three elements of the (symmetric) transition
matrix T ** p, where p is the current power of two.

The last two lines of the loop updating a, b, and c could equivalently
be written as:

a, b, c = a*a + b*b, a*b + b*c, b*b + c*c

A little bit of algebra shows that if a = b + c before the assignment,
the equality is maintained after the assignment (in fact the elements
of T ** n are fib(n+1), fib(n), and fib(n-1)), so the two
multiplications needed to update a can be optimized away in favor of a
single addition.