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.
return there. Also, I computed 300 fibonacci number with a plain recursive function with memoization and got 222232244629420445529739893461909967206666939096499764990979600 in 0.23246139999999998 secs. With Binet's Formula I got 222232244629422676106398124069050176556246085874450435841982464 in 0.9962692000000001 secs. Notice it took longer and with a difference of 2230576658230607140209349579146777950670851002864. What do you think about this?
timeit here it is Share your thoughtsn**300 takes lot of time though it's asymptotically O(1). I guess using memoization is better. Post it as answer. I'll sure upvote. ;)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.
lru_cache ?lru_cache for others. Feel free to do it in an answer, would be helpful. GreetingsAnother 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).