Welcome, guest | Sign In | My Account | Store | Cart

Fibonacci Object (Python recipe) by Leandro Mariano Lopez
ActiveState Code (http://code.activestate.com/recipes/128711/)

A simple object to compute Fibonacci numbers. Object methods return the nth Fibonacci number, return list first n Fibonacci numbers and list from F(k) to F(n) numbers. In a future I hope to add more functions closely related with applications of Fibonacci Numbers

Python, 50 lines
Download
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
from math import sqrt, pow, floor
from __future__ import generators

class Fibonacci:
    """A simple class which brings functions to calculate Fibonacci numbers
    and make operations between them"""

    def __init__(self):
        self.Phi    = (1 + sqrt(5))/2
        self.PhiP   = (1 - sqrt(5))/2
        self.rs5    = 1/sqrt(5)
        self.succ   = self.unboundedGenerator()

    def __call__(self, n=-1):
        if n == -1:
            return self.next()
        return self.nth(n)

    def next(self):
        """Next Fibonacci number in the sucesion"""
        return self.succ.next()

    def nth(self, n):
        """Calculate the nth Fibonacci Number by formula. Doesn't work for n > 1474"""
        return floor(self.rs5 * (pow(self.Phi, n) - pow(self.PhiP, n)))

    def list(self, k, n):
        """Returns a list from Fibonacci(k) to Fibonacci(n) numbers"""
        return [ self.nth(i) for i in range(k, n + 1) ]

    def first(self, n):
        """Returns a list with the first n Fibonacci numbers"""
        g = self.generator(n)
        return [ g.next() for i in range(n) ]

    def unboundedGenerator(self):
        """Unbounded Fibonacci generator"""
        thisnum, nextnum = 0, 1L
        while 1:
            yield thisnum
            thisnum, nextnum = nextnum, thisnum + nextnum
        return

    def generator(self, n):
        """n-Bounded Fibonacci generator"""
        thisnum, nextnum = 0, 1L
        for i in range(n + 1):
            yield thisnum
            thisnum, nextnum = nextnum, thisnum + nextnum
        return

I've developed this object 'cause I'm learning Python as a hobbie and Algebra at college, so it's useful to me :-)

Known bugs: Fibonacci.nth(1474) is the last number that I can calculate in this poor little AMD K6 with Windows ME and 64 Mb, Fibonacci.nth(1475) throws an arithmetic overflow

Fibonacci Numbers, the Golden section and the Golden String http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fib.html

Tags: algorithms

6 comments

Justin Shaw 21 years, 11 months ago  # | flag

Try *. Fun project! I prefer x * y in place of pow(x, y) your milage may vary.

Leandro Mariano Lopez (author) 21 years, 11 months ago  # | flag

I've tried it... ... but I haven't seen any changes :\

Anyway, thanks for yor comments... I kept with ** instead of pow :)

Regards

inkel

Robert Kimble 21 years, 8 months ago  # | flag

The problem is with floating point numbers. Your problem is the limitation of floating point numbers, not your machine. You could get around this by keeping all your calculations as integers and letting Python's "big number" arithmetic do its thing. You're better off if you just calculate the first n Fibonacci numbers and then report the nth one as your result.

Thunder Peuk 21 years, 6 months ago  # | flag

Why can i calculate even the 100000th fib-number? I just made a simple for, in stead of that ugly code and whats the result: it takes me 2 sec for the calculation of the 100000th fib-number s... where is the limit???

Josiah Carlson 19 years, 7 months ago  # | flag

Or you can do it the right way... While iterating through all values 1...n to generate the nth

fibonacci number via DP is reasonably fast, it can be done even

faster.

def dfib(n):
    if  2 >= n:
        return 1
    i, j = 1, 1
    for _ in xrange(n-2):
        i,j = i+j, i
    return i


>>> t = time.clock();C = dfib(100000);time.clock()-t

4.1060637595001026

def fibo(n):
    if 2 >= n:
        return 1
    t = 1
    while n >= t:
        t *= 2
    t = int(t/4)
    i, j, k = 1, 1, 0
    while t > 0:
        B = j*j
        j *= i+k
        i = i*i + B
        k = k*k + B
        if n&t:
            k = j
            j = i
            i = j+k
        t = int(t/2)
    return j


>>> t = time.clock();B = fibo(100000);time.clock()-t

0.079098041790302887

>>> t = time.clock();B = fibo(1000000);time.clock()-t

2.6970709964534763

>>> len(hex(B))

173564

With an n much larger than 1,000,000 we start running into the

inefficiencies of large integer multiplication.

Yair Chuchem 19 years, 1 month ago  # | flag

Way ineffiecient. If you look into the algorithm's complexity you'll find out that the algebraic solution is by no means more efficient than the plain simple series development algorithm.