@@ -0,0 +1,680 @@
+import math%0A%0A# The code below calculates N-th fibonacci number by O(1)%0A# Such speed is achieved by using the Binet's formula which is%0A# fib(n) = (phi%5En - psi%5En) / sqrt(5)%0A# where%0A# phi = (1 + sqrt(5)) / 2 and psi = (1 - sqrt(5)) / 2%0A# But in code we compute fib(n) as%0A# fib(n) = round(phi%5En) / sqrt(5)%0A# because when n -%3E inf: abs(psi%5En) -%3E 0%0A# When n is small this formula is innacurate because%0A# we are computing in double and float and they aren't the exact values that we have in Math%0A# Because of the same reasons we may have slightly innacurate values with small n.%0A%0Adef fib(n):%0A%09phi = (1 + math.sqrt(5)) / 2%0A%09return int(round(phi**n / math.sqrt(5)))%0A%0An = 50%0Aprint(fib(50))%0A

add way of computing fibonacci sequence by O(1) in Python3