@@ -0,0 +1,911 @@
+import java.lang.Math;%0A%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 */%0A%0Apublic class FibonacciByFormula %7B%0A%0A    final static double phi = (1 + Math.sqrt(5)) / 2;%0A%0A    private static long fib(int n) %7B%0A        return (long) (Math.round(Math.pow(phi, n)) / Math.sqrt(5));%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        int n = 50;%0A        System.out.print(fib(n));%0A    %7D%0A%7D

add way of computing fibonacci number by O(1) in Java