ISourceCode

Make the frequent cases fast and the rare case correct

Fibonacci Numbers – [Recursion , Iterative using Dynamic Programming , Matrix Property]

In mathematics, the Fibonacci numbers are the numbers in the following integer sequence:

the sequence Fn of Fibonacci numbers is defined by the recurrence relation

with seed values

Closed form solution:
Binet’s formula, even though it was already known by Abraham de Moivre

where

is golden ratio

Matrix form:

A 2-dimensional system of linear difference equations that describes the Fibonacci sequence is

direct formula for the nth element in the fibonacci series:

Python using Matrix property:

>>> import numpy
>>> fib = numpy.matrix([[1,1],[1,0]])
>>> result = fib*fib
>>> result
matrix([[2, 1],
        [1, 1]])
>>> result = fib*fib*fib
>>> result
matrix([[3, 2],
        [2, 1]])
>>> result = fib*fib*fib*fib*fib
>>> result
matrix([[8, 5],
        [5, 3]])

In this Post you can find implementation for finding nth fibonacci number using

1 . Recursion – exponential
2 . Iterative method using Dynamic Programming – O(n)
3 . Matrix Property – O(log n)

For the Run time of the three algorithms please refer to this article from cs.wisc here

Implementation:

import time
def fib_matrix(n):
	i = h = 1
	j = k = 0
	while (n > 0) :
		if (n%2 == 1) : # when n is odd
			t = j*h
			j = i*h + j*k + t
			i = i*k + t
		t = h*h
		h = 2*k*h + t
		k = k*k + t
		n = int(n/2)
	return j
start1 = time.strftime('%s')
value1 = fib_matrix(500000)
#print value1
end1 = time.strftime('%s')
time1 = int(end1) - int(start1)
print "Time to execute the algorithm using matrix property=", time1 ,"Second(s)"

def fib_dp(n):
	a = b = 1
	for i in range(2,n) :
		c = a+b
		a = b
		b = c
	return c
start2 = time.strftime('%s')
value2 = fib_dp(500000)
#print value2
end2 = time.strftime('%s')
time2 = int(end2) - int(start2)
print "Time to execute the algorithm using dynamic programming =", time2 ,"Second(s)"

def fib_rec(n) :
	if (n==1 or n==2) :
		return 1
	return fib_rec(n-1) + fib_rec(n-2)
start3 = time.strftime('%s')
value3 = fib_rec(35)
#print value3
end3 = time.strftime('%s')
time3 = int(end3) - int(start3)
print "Time to execute the algorithm using recursion without dynamic programming =", time3 ,"Second(s)"

OUTPUT:

labuser@ubuntu:~$ python fib.py
Time to execute the algorithm using matrix property= 2 Second(s)
Time to execute the algorithm using dynamic programming = 38 Second(s)
Time to execute the algorithm using recursion without dynamic programming = 19 Second(s)

Note : I had to use input 35 for recursion to capture a run time as its a exponential time algorithm

The matrix method is more efficient than the simple iterative algorithm for larger numbers. For smaller numbers, the simplicity of the iterative algorithm is preferable.

Thanks to Wikipedia for the Theory !

One response to “Fibonacci Numbers – [Recursion , Iterative using Dynamic Programming , Matrix Property]

  1. Jonas March 4, 2011 at 9:04 pm

    Hwy could you please please please, make the Matrix Property Algorithm O(log n) into C or C++, because i am struggling to understand the code =/

    Thanks mate.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: