import java.util.HashMap;
import java.util.Map;


interface DecorateMethod {

    public void runMe();

}


public class FibonacciFun {

    private static final int NUM_ITERATIONS = 2000000; //2,000,000
    private static final int MAX_FIB = 1000;

    private static Map<Integer, Long> results;

    static {
        results = new HashMap<>();
        results.put(0, 0l);
        results.put(1, 1l);
    }

    public static long dynamicFib(int n) {
        if (results.containsKey(n)) {
            return results.get(n);
        } else {
            results.put(n, dynamicFib(n - 1) + dynamicFib(n - 2));
            return results.get(n);
        }
    }

    public static long dumbFib(int n) {
        if (n == 0)
            return 0;
        else if (n == 1)
            return 1;
        else
            return dumbFib(n - 1) + dumbFib(n - 2);
    }

    public static long smartFib(int n) {
        int iteration = 0;
        int a = 0;
        int b = 1;
        while (iteration++ < n) {
            b = a + b;
            a = b - a;
        }
        return a;
    }

    public static long arrayFib(int n, boolean printMe) {
        int[] results = new int[n + 1];
        results[0] = 0;
        if (n > 0) {
            results[1] = 1;
            for (int i = 2; i <= n; i++) {
                results[i] = results[i - 1] + results[i - 2];
            }
        }
        if (printMe) {
            System.out.println(results.length);
        }
        return results[n];
    }

    public static long testMethod(DecorateMethod method) {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < NUM_ITERATIONS; i++) {
            method.runMe();
        }
        long endTime = System.currentTimeMillis();
        return endTime - startTime;
    }

    public static void main(String[] beans) {
        //Test array fib
        System.out.println("Array fib1 " + testMethod(new DecorateMethod() {
            @Override
            public void runMe() {
                arrayFib(MAX_FIB, false);
            }
        }));

        long start, end;

        start = System.currentTimeMillis();
        for (int j = 0; j < NUM_ITERATIONS; j++) {
            arrayFib(MAX_FIB, false);
        }
        end = System.currentTimeMillis();
        System.out.printf("Array fib %d\n", end - start);


//        start = System.currentTimeMillis();
//        for (int j = 0; j < NUM_ITERATIONS; j++) {
//            smartFib(MAX_FIB);
//        }
//        end = System.currentTimeMillis();
//        System.out.printf("Smart fib %d\n", end - start);


//        start = System.currentTimeMillis();
//        for (int j = 0; j < NUM_ITERATIONS; j++) {
//            dumbFib(MAX_FIB);
//        }
//        end = System.currentTimeMillis();
//        System.out.printf("Dumb fib %d\n", end - start);
    }
}