-
Notifications
You must be signed in to change notification settings - Fork 123
Fibonacci Series
Qiang Zhu edited this page Sep 25, 2018
·
6 revisions
def Fibonacci(N):
'''
This program is to calculate Fibonacci number`
Input: N (must be a positive integer number) `
output: the Fibonacci series`
'''
Fib_series = []
for i in range(1,N+1):
if len(Fib_series)<=1:
Fib_series.append(1)
else:
Fib_series.append(Fib_series[-1] + Fib_series[-2])
return Fib_series
print(Fibonacci(-1))
print(Fibonacci(1))
print(Fibonacci(2))
print(Fibonacci(3))
print(Fibonacci(4))
print(Fibonacci(1000))
Suppose if we just want to calculate the Fibonacci number for a given index, the above program can be written as follows:
def Fibonacci(N):
'''
This program is to calculate fibonacci number using return
Input: N (must be a positive integer number)
output: the Fibonacci series
'''
Fib_series = []
for i in range(1,N+1):
if len(Fib_series)<=1:
return 1
else:
Fib_series.append(b)
a, b = b, a + b
return Fib_series[-1]
%timeit(Fibonacci(10000))
You can simply evaluate the time cost by using the timeit function
530 ns ± 35.4 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
However, the time cost can be reduced to half by simply replacing return with yield function:
def Fibonacci2(N):
'''
This program is to calculate fibonacci number using yield
Input: N (must be a positive integer number)
output: the Fibonacci series
'''
Fib_series = []
a = b = 1
for i in range(1,N+1):
if len(Fib_series)<=1:
yield 1
else:
yield a
a, b = b, a + b
%timeit(Fibonacci2(10000))
225 ns ± 5.18 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
The yield statement suspends function’s execution and sends a value back to caller, but retains enough state to enable function to resume where it is left off. When resumed, the function continues execution immediately after the last yield run. This allows its code to produce a series of values over time, rather them computing them at once and sending them back like a list.