fibonacci specific number generator python

Question

Is there a way to show the N^th Fibonacci number? e.g. I want the 15^th 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))

Answer 1

A naive approach would be to generate all n Fibonacci numbers and return the last element which takes O(n) time. You can calculate N^thFibonacci number in O(1)(assuming math.pow takes O(1) time) using Binet's Formula.

Binet's Formula:

Fib(n) =(Phin − (−Phi)−n)/√5

Where

• 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.