# return the first n fibonacci numbers

#version 1: for loop, list,  nonrecursive
from pylab import *


def fib(N):
    #req: N>=0 , no error checking
    if N==0:
        ret =[0]
        return ret
        
    if N==1:
        ret = [0, 1]
        return ret
    
    ret = [0,1]
    for n in range(2,N+1):
        ret+=[ret[n-1]+ret[n-2]]
    return ret
        
#version 2:  for loop, numpy, nonrecursive
def fib2(N):
    #req: N>=0, no error checking
    x=empty(N+1)
    if N==0:  #careful! 
        x[0]=0
        return x
    if N==1:
        x[1]= 1
        return x 
    
    x[:2]= [0,1]
    for n in arange(2, N+1):
        x[n] = x[n-1] + x[n-2]

    return x


#version 3: generator, list, nonrecursive 
def fib3(N):
    a,b = 0,1
    i=0
    while i<=N:
        yield a
        a,b = b, a+b
        i= i+1
        

from  timeit import timeit;
if __name__=='__main__':
#    print fib(5)
#    print fib2(5)
#    print fromiter(fib3(5), np.float)
    #print list(fib3(5))

    X = zeros((3,1000))
    
#     import cProfile
#     cProfile.run('from ex301 import fib2; fib2(1000)')
#     
    
    for i in range(size(X,1)):
        X[0,i] = timeit("fib(%d)"%i, setup='from w5_3 import fib' ,number=1)/1;
        X[1,i] = timeit("fib2(%d)"%i,setup='from w5_3 import fib2' , number=1)/1;
        X[2,i] = timeit("list(fib3(%d))"%i, setup='from w5_3 import fib3' , number=1)/1;
    figure(0)
    plot(arange(size(X,1)), X[0,:],'r', 
        arange(size(X,1)), X[1,:],'g', arange(size(X,1)), X[2,:], 'b' )         
    

# explorer several issues. 
# number = 1 versus 1000
# why numpy is so slow?
# explore when N is too big