Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #87866 > unrolled thread

Re: fibonacci series what Iam is missing ?

Back to article view | Back to comp.lang.python

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: fibonacci series what Iam is missing ? Ian Kelly <ian.g.kelly@gmail.com> - 2015-03-23 23:20 -0600
    Re: fibonacci series what Iam is missing ? Rustom Mody <rustompmody@gmail.com> - 2015-03-23 23:20 -0700
      Re: fibonacci series what Iam is missing ? Rustom Mody <rustompmody@gmail.com> - 2015-03-23 23:28 -0700
        Unicode magic (was fibonacci series what Iam is missing ?) Rustom Mody <rustompmody@gmail.com> - 2015-03-23 23:33 -0700
      Re: fibonacci series what Iam is missing ? Ian Kelly <ian.g.kelly@gmail.com> - 2015-03-24 08:23 -0600
        Re: fibonacci series what Iam is missing ? CHIN Dihedral <dihedral88888@gmail.com> - 2015-03-24 10:22 -0700

#87866 — Re: fibonacci series what Iam is missing ?

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]

[toc] | [next] | [standalone]

#87869

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?

[toc] | [prev] | [next] | [standalone]

#87870

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ₙ₊₁)²

[toc] | [prev] | [next] | [standalone]

#87871 — Unicode magic (was fibonacci series what Iam is missing ?)

On Tuesday, March 24, 2015 at 11:58:53 AM UTC+5:30, Rustom Mody wrote:
> f₂ₙ = (fₙ)² + 2fₙ₋₁fₙ
> f₂ₙ₊₁ = (fₙ)² + (fₙ₊₁)²

Is there some unicode magic which makes

fₙ² which makes the 2 appear as superscript on the f rather than ahead of the n?

[toc] | [prev] | [next] | [standalone]

#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.

[toc] | [prev] | [next] | [standalone]

#87888

On Tuesday, March 24, 2015 at 10:24:59 PM UTC+8, Ian wrote:
> 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.

Well, solving a  homogeneous difference equation of 2 degrees 
and generating the solution sequence 
for a particular one like the Finbnaci series is a good programming practice.

A more general programming practice 
is to generate the solution series 
of an arbitrary   homogeneous 
difference euqation of integer coefficients when a real or complex solution does exist.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web