Table of Contents

A fairly acute Fibonacci sequence generator written in the Python programming language. This is a conversion of my earlier Ada Fibonacci Generator. In fact, this is now the sixth conversion of that program.

Just in case anyone wonders why I keep writing Fibonacci programs, I like to attempt it in any new language I learn as I consider it to be just complicated enough for me to find it tricky, but not so complicated that it will frustrate me and put me off the new language. I have actually produced two versions of this program which have one large difference in their implementation. Python, being such a super language, doesn't really need me to deal with the Big Integer representation because Python takes care of this itself. In fact, Python's method of dealing with them must be better than mine since the Python interpreted version actually runs faster than my C compiled version. However, Python's method of representing large numbers (whatever that may be) is not infinite. There is still a 'largest number'. This is the one advantage of my earlier implementations which can go until you actually fill all the RAM on your machine (sometimes causing the computer to crash). Therefore, I have produced two versions of the Python program: One which uses Python's own methods for dealing with large numbers, and one which uses my method of dealing with large numbers. You will most likely find that my version is MUCH slower than Python's. However, it can (in theory) handle larger Fibonacci indices. So it's up to you which one you think is more useful.

The only oddity of implementing the program in Python is that Python has a default recursion depth is of 1000 (usually). For my Fib function that just isn't deep enough for the larger indices. But luckily you can just change it to a larger number, which the program bases on the numbers entered. Another fun little feature of Python is that when it deals with the large numbers itself and a number is too big, it returns a segmentation fault. This is because it doesn't want the Python interpreter to be allowed to hang your computer, and frankly that is a good thing.

I started learning Python at 10 o'clock and had the first version of this program (the one where Python deals with the large numbers) fully finished as you now see it by 3 o'clock. This is by far the quickest turn around of the cycle that I have yet achieved, and I have to say it's because Python is so damn groovy. If you haven't learned Python, I seriously urge you to give it a go. I have so far only written this one program, but I haven't found anything in the language yet that I thought was bad. In fact, the subtle differences between this language and others seems to make my programming much quicker and easier. I guess the code itself doesn't look as pretty when it's laid out, but it is still easier to read than a lot of languages by getting a better balance between good looking code and easier code to produce. It doesn't feel bogged down by what is, frankly, unnecessary use of symbols.

Anyway, that's enough about Python, here is yet another Fib program.

The Fibonacci algorithm was invented by an Italian mathematician (Fibonacci) to predict rabbit growth. A lot of assumptions are made, some of which are a bit sillier than others:

Assume that you start with two rabbits.

Assume that once a rabbit is three years old, it is capable of mating.

Assume that all rabbits capable of mating will in fact mate.

Assume that every time two rabbits mate, one offspring is produced without failure; no more, no less.

Assume rabbits can only produce one 'litter' a year.

Assume that there is an almost equal number of male and female rabbits.

Assume rabbits never die.

Anyway, the interesting thing about the Fibonacci algorithm is that it can be implemented recursively, and the numbers get big VERY quickly. The most basic way of expressing the algorithm is shown below:

fib[n] = fib[n-1] + fib[n-2]

where fib[1] = 1, fib[2] = 1

You can view all the source code of the program below.

**fib.py (version 1)**:

#!/usr/bin/python # Filename: fib.py '''Fast-Fib program for calculating Fibonacci numbers. Program Title : Fast-Fib Version 0.9 Author : nex Date Last Modified : 20th January 2006 Description : This program takes in two integers from standard input and uses them as indices to calculate Fibonacci numbers from the lower to upper index. State of Program : The program has worked correctly for all test data. ''' # We need to import the sys module to change the # default recursion limit. import sys def helpFib(n, k, fibk, fibk1): '''Helper function for main fib function. All the clever stuff is done here. helpFib is used to speed up the fib function by preventing repeated calculations. In truth, I only ever briefly understood how this works. I did not come up with it and I understood it just long enough to program it in the original Ada version of this program. ''' if n == k: return fibk else: return helpFib(n, (k+1), (fibk + fibk1), fibk) def fib(x): '''Fib function for calculating Fibonacci numbers. The Fib function calculates the value of the Fibonacci number with index x. ''' # For values less than 3, the Fib number is 1 if x < 3: return 1 # For Fibonacci indices smaller than 21, use a # simple recursive Fib function as this produces # the most optimal performance (this may not be # true for Python - not really tested it yet) else: if x < 21: return fib(x-1) + fib(x-2) # For indices larger than 20, use the # helpFib function to speed things up. else: return helpFib(x, 1, 1, 0) def verify(n): '''Verify results of fib function. The verify procedure tests to see if the Fibonacci number calculated is accurate by trying to find it by a different algorithm (which, incidentally, uses the same algorithm as the `main program` as it were) and then comparing it to the originally found value. ''' if n != 2: test = fib(n) test = test + test + test if test == (fib(n+2) + fib(n-2)): return 1 else: return 0 else: return 1 # Get Lower and Upper values to run algorithm from and # to. LowFib = int(raw_input("Enter low number: ")) HiFib = int(raw_input("Enter high number: ")) # Check that Lower and Upper values are positive if LowFib < 1 or HiFib < 1: print "Fibonacci Indices must be positive integers greater than zero." else: # Check that the Lower Limit is less than the # Upper Limit and swap if appropriate. if LowFib > HiFib: Swap = LowFib LowFib = HiFib HiFib = Swap # We need to change the recursion limit as for large # vales we will be going quite a bit deeper than the # default of 1000. However, this default is fine for # and index of one. if HiFib > 1: sys.setrecursionlimit(HiFib*8) # Find, validate and output requested Fibonacci # sequence for i in range(LowFib, HiFib+1): print "Fib(" + str(i) + ") = ", print fib(i), if verify(i): print " Valid" else: print " Invalid"

**fib.py (version 2)**:

#!/usr/bin/python # Filename: fib.py '''Fast-Fib program for calculating Fibonacci numbers. Program Title : Fast-Fib Version 0.9 (version 2) Author : nex Date Last Modified : 8th August 2006 Description : This program takes in two integers from standard input and uses them as indices to calculate Fibonacci numbers from the lower to upper index. State of Program : The program has worked correctly for all test data. ''' # We need to import the sys module to change the # default recursion limit. import sys # We need to import the copy module to do deep # copying of objects. import copy class BigInt: '''The BigInt class deals with large integer representation.''' class BigIntList: '''The BigIntList is a private class of BigInt.''' def __init__(self, v): '''Initializes the BigIntList`s data.''' self.val = v self.next = None self.prev = None def __init__(self, v = None): '''Initializes the BigInt`s data.''' # This `if` statement gets around Python only # allowing one constructor per class. if v == None: self.head = None self.tail = None else: self.head = self.BigIntList(v) self.tail = self.head def add(self, y): '''Calculates this + y (both of type `BigInt`) and returns as type `BigInt`. This method is specifically designed for the BigInt type of this program.''' # Clear variables of data. c = s = p = q = 0 # Initialise variables. xTemp = copy.deepcopy(self) yTemp = copy.deepcopy(y) r = BigInt() # If `this` or y have no values, return r (which will equal null). if ((self.head != None) or (y.head != None)): # If there is still data in the current xTemp or yTemp or # there is a carry, get intermediate values for use in equations. while ((xTemp.head != None) or (yTemp.head != None) or (c == 1)): if ((xTemp.head == None) and (yTemp.head != None)): q = yTemp.head.val yTemp.head = yTemp.head.next p = 0 elif ((xTemp.head != None) and (yTemp.head == None)): p = xTemp.head.val xTemp.head = xTemp.head.next q = 0 elif ((xTemp.head == None) and (yTemp.head == None)): p = q = 0 else: p = xTemp.head.val xTemp.head = xTemp.head.next q = yTemp.head.val yTemp.head = yTemp.head.next # Use intermediate values to calculate sum and carry. if (r.head == None): s = ((p + q) % 1000) c = ((p + q) / 1000) else: s = ((p + q + c) % 1000) c = ((p + q + c) / 1000) # Add new nodes containing correct values to doubly linked # list. if (r.head == None): r.head = self.BigIntList(s) r.tail = r.head else: r.tail.next = self.BigIntList(s) rTemp = copy.deepcopy(r) r.tail = r.tail.next r.tail.prev = rTemp.tail return r def isEqual(self, y): '''Returns the boolean expression `x = y`, where x = `this`, and y and x are both BigInt objects.''' xTemp = copy.deepcopy(self) yTemp = copy.deepcopy(y) # Tests all possible cases in which x == y (or x != y), # using recursion to call all nodes. if ((xTemp.head != None) and (yTemp.head != None)): if (xTemp.head.val == yTemp.head.val): xTemp.head = xTemp.head.next yTemp.head = yTemp.head.next return (xTemp.isEqual(yTemp)) else: return 0 elif ((xTemp.head != None) and (yTemp.head == None)): return 0 elif ((xTemp.head == None) and (yTemp.head != None)): return 0 elif ((xTemp.head == None) and (yTemp.head == None)): return 1 else: return 0 def __str__(self): '''Outputs the value of the `BigInt` type, `x`, to standard output.''' xTemp = copy.deepcopy(self) retString = str() if (self.tail != None): # Extra zeros will need to be printed if current node value # is less than 100. if (self.tail.next != None): if (self.tail.val < 100): if (self.tail.val < 10): retString = retString + "00" else: retString = retString + "0" # Output current node value then recursively call other node # values for output. retString = retString + str(self.tail.val) xTemp.tail = self.tail.prev return (retString + str(xTemp)) else: return retString def helpFib(n, k, fibk, fibk1): '''Helper function for main fib function. All the clever stuff is done here. helpFib is used to speed up the fib function by preventing repeated calculations. In truth, I only ever briefly understood how this works. I did nt come up with it and I understood it just long enough to program it in the original Ada version of this program. ''' if n == k: return fibk else: return helpFib(n, (k+1), fibk.add(fibk1), fibk) def fib(x): '''Fib function for calculating Fibonacci numbers. The Fib function calculates the value of the Fibonacci number with index x. ''' one = BigInt(1) zero = BigInt(0) # For values less than 3, the Fib number is 1 if x < 3: return one # For Fibonacci indices smaller than 21, use a # simple recursive Fib function as this produces # the most optimal performance (this may not be # true for Python - not really tested it yet) else: if x < 21: return (fib(x-1)).add(fib(x-2)) # For indices larger than 20, use the # helpFib function to speed things up. else: return helpFib(x, 1, one, zero) def verify(n): '''Verify results of fib function. The verify procedure tests to see if the Fibonacci number calculated is accurate by trying to find it by a different algorithm (which, incidentally, uses the same algorithm as the `main program` as it were) and then comparing it to the originally found value. ''' if n != 2: test = fib(n) test = (test.add(test)).add(test) if test.isEqual((fib(n+2)).add(fib(n-2))): return 1 else: return 0 else: return 1 # Get Lower and Upper values to run algorithm from and # to. LowFib = int(raw_input("Enter low number: ")) HiFib = int(raw_input("Enter high number: ")) # Check that Lower and Upper values are positive if LowFib < 1 or HiFib < 1: print "Fibonacci Indices must be positive integers greater than zero." else: # Check that the Lower Limit is less than the # Upper Limit and swap if appropriate. if LowFib > HiFib: Swap = LowFib LowFib = HiFib HiFib = Swap # We need to change the recursion limit as for large # vales we will be going quite a bit deeper than the # default of 1000. However, this default is fine for # an index of one. if HiFib > 1: sys.setrecursionlimit(HiFib*8) # Find, validate and output requested Fibonacci # sequence for i in range(LowFib, HiFib+1): print "Fib(" + str(i) + ") = ", print fib(i), if verify(i): print " Valid" else: print " Invalid"

To use the program enter the low number you want the Fibonacci sequence to start from then the high number you want it to finish with.

*Input (each end of line is an 'enter')*:

`4`

600

*Output*:

`Fib(`

*n*) = *fibnumber* Valid *OR* Invalid

Fib(*n + 1*) = *next_fibnumber* Valid *OR* Invalid

None, but for large Fibonacci indices, the computer may crash from running out of memory or produce a segmentation fault.

— *Nexami Engeo 2007/07/06 11:19*

## Discussion