Vote Up 0 Vote Down

fibonacci series in python code

Hi I have written code for Fibonacci series in Python.
Can anyone suggest me how to make this code smaller and efficient?

import random
r = 5
c = 5
a = [ ([0] * c) for row in xrange(r) ]
b = []
for i in range(25):
b.append(i+1)

for i in range(r):
for j in range(c):
k = random.randint(0,24)
n = b[k]
b[k] = 0
if n == 0:
for m in range(25):
if b[m] != 0:
n = b[m]
b[m] = 0
break

a[i][j] = n
flag

Answers


Vote Up 0 Vote Down
When using recursion, keep in mind for computing high values of fibonacci series, it will waste lot of time computing already computed values. To overcome, use memorization technique.
flag | link |
Vote Up 0 Vote Down
The fastest way to compute fibonnaci numbers exactly is exponentiation by squaring, using matrices. Also, Claus's code isn't giving you the n'th fib, it is printing all the fibs less than n.

You might find this interesting.

# your code goes here
def fib_iter(n):
a, b = 0, 1
while n:
a, b = b, a+b
n -= 1
return a

def fib_mat(n):
start = [[0,1],[1,1]]
return mat_pow(start,n)[0][1]

def mat_pow(mat, n):
if n==0: return [[1,0],[0,1]]
if n==1: return mat
if n&1: return mat_mul(mat, mat_pow(mat, n-1))
return mat_pow(mat_mul(mat, mat), n/2)

def mat_mul(A, B):
return map(lambda row: map(lambda col: dot(row, col), zip(*B)), A)

def dot(u, v):
return sum(map(lambda a,b: a*b, u, v))

print map(fib_iter, range(11))
print map(fib_mat, range(11))
flag | link |
Vote Up 0 Vote Down
There is a technique called memoization (caching previously computed results, in dictionary - argument:result pair)

Fastest way depends highly on mathematical relations and properties of fibonacci series. At the same time we should keep in mind that most primitive instructions which are actually optimized in hardware because they are used most often in almost any program (simple arithmetic operations and assignments and iteration rather than unnecessary jumps and function calls) and if we want better performance we shouldn't fight against physics and math. Both recursion and matrices require significant memory to compute values for higher arguments.
flag | link |
Vote Up 0 Vote Down
Another method to do it is to use the fact that the Fibonacci sequence forms a linear homogeneous recurrence relation, whose characteristic equation's roots can be used to find the nth Fibonacci number
flag | link |
Vote Up 0 Vote Down
If you want to just find the nth term in a fibonaci sequenc, Binet formula is a better choice with a time complexity of o(log n) [Same as that of exponating a number]. But for computing the first n terms of a fibonaci sequence, Binet formula will have a complexity of o(n*log n), and using the recurrence relation will be faster in this case as it has a time complexity of o(n).
flag | link |

Your Answer

Login before answering

Login with facebook