import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;
import java.util.stream.Stream;

/** Five ways to compute Fibonacci numbers. */
public class FibonacciSeries {

    // BEGIN loop
    static long fibLoop(int n) {
        long a = 0, b = 1;                 // fib(0), fib(1)
        for (int i = 0; i < n; i++) {
            long next = a + b;
            a = b;
            b = next;
        }
        return a;
    }
    // END loop

    // BEGIN recursion
    static long calls;                     // counts invocations, for the demo only

    static long fibRecursive(int n) {
        calls++;
        if (n < 2) return n;
        return fibRecursive(n - 1) + fibRecursive(n - 2);
    }
    // END recursion

    // BEGIN memo
    static final Map<Integer, Long> cache = new HashMap<>();

    static long fibMemo(int n) {
        if (n < 2) return n;
        Long hit = cache.get(n);
        if (hit != null) return hit;
        long value = fibMemo(n - 1) + fibMemo(n - 2);
        cache.put(n, value);
        return value;
    }
    // END memo

    // BEGIN stream
    static long fibStream(int n) {
        return Stream.iterate(new long[]{0, 1}, p -> new long[]{p[1], p[0] + p[1]})
                     .skip(n)
                     .findFirst()
                     .get()[0];
    }
    // END stream

    // BEGIN bigint
    static BigInteger fibBig(int n) {
        BigInteger a = BigInteger.ZERO, b = BigInteger.ONE;
        for (int i = 0; i < n; i++) {
            BigInteger next = a.add(b);
            a = b;
            b = next;
        }
        return a;
    }
    // END bigint

    // BEGIN exact
    static long fibExact(int n) {
        long a = 0, b = 1;
        for (int i = 0; i < n; i++) {
            long next = Math.addExact(a, b);   // throws ArithmeticException instead of wrapping
            a = b;
            b = next;
        }
        return a;
    }
    // END exact

    public static void main(String[] args) {
        System.out.print("First 15 terms: ");
        for (int i = 0; i < 15; i++) System.out.print(fibLoop(i) + (i < 14 ? ", " : "\n"));

        System.out.println();
        System.out.println("All five agree for n = 0..40: " + allAgree());

        System.out.println();
        System.out.printf("%-4s %-12s %-14s %-14s%n", "n", "fib(n)", "calls (naive)", "2*fib(n+1)-1");
        for (int n : new int[]{1, 2, 3, 5, 10, 20, 30}) {
            calls = 0;
            long v = fibRecursive(n);
            System.out.printf("%-4d %-12d %-14d %-14d%n", n, v, calls, 2 * fibLoop(n + 1) - 1);
        }

        System.out.println();
        long t = System.nanoTime();
        calls = 0;
        long v = fibRecursive(40);
        System.out.println("naive  fib(40) = " + v + "  calls=" + calls + "  " + (System.nanoTime() - t) / 1_000_000 + " ms");
        t = System.nanoTime();
        v = fibMemo(40);
        System.out.println("memo   fib(40) = " + v + "  " + (System.nanoTime() - t) / 1_000 + " us");

        System.out.println();
        System.out.println("fib(92) = " + fibLoop(92) + "   (largest that fits in long)");
        System.out.println("fib(93) with plain long  = " + fibLoop(93) + "   <- wrapped around");
        try {
            fibExact(93);
        } catch (ArithmeticException e) {
            System.out.println("fib(93) with addExact    -> " + e);
        }
        System.out.println("fib(93)  as BigInteger   = " + fibBig(93));
        System.out.println("fib(100) as BigInteger   = " + fibBig(100));
        System.out.println("fib(1000) has " + fibBig(1000).toString().length() + " digits");
    }

    static boolean allAgree() {
        for (int n = 0; n <= 40; n++) {
            long e = fibLoop(n);
            if (fibRecursive(Math.min(n, 25)) != fibLoop(Math.min(n, 25))) return false;
            if (fibMemo(n) != e || fibStream(n) != e || !fibBig(n).equals(BigInteger.valueOf(e))) return false;
        }
        return true;
    }
}