Strict Standards: Declaration of action_plugin_importoldindex::register() should be compatible with DokuWiki_Action_Plugin::register($controller) in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/lib/plugins/importoldindex/action.php on line 8
Strict Standards: Declaration of action_plugin_include::register() should be compatible with DokuWiki_Action_Plugin::register($controller) in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/lib/plugins/include/action.php on line 140
Strict Standards: Declaration of action_plugin_discussion::register() should be compatible with DokuWiki_Action_Plugin::register($controller) in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/lib/plugins/discussion/action.php on line 955
Strict Standards: Declaration of action_plugin_blog::register() should be compatible with DokuWiki_Action_Plugin::register($controller) in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/lib/plugins/blog/action.php on line 154
Strict Standards: Declaration of action_plugin_importoldchangelog::register() should be compatible with DokuWiki_Action_Plugin::register($controller) in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/lib/plugins/importoldchangelog/action.php on line 157
Deprecated: Assigning the return value of new by reference is deprecated in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/parserutils.php on line 205
Deprecated: Assigning the return value of new by reference is deprecated in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/parserutils.php on line 208
Deprecated: Assigning the return value of new by reference is deprecated in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/parserutils.php on line 389
Deprecated: Assigning the return value of new by reference is deprecated in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/parserutils.php on line 530
Strict Standards: Declaration of cache_instructions::retrieveCache() should be compatible with cache::retrieveCache($clean = true) in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/cache.php on line 291
Deprecated: Function split() is deprecated in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/inc/auth.php on line 154
Strict Standards: Only variables should be passed by reference in /freeola/users/0/0/sr0193000/htdocs/dokuwiki/doku.php on line 71
====== Fibonacci Generator 2006 ======
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.
===== Description =====
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
===== The Source Code =====
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"
===== Example of Use =====
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''
===== Assumptions =====
None, but for large Fibonacci indices, the computer may crash from running out of memory or produce a segmentation fault.
--- //[[nex@n-e-x.co.uk|Nexami Engeo]] 2007/07/06 11:19//
~~DISCUSSION~~