fast_fibonacci.py

#!/usr/bin/env python3

"""
This program calculates the nth Fibonacci number in O(log(n)).
It's possible to calculate F(1_000_000) in less than a second.
"""

from __future__ importannotations

importsys


deffibonacci(n: int) ->int:
"""
 return F(n)
 >>> [fibonacci(i) for i in range(13)]
 [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]
 """
ifn<0:
raiseValueError("Negative arguments are not supported")
return_fib(n)[0]


# returns (F(n), F(n-1))
def_fib(n: int) ->tuple[int, int]:
ifn==0: # (F(0), F(1))
return (0, 1)

# F(2n) = F(n)[2F(n+1) - F(n)]
# F(2n+1) = F(n+1)^2+F(n)^2
a, b=_fib(n//2)
c=a* (b*2-a)
d=a*a+b*b
return (d, c+d) ifn%2else (c, d)


if__name__=="__main__":
n=int(sys.argv[1])
print(f"fibonacci({n}) is {fibonacci(n)}")