def fastFib(n):
    if n <= 2:
        return 1
    half = int(n / 2)
    a = fastFib(half)
    b = fastFib(half + 1)
    if n%2 == 0:
        return a*(2*b-a)
    else:
        return a*a+b*b

from math import sqrt
def mathFib(n):
    s5 = sqrt(5)
    return ((1+s5)**n-(1-s5)**n)/(2**n*s5)

print(fastFib(100000))
print(mathFib(100000))