import java.math.BigInteger;
import java.util.stream.IntStream;
import java.util.stream.LongStream;

/** Factorial: loop, recursion, streams and BigInteger, with the overflow points shown. */
public class FactorialPrograms {

    // BEGIN loop
    static long factorialLoop(int n) {
        long result = 1;
        for (int i = 2; i <= n; i++) {
            result *= i;
        }
        return result;
    }
    // END loop

    // BEGIN recursion
    static long factorialRecursive(int n) {
        if (n <= 1) return 1;                 // base case: 0! = 1! = 1
        return n * factorialRecursive(n - 1);
    }
    // END recursion

    // BEGIN stream
    static long factorialStream(int n) {
        return LongStream.rangeClosed(1, n).reduce(1L, (a, b) -> a * b);
    }
    // END stream

    // BEGIN bigint
    static BigInteger factorialBig(int n) {
        BigInteger result = BigInteger.ONE;
        for (int i = 2; i <= n; i++) {
            result = result.multiply(BigInteger.valueOf(i));
        }
        return result;
    }

    static BigInteger factorialBigStream(int n) {
        return IntStream.rangeClosed(2, n)
                        .mapToObj(BigInteger::valueOf)
                        .reduce(BigInteger.ONE, BigInteger::multiply);
    }
    // END bigint

    // BEGIN exact
    static long factorialExact(int n) {
        long result = 1;
        for (int i = 2; i <= n; i++) {
            result = Math.multiplyExact(result, (long) i);   // throws on overflow
        }
        return result;
    }
    // END exact

    static BigInteger factorialBigRecursive(int n) {
        return n <= 1 ? BigInteger.ONE : BigInteger.valueOf(n).multiply(factorialBigRecursive(n - 1));
    }

    public static void main(String[] args) {
        System.out.println("factorialLoop(5) = " + factorialLoop(5) + ", factorialRecursive(5) = " + factorialRecursive(5)
                + ", factorialStream(5) = " + factorialStream(5) + ", 0! = " + factorialLoop(0));

        System.out.println();
        System.out.printf("%-4s %-24s %-24s %-24s%n", "n", "n! (true)", "int arithmetic", "long arithmetic");
        for (int n : new int[]{10, 12, 13, 15, 20, 21, 22}) {
            int iv = 1;
            for (int i = 2; i <= n; i++) iv *= i;
            System.out.printf("%-4d %-24s %-24d %-24d%n", n, factorialBig(n), iv, factorialLoop(n));
        }

        System.out.println();
        int firstInt = 0, firstLong = 0;
        for (int n = 1; n <= 25 && (firstInt == 0 || firstLong == 0); n++) {
            if (firstInt == 0) {
                try { int r = 1; for (int i = 2; i <= n; i++) r = Math.multiplyExact(r, i); }
                catch (ArithmeticException e) { firstInt = n; }
            }
            if (firstLong == 0) {
                try { factorialExact(n); } catch (ArithmeticException e) { firstLong = n; }
            }
        }
        System.out.println("int overflows first at n = " + firstInt + "   (12! = " + factorialLoop(12) + " fits, int max = " + Integer.MAX_VALUE + ")");
        System.out.println("long overflows first at n = " + firstLong + "   (20! = " + factorialLoop(20) + " fits, long max = " + Long.MAX_VALUE + ")");
        try {
            factorialExact(21);
        } catch (ArithmeticException e) {
            System.out.println("factorialExact(21) -> " + e);
        }

        System.out.println();
        BigInteger f100 = factorialBig(100);
        System.out.println("100! = " + f100);
        System.out.println("100! has " + f100.toString().length() + " digits; stream version equal: " + f100.equals(factorialBigStream(100)));

        System.out.println();
        try {
            factorialBigRecursive(1_000_000);
        } catch (StackOverflowError e) {
            System.out.println("recursive factorial of 1,000,000 -> " + e.getClass().getSimpleName());
        }
        System.out.println("iterative BigInteger 5000! has " + factorialBig(5000).toString().length() + " digits");
    }
}