Is there a way to show the Nth Fibonacci number? e.g. I want the 15th Fibonacci Number, but this only gives a list.
a = int(input('Enter N Number: '))
def fib(n):
a = b = 1
for i in range(n):
yield a
a, b = b, a + b
print(fib(a))
A naive approach would be to generate all n Fibonacci numbers and return the last element which takes O(n) time. You can calculate NthFibonacci number in O(1)(assuming math.pow takes O(1) time) using Binet's Formula.
Binet's Formula:
Fib(n) =(Phin − (−Phi)−n)/√5Where
Phi=(1+√5)/2= and -Phi=(1-√5)/2(1+√5)/2 is also called Golden Ratio.import math
def fib(n):
phi=1.61803398874989484820
return round(((math.pow(phi,n))-(math.pow(-(1-phi),n)))/math.sqrt(5))
fib(15)
# 610
fib(10)
# 55
Mathematical proof and calculator here.
Convert the result of fib() to a list and index it at -1:
print(list(fib(a))[-1])
>> Enter N Number: 15
>> [610]
You can compute the Nth-Fibonacci Number using recursion with memoization
Why?
For instance: imagine you are to compute fibonacci(5) so you need to compute fibonacci(4) and fibonacci(3). But now, for fibonacci(4) you need to compute fibonacci(3) and fibonacci(2), and so on. But wait, when you finish computing fibonacci(4) branch you already computed all fibonacci for 3 and 2, so when you go back to the other branch (fibonacci(3)) from the first recursive call, you already have computed it. So, What if there is a way I can store those calculations so I can access them faster? You can do it with Decorators to create a memoize class (some sort of memory to avoid repeated calculations):
This way we are going to store each computation of fibonacci(k) on a dict and we would check each time before a call if it exists on the dictionary, return if True or else compute it. This way is faster and accurate.
class memoize:
def __init__(self, function):
self.f = function
self.memory = {}
def __call__(self, *args):
if args in self.memory:
return self.memory[args]
else:
value = self.f(*args)
self.memory[args] = value
return value
@memoize
def fib(n):
if n <= 1:
return n
else:
return fib(n-1) + fib(n-2)
r = fib(300)
print(r)
Outputs:
222232244629420445529739893461909967206666939096499764990979600
It only took 0.2716239 secs.
Another approach of the answer posted by @DarK_FirefoX using the concept of memoization within the built-in function lru_cache which is a:
Decorator to wrap a function with a memoizing callable that saves up to the maxsize most recent calls. It can save time when an expensive or I/O bound function is periodically called with the same arguments.
from functools import lru_cache
@lru_cache()
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)
print(fib(300))
# 222232244629420445529739893461909967206666939096499764990979600
Bonus:
$> %timeit fib(300)
78.2 ns ± 0.453 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
As suggested in the comments your program can be used to generate the Nth number by taking the last in the sequence, i.e.
list(fib(n))[-1]
However, there are more efficient programs for just generating the Nth fibonacci number as discussed here
One such example is the 6th program from this source, i.e.:
# Python 3 Program to find n'th fibonacci Number in
# with O(Log n) arithmatic operations
MAX = 1000
# Create an array for memoization
f = [0] * MAX
# Returns n'th fuibonacci number using table f[]
def fib(n) :
# Base cases
if (n == 0) :
return 0
if (n == 1 or n == 2) :
f[n] = 1
return (f[n])
# If fib(n) is already computed
if (f[n]) :
return f[n]
if( n & 1) :
k = (n + 1) // 2
else :
k = n // 2
# Applyting above formula [Note value n&1 is 1
# if n is odd, else 0.
if((n & 1) ) :
f[n] = (fib(k) * fib(k) + fib(k-1) * fib(k-1))
else :
f[n] = (2*fib(k-1) + fib(k))*fib(k)
return f[n]
# Driver code
n = 9
print(fib(n)
Output
34
Advantage over Posted Code
The advantage of this approach is the complexity is O(log(n)) for the nth fibonacci number, while the posted code from the question has complexity O(n).
