m1b on 10/09/11

# Fun with Fibonacci, Golden Ratio and Factorials, with loops vs recursives

/ Published in: Java   `import java.math.*;import static java.math.BigInteger.*; /** * Fun with Fibonacci, Golden Ratio and Factorials, with loops vs recursives. */public class FiboFact {     /**     * Fibonacci in a loop, no recursion.     */    private static int fibLoop(int n) {        if(n < 2) return n;        int previous = 0;        int next = 1;        for(int i = 1; i < n; i++) {            int save = next;             next += previous;            previous = save;        }        return next;    }     /**     * Fibonacci recursive. Although sleek, short and with nothing that could go wrong, there is a serious     * performance issue for large N: there is an exponential explosion of reevaluations and Java does not provide memoization without      * a dedicated effort to it. Therefore, for an N, N-2 will be evaluated by N and N-1. N-3 will be evaluated by N, N-1 and N-2,     * and so on.     */    private static int fibRecursive(int n) {        // uncomment the following line to see the exponential explosion of reevaluations:        //System.out.printf("<fib:" + n + '>');        return n < 2 ? n : fibRecursive(n-1) + fibRecursive(n-2); // this fork is the cause of exponential explosion    }     /**     * Factorial in a loop with long, good till n = 20. With int, the biggest n would be 12.     */    private static long factLoop(long n) {        if(n < 0) throw new IllegalArgumentException("Factorial operation illegal for " + n);        if(n == 0) return 1;        long result = 1;        for(int i = 1; i <= n; i++) result *= i;        return result;    }     private static long factRecursive(long n) {        if(n < 0) throw new IllegalArgumentException("Factorial operation illegal for " + n);        return n <= 1 ? 1 : n * factRecursive(n - 1);    }     /**     * Big Integer for factorials of integers greater than 20.     */    private static BigInteger factBdLoop(final BigInteger n) {        if(n.compareTo(ZERO) < 0) throw new IllegalArgumentException("Factorial operation illegal for " + n);        if(n.compareTo(ONE) <= 0) return ONE;        BigInteger result = ONE;        for(int i = 1; i <= n.intValue(); i++) result = result.multiply(BigInteger.valueOf(i));        return result;    }     private static BigInteger factBdRecursive(final BigInteger n) {        if(n.compareTo(ZERO) < 0) throw new IllegalArgumentException("Factorial operation illegal for " + n);        return n.compareTo(ONE) <= 0 ? ONE : n.multiply(factBdRecursive(n.subtract(ONE)));    }    public static void main(String[] args) {        int prev = 0;        for(int n = 0; n <= 15; n++) {            int f = fibLoop(n);            System.out.printf("%nn=%2d, loop: %d, recurse: %d", n, f, fibRecursive(n));            if(prev != 0) System.out.printf(", golden ratio= %19.17f", Double.valueOf(f)/Double.valueOf(prev));            prev = f;        }        final int goldenBase = 46; // max fib that fits in an int        // for 92, 7540113804746346429/4660046610375530309=1.618033988749894848204586834365638117699        final BigDecimal fiBigger = BigDecimal.valueOf(fibLoop(goldenBase));        final BigDecimal fiSmaller = BigDecimal.valueOf(fibLoop(goldenBase - 1));        // for fib/fib we get 17 correct digits of golden ratio        System.out.printf("%nGolden Ratio of %,.0f/%,.0f: %19.17f", fiBigger, fiSmaller, fiBigger.divide(fiSmaller, 44, RoundingMode.HALF_UP));        for(int n = 0; n <= 21; n++) { // 21! already blows the Long range of -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807 inclusive            // 20! is the last valid factorial for Long; for int it's 12            System.out.printf("%nn=%2d, loop: %,25d; recurse: %,25d", n, factLoop(n), factRecursive(n));        }        System.out.printf("  <<<< WOOPS!! Too big for a Long!");        for(int n = 0; n < 31; n++) { // with big integer the limit is memory            final BigInteger bigN = BigInteger.valueOf(n);            System.out.printf("%nn=%2d, loop: %,45d; recurse: %,45d", n, factBdLoop(bigN), factBdRecursive(bigN));        }        System.out.printf("%nLong: min=%,d, max=%,d", Long.MIN_VALUE, Long.MAX_VALUE);    }}`