Fibonacci

README.md

Fibonacci formula:

fib n = floor (phiⁿ/√5 + ¹/₂)

fib n ~= phiⁿ/√5

How many digits is fib n?

numDigits (fib n) = log (fib n) = log (phiⁿ/√5) = log phiⁿ - log √5 = n * log phi - log √5

numDigits (fib n) = n * const + const

it's O(n)

Since the requested result is of O(n), it can't be calculated in less than O(n) time.

If you only want the lower digits of the answer, then it is possible to calculate in sub-linear time using the matrix exponentiation method.

Fibonacci.java

Main.java

import java.lang.Math;

public class Main {

    public static double inverseSqrt5 = 1 / Math.sqrt(5);
    public static double phi = (1 + Math.sqrt(5)) / 2;

    public static int fibonacci(int n) {
        return (int)Math.floor(Math.pow(phi, n) * inverseSqrt5 + 0.5);
    }
    public static void main(String[] args) {
        System.out.println("Fib 1 = " + fibonacci(1));
        System.out.println("Fib 2 = " + fibonacci(2));
        System.out.println("Fib 3 = " + fibonacci(3));
        System.out.println("Fib 4 = " + fibonacci(4));
        System.out.println("Fib 5 = " + fibonacci(5));
        System.out.println("Fib 6 = " + fibonacci(6));
        System.out.println("Fib 7 = " + fibonacci(7));
    }
}