After learning so much about development in Python, I thought this article would be interesting for readers and to myself…
This is about 5 different ways of calculating Fibonacci numbers in Python
[sourcecode language=”python”]
## Example 1: Using looping technique
def fib(n):
a,b = 1,1
for i in range(n-1):
a,b = b,a+b
return a
print fib(5)
## Example 2: Using recursion
def fibR(n):
if n==1 or n==2:
return 1
return fibR(n-1)+fibR(n-2)
print fibR(5)
## Example 3: Using generators
a,b = 0,1
def fibI():
global a,b
while True:
a,b = b, a+b
yield a
f=fibI()
f.next()
f.next()
f.next()
f.next()
print f.next()
## Example 4: Using memoization
def memoize(fn, arg):
memo = {}
if arg not in memo:
memo[arg] = fn(arg)
return memo[arg]
## fib() as written in example 1.
fibm = memoize(fib,5)
print fibm
## Example 5: Using memoization as decorator
class Memoize:
def __init__(self, fn):
self.fn = fn
self.memo = {}
def __call__(self, arg):
if arg not in self.memo:
self.memo[arg] = self.fn(arg)
return self.memo[arg]
@Memoize
def fib(n):
a,b = 1,1
for i in range(n-1):
a,b = b,a+b
return a
print fib(5)
[/sourcecode]
You may ask, all this is okay, but what’s the best way? Wait for another post on performance of these… Its on the way!
PYTHON ROCKS
nerd
then why are you here John
Here is another way:
fibo=[0,1]
for i in range (50):
fibo.append(fibo[-1]+fibo[-2])
print fibo
i like this method, this is more or less the way i went, because being able to display the whole sequence or the last value only seemed useful to me, so i had it store a list. i added a few failsafes to the code, so you can’t crash your computer with too large of values, and so it doesn’t always print the whole list…but i found it to be useful like this. it is not the most efficient way to calculate just the value, I believe the recursions get to the value faster. this spends way too much resource on indexing, methinks..
You have an error in the function fibR (Example 2). When you recursively call the functions in the return statement, you are calling fib(n-1)+fib(n-2) instead of fibR(n-1)+fibR(n-2). The example script only works because fib(n) has already been defined!
Other than that, excellent job.
Thanks,
Jeff
Agreed! The recursive approach here doesn’t really work
how about
fibo=g.67
a=c67
fbr=(9-8a)
(n-2)
n8-7
works for me 🙂
import math
def C(x,y):
t=math.factorial(x-y)*math.factorial(y)
return math.factorial(x)/t
def fib(n):
i=0
t=0
m=n-1
while (i<n/2.0):
t=t+C(m-i,i)
i=i+1
return t
Python is childs play
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
return n if n < 2 else fib(n-1) + fib(n-2)
In your first memoization example (not the one with decorators) I don’t understand why your hashmap/dict (memo) is not declared globally. Wouldn’t this just instantiate an empty dict every time you call the function? You’re not actually storing any values for reference later since you essentially wipe the data structure every time you call the function.
That’s true, thanks Chris for pointing it out. I just wanted to add a simple example to demonstrate the case, but your suggestion is useful, thanks.
Thanks for the response Chetan, simply moving the dict to the global scope would make memoization technically work for the iterative/looping solution, although that really only improves your runtime on multiple calculations of fib (aka, fib(6) only gets a performance boost if you had explicitly run fib(5) or under previously in the same run of the program.
From my experience with interviews with companies that ask this question, they usually want you to take your recursive function and add memoization to that since it benefits the most from it (relatively that is). You’re actually populating your hash WHILE running fib(5) as opposed to just after the fact.
Example 5, with the memoization decorator, does not take full advantage of the memoization feature. You should combine Example 2’s recursive method inside Example 5’s decorated function, so that calls to fibR(n-1) and fibR(n-2) reuse the previously calculated values in the Memoization instance.
Thanks for your comment 🙂
here is another simple way:
for num in range (15):
fibo = ((1.618033988749895**num) -(1-1.618033988749895)**num) / float (5**0.5)
print fibo
#Another simple method
for num in range (15):
fibo = ((1.618033988749895**num) -(1-1.618033988749895)**num) / float (5**0.5)
print fibo
how about this?
a=c=0
b=1
print 1
while 1:
c=a+b
a=b
b=c
print c
That’s interesting to see the Fibonacci generation using five different approaches. However, mentioning their time complexity would have made more sense for us to observe the effectiveness of each method. None the less, I get to know another way which gives two formulas to find nth Fibonacci Number in O(log n) time.
-> F(n) = [2*F(k-1) + F(k)]*F(k) where n is even and k is n/2.
-> F(n) = F(k)*F(k) + F(k-1)*F(k-1) where n is odd and k is (n + 1)/2.
Good to know Meenakashi, thanks for your comment.
## Example 3: Using generators
yield should be before a,b = b,a+b. Else you are missing 0 as the first output from the next calls
Thanks for your comment Kamakhya, I’m not sure if 0 is part of Fibonacci series.
Your #4 memoization function begins for every function call the entire recursive looping anew.
There is a much more efficient way. That the function stores during the entire session all calculated results.
And if you do sth else and later call the function – the function still has in memory all the previous results.
It is done by this:
# this memoize function returns a new helper function
# which is a closure – so has the memo-dicitonary as a hidden (encapsulated) state.
def memoize(f):
memo = {}
def helper(x):
if x not in memo:
memo[x] = f(x)
return memo[x]
return helper
# this is your example # 1
def fib(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib(n-1) + fib(n-2)
fib = memoize(fib)
# here the magic happens!
# fib is a new helper function which took the fold fib and wraps the memo dicitonary around it
# as a hidden/encapsulated inner state – and if you add new values to it – the values
# stay until the nexa call of the new fib().
# fib(10) # it calculates the first 10 fibonacci numbers – but keeps in memory them all –
# and if you next time call fib(15) – all the values until fib(10) are “remembered”
# and only fib(11) to fib(14) calculated in addition by the recursive (now inner) fib() function!
# so this is a far more efficient way than your #4
# because with your memoize(fib, 10) – all the fib(1) to fib(10) are calculated on the way.
# and if you next time call memoize(fib, 15), then it has to calculate fib(1) to fib(15) anew.
# Just that during this new round just repetitive calculations of same fib(n) are avoided.
That is the difference if you create a closure – you get an encapsulated hidden inner state
which the new fib() carries with it – and during the entire program,
the function has a memory of previously calculated values.
And instead of the
def fib(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib(n-1) + fib(n-2)
fib = memoize(fib)
one can write:
@memoize
def fib(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib(n-1) + fib(n-2)
# this would be #5a – without a callable class just using functions!
# and I guess #5a will be faster than your #5, since it has some class/function calls less.
That makes perfect sense thanks your for your comments Kim!