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

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

Faster Recursive Fibonacci Numbers

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

Contents

  Faster Recursive Fibonacci Numbers RJB <rbotting@csusb.edu> - 2011-05-17 08:50 -0700
    Re: Faster Recursive Fibonacci Numbers Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-17 10:23 -0600
    Re: Faster Recursive Fibonacci Numbers rusi <rustompmody@gmail.com> - 2011-05-17 09:25 -0700
    Re: Faster Recursive Fibonacci Numbers rusi <rustompmody@gmail.com> - 2011-05-17 09:36 -0700
      Re: Faster Recursive Fibonacci Numbers geremy condra <debatem1@gmail.com> - 2011-05-17 10:02 -0700
        Re: Faster Recursive Fibonacci Numbers Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2011-05-17 20:19 +0300
          Re: Faster Recursive Fibonacci Numbers geremy condra <debatem1@gmail.com> - 2011-05-17 11:56 -0700
            Re: Faster Recursive Fibonacci Numbers Wolfram Hinderer <wolfram.hinderer@googlemail.com> - 2011-05-17 14:04 -0700
              Re: Faster Recursive Fibonacci Numbers geremy condra <debatem1@gmail.com> - 2011-05-17 14:59 -0700
              Re: Faster Recursive Fibonacci Numbers rusi <rustompmody@gmail.com> - 2011-05-17 21:43 -0700
        Re: Faster Recursive Fibonacci Numbers Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-19 22:47 +0000
          Re: Faster Recursive Fibonacci Numbers Chris Angelico <rosuav@gmail.com> - 2011-05-20 09:37 +1000
            Re: Faster Recursive Fibonacci Numbers Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-20 05:58 +0000
              Re: Faster Recursive Fibonacci Numbers Chris Angelico <rosuav@gmail.com> - 2011-05-20 16:06 +1000
                Re: Faster Recursive Fibonacci Numbers harrismh777 <harrismh777@charter.net> - 2011-05-20 01:26 -0500
                  Re: Faster Recursive Fibonacci Numbers Chris Angelico <rosuav@gmail.com> - 2011-05-20 16:54 +1000
                    Re: Faster Recursive Fibonacci Numbers Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-20 17:07 +0000
                      Re: Faster Recursive Fibonacci Numbers geremy condra <debatem1@gmail.com> - 2011-05-20 11:43 -0700
                      Re: Faster Recursive Fibonacci Numbers Chris Angelico <rosuav@gmail.com> - 2011-05-21 10:44 +1000
                Re: Faster Recursive Fibonacci Numbers Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2011-05-21 20:49 +1200
              Re: Faster Recursive Fibonacci Numbers Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-20 01:26 -0600
              Re: Faster Recursive Fibonacci Numbers Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-20 01:32 -0600
                Re: Faster Recursive Fibonacci Numbers SigmundV <sigmundv@gmail.com> - 2011-05-20 03:53 -0700
          Re: Faster Recursive Fibonacci Numbers geremy condra <debatem1@gmail.com> - 2011-05-19 17:03 -0700
    Re: Faster Recursive Fibonacci Numbers Raymond Hettinger <python@rcn.com> - 2011-05-24 16:44 -0700

Page 2 of 2 — ← Prev page 1 [2]

#5835

On Thu, May 19, 2011 at 11:58 PM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> Sure, which is why the above fib() function will become increasing
> inaccurate beyond some given n, by memory about n=71 or so. Er, at least
> the fib() function that *was* above until you deleted most of it :)
>
> If you want an *accurate* fib() function using exponentiation of φ, you
> need arbitrary precision non-integers.

This seems to work for arbitrary n, although I only tested it out to
about n=2000.

from decimal import Decimal, localcontext
from math import sqrt

def fib(n):
    if n <= 70:
        return fib_float(n)
    else:
        return fib_decimal(n)

phi_float = (1 + sqrt(5)) / 2
def fib_float(n):
    numerator = (phi_float ** n) - (1 - phi_float) ** n
    denominator = sqrt(5)
    return int(round(numerator / denominator))

def fib_decimal(n):
    with localcontext() as ctx:
        ctx.prec = n // 4 + 1
        sqrt_5 = Decimal('5').sqrt()
        phi = (1 + sqrt_5) / 2
        numerator = (phi ** n) - (1 - phi) ** n
        return int((numerator / sqrt_5).to_integral_value())

Cheers,
Ian

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

#5836

2011/5/20 Ian Kelly <ian.g.kelly@gmail.com>:
> def fib_decimal(n):
>    with localcontext() as ctx:
>        ctx.prec = n // 4 + 1
>        sqrt_5 = Decimal('5').sqrt()
>        phi = (1 + sqrt_5) / 2
>        numerator = (phi ** n) - (1 - phi) ** n
>        return int((numerator / sqrt_5).to_integral_value())

Note that I believe this is O(n) since the necessary precision grows
linearly with n.

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

#5848

There is a nice matrix representation of consecutive Fibonacci
numbers: [[1, 1], [1, 0]] ** n = [[F_n+1, F_n], [F_n, F_n-1]]. Using
the third party mpmath module, which uses arbitrary precision floating
point arithmetic, we can calculate the n'th Fibonacci number for an
arbitrary n as follows:

import mpmath
A = mpmath.matrix([[1, 1], [1, 0]])
F = A ** n

The n'th Fibonacci number is then found as the elements [0, 1] and [1,
0] in the matrix F.

This is more expensive than the formula involving the golden ratio,
but I like the compact representation.

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

#5798

On Thu, May 19, 2011 at 3:47 PM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> On Tue, 17 May 2011 10:02:21 -0700, geremy condra wrote:
>
>> or O(1):
>>
>> φ = (1 + sqrt(5)) / 2
>> def fib(n):
>>     numerator = (φ**n) - (1 - φ)**n
>>     denominator = sqrt(5)
>>     return round(numerator/denominator)
>
> I'd just like to point out that, strictly speaking, it's only O(1) if you
> assume that exponentiation is O(1). Computer scientists often like to
> make this simplifying assumption, and it might even be true for floats,
> but for long ints and any numeric data types with unlimited precision, it
> won't be.

Great point, and something I should have paid attention to. Thanks.

Geremy Condra

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

#6185

On May 17, 8:50 am, RJB <rbott...@csusb.edu> wrote:
> I noticed some discussion of recursion..... the trick is to find a
> formula where the arguments are divided, not decremented.
> I've had a "divide-and-conquer" recursion for the Fibonacci numbers
> for a couple of years in C++ but just for fun rewrote it
> in Python.  It was easy.  Enjoy.  And tell me how I can improve it!
>
> def fibo(n):
>         """A Faster recursive Fibonaci function
> Use a formula from Knuth Vol 1 page 80, section 1.2.8:
>            If F[n] is the n'th Fibonaci number then
>                    F[n+m] = F[m]*F[n+1] + F[m-1]*F[n].
>   First set m = n+1
>    F[ 2*n+1 ] = F[n+1]**2 + F[n]*2.
>
>   Then put m = n in Knuth's formula,
>            F[ 2*n ] = F[n]*F[n+1] + F[n-1]* F[n],
>    and replace F[n+1] by F[n]+F[n-1],
>            F[ 2*n ] = F[n]*(F[n] + 2*F[n-1]).
> """
>         if n<=0:
>                 return 0
>         elif n<=2:
>                 return 1
>         elif n%2==0:
>                 half=n//2
>                 f1=fibo(half)
>                 f2=fibo(half-1)
>                 return f1*(f1+2*f2)
>         else:
>                 nearhalf=(n-1)//2
>                 f1=fibo(nearhalf+1)
>                 f2=fibo(nearhalf)
>                 return f1*f1 + f2*f2
>
> RJB the Lurkerhttp://www.csci.csusb.edu/dick/cs320/lab/10.html

There are many ways to write this function.  The one I like shows-off
a general purpose dynamic programming technique while staying *very*
close to a common textbook definition of a fibonacci number:

@functools.lru_cache()
def fibo(n):
    return 1 if n < 2 else fibo(n-1) + fibo(n-2)

Raymond

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

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

csiph-web