Fibonacci in Python

fibonacci.py

#! /usr/bin/env python
from __future__ import division
import sys
import time
import traceback



class TimeoutError(Exception):
    """Exception raised for operations exceeding maximum time"""

    MSG = "Execution time of %g seconds exceeded maximum of %g."

    def __init__(self, elapsed=0, max_time=0):
        self.elapsed  = elapsed
        self.max_time = max_time
        self.msg      = self.MSG % (elapsed, max_time)

    def __str__(self):
        return repr(self.msg)


class Timer:
    """Simple timer class to handle operation timing"""

    time_start   = 0
    time_end     = 0
    time_check   = 0

    def __init__(self, max_time=0, check_marks=False):
        self.max_time = max_time
        self.check_marks = check_marks
        self.start()

    def start(self):
        self.time_start = time.clock()

    def end(self):
        self.time_end = time.clock()
        return self.check(self.time_end)

    def check(self, current=0):
        if  self.check_marks:
            sys.stdout.write(".") # just for fun

        self.time_check = current or time.clock()
        elapsed = self.time_check - self.time_start
        if self.max_time and elapsed > self.max_time:
            raise TimeoutError(elapsed, self.max_time)
        return elapsed


class Fibonacci:
    """Fibonacci number generator

    Using disk cache to play around with Python
    Using timers to prevent locking up the disk
    Perhaps there is a better way...
    """


    CACHE     = "cache.txt"
    TEMPLATE  = "template.txt"
    MAX_TIME  = 1
    SQRT5     = pow(5, 0.5)

    Name      = "Fibonacci"

    cache_on  = False         # can we use disk cache
    cache     = (0, 0, 0, 0)  # m, n, a, b
    cache_max = 0             # last n on disk


    def __init__(self, cache_on=True):
        if cache_on:
            self.init_cache()
            self.validate_cache()


    def init_cache(self):
        """Test cache read and write, set cache values"""

        F         = None
        readable  = False
        writeable = False
        index     = None
        line      = None

        # try writing
        try:
            with open(self.CACHE, "a") as F:
                writeable = True

        finally:
            F and F.close()

        # try reading
        try:
            with open(self.CACHE) as F:
                readable = True

        finally:
            F and F.close()

        self.cache_on = readable and writeable

        # set values
        if self.cache_on:
            self.read_cache(0)


    def read_cache(self, i):
        """Read cache for line number i

        Returns a tuple
        """

        if not self.cache_on:
            raise Exception("Disk cache is not available")

        F          = None
        index      = None
        line       = None
        m, n, a, b = (0, 0, 0, 0)
        T          = Timer(self.MAX_TIME)

        try:
            with open(self.CACHE) as F:
                for index, line in enumerate(F):
                    if index + 1 == i:
                        break
                    if index % 500 == 0:
                        T.check()

        finally:
            F and F.close()

        if line:
            m, n, a, b = (int(x) for x in line.split(" "))

        if i == 0:
            self.cache = (m, n, a, b)
            self.cache_max = n

        return (m, n, a, b)


    def write_cache(self, i):
        """Write cache to line number i

        Returns a tuple
        """

        if not self.cache_on:
            raise Exception("Disk cache is not available")

        F          = None
        v          = None
        m, n, a, b = self.cache
        T          = Timer(self.MAX_TIME)

        try:
            with open(self.CACHE, "a") as F:
                enum_f = enumerate(self.gen_fibonacci(n, i, a, b))
                for index, v in enum_f:
                    s = " ".join(str(x) for x in v) + "\n"
                    F.write(s)
                    if index % 500 == 0:
                        T.check()

        except TimeoutError as e:
            if v:
                m, n, a, b = v
                self.cache = (m, n, a, b)
                self.cache_max = n
            raise(e)

        finally:
            F and F.close()

        if v:
            m, n, a, b = v
            self.cache = (m, n, a, b)
            self.cache_max = n

        return (m, n, a, b)


    def validate_cache(self):
        """Sanity check"""

        if not self.cache_on:
            raise Exception("Disk cache is not available")

        F          = None
        T          = Timer(15, True)
        last_n     = 0

        try:
            with open(self.CACHE) as F:
                for index, line in enumerate(F):
                    m, n, a, b = (int(x) for x in line.split(" "))
                    if n <= last_n:
                        print "n <= last_n", n, last_n
                        raise ValueError("Bullshit!")
                    else:
                        last_n = n
                    if index % 500 == 0:
                        T.check()

        except ValueError as e:
            F and F.close()
            F = None
            self.clear_cache()
            self.init_cache()

        finally:
            F and F.close()


    def clear_cache(self):
        """Used when validation fails"""

        if not self.cache_on:
            raise Exception("Disk cache is not available")

        F = None

        try:
            with open(self.CACHE, "w") as F:
                pass

        finally:
            F and F.close()


    def gen_fibonacci(self, m, n, a, b):
        """Fibonacci generator

        m is the start of the range
        n is the end of the range
        a is the value at index m - 1
        b is the value at index m

        Returns a tuple
        """

        for i in xrange(m, n):
            if i == 0:
                b, a = 1, 0
            else:
                b, a = a + b, b

            yield (i, i + 1, a, b)


    def get_fibonacci(self, i):
        """Get the Fibonacci number without caching

        Returns a tuple
        """

        T = Timer(self.MAX_TIME)

        enum_f = enumerate(self.gen_fibonacci(0, i, 0, 1))
        for index, v in enum_f:
            if index % 500 == 0:
                T.check()

        m, n, a, b = v
        return (m, n, a, b)


    def fibonacci(self, i):
        """Return the fibonacci number at index i"""

        if self.cache_on:
            if i == self.cache_max:
                # return value currently in self.cache
                m, n, a, b = self.cache
            elif i < self.cache_max:
                # search disk cache for value
                m, n, a, b = self.read_cache(i)
            else:
                # need to generate some values"
                m, n, a, b = self.write_cache(i)
        else:
            m, n, a, b = self.get_fibonacci(i)

        return b


    def binet(self, i):
        """Return the binet approximation of the fibonacci number

        Always returns an int, excepting an OverflowError
        when i > 1474; in that case return self.fibonacci(i)
        """

        try:
            sqrt5 = self.SQRT5
            x = pow((1 + sqrt5) / 2, i)
            y = pow((1 - sqrt5) / 2, i)
            b = int((1 / sqrt5) * (x - y))

        except OverflowError as e:
            b = self.fibonacci(i)

        return b


    def get_template(self):
        """Returns the results template from a text file"""

        F = None

        try:
            with open(self.TEMPLATE) as F:
                s = F.read()
        finally:
            F and F.close()
        return s


    def get_natural(self):
        """Prompt the user to input a natural number"""

        n = 0
        prompt = "Please enter a natural number (0 to exit): "
        notice = "That was not a natural number.  Try again..."

        if not n:
            while True:
                try:
                    print "\n", "*" * 72, "\n"
                    n = int(raw_input(prompt))

                    if n >= 0: break
                    else: raise ValueError

                except ValueError:
                    print notice

        return n


    def test(self, i):
        """Test the class methods

        Time each method and output both the values
        and the difference between them in percent
        """

        T  = Timer()

        T.start()
        v1, t1 = self.binet(i), T.end()

        T.start()
        v2, t2 = self.fibonacci(i), T.end()

        dv = ((v1 - v2) / v2) * 100
        dt = ((t1 - t2) / t2) * 100

        s = self.get_template()
        print "\n", s % (v1, t1, v2, t2, dv, dt)


def trace_error(e):
    """Print the stack trace of an Exception"""

    print "\n", "-" * 72, "\n"
    traceback.print_exc(file = sys.stdout)
    print "\n", "-" * 72, "\n"

LICENSE

Copyright (c) 2011, Matthew Cobbs

Permission is hereby granted, free of charge, to any person obtaining
a copy of this software and associated documentation files (the
"Software"), to deal in the Software without restriction, including
without limitation the rights to use, copy, modify, merge, publish,
distribute, sublicense, and/or sell copies of the Software, and to
permit persons to whom the Software is furnished to do so, subject to
the following conditions:

The above copyright notice and this permission notice shall be included
in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

run.py

#! /usr/bin/env python
from fibonacci import Fibonacci, trace_error



if __name__ == "__main__":

    F = None

    try:
        F  = Fibonacci()

    except Exception as e:
        trace_error(e)

    while F:
        n = F.get_natural()

        if n < 1:
            break

        try:
            F.test(n)

        except Exception as e:
            trace_error(e)

template.txt

**Binet approximation:

%d (%g seconds)

**Fibonacci number:

%d (%g seconds)

**Difference ((B - F) / F):

%g%% value (%g%% time)