Constant time solutions to Fibonacci and factorial calculations.

FactAndFib.java

package fact;

import static java.lang.Math.PI;
import static java.lang.Math.exp;
import static java.lang.Math.log;
import static java.lang.Math.pow;
import static java.lang.Math.rint;
import static java.lang.Math.sqrt;

public class FactAndFib {

    private static long hardFib(final int n) {
        final double sqrt = sqrt(5.0);
        final double mult = 0.5 * sqrt;
        return (long) rint((pow(0.5 + mult, n) -
            pow(0.5 - mult, n)) / sqrt);
    }

    private static long hardFact(final int n) {
        return (long) rint(gamma(n));
    }

    // http://introcs.cs.princeton.edu/java/91float/Gamma.java.html
    // Uses Lanczos approximation formula.
    static double logGamma(final double x) {
        final double tmp = (x - 0.5) * log(x + 4.5) - (x + 4.5);
        final double ser = 1.0 + 76.18009173 / (x + 0) - 86.50532033 / (x + 1)
            + 24.01409822 / (x + 2) - 1.231739516 / (x + 3)
            + 0.00120858003 / (x + 4) - 0.00000536382 / (x + 5);
        return tmp + log(ser * sqrt(2 * PI));
    }

    static double gamma(final double x) {
        return exp(logGamma(x));
    }

    public static void main(final String[] args) {

        System.out.println("Factorials 1..12");
        for (int i = 1; i < 12; i++) {
            System.out.println(hardFact(i));
        }

        System.out.println();
        System.out.println("Fibonacci Numbers 1..20");
        for (int i = 0; i < 20; i++) {
            System.out.println(hardFib(i));
        }
    }

}