Minborg

Minborg
Minborg

Saturday, July 4, 2015

An O(1) n-factorial Support Class for Java 8

Background


In some of my posts, I have talked about calculating n-factorial (i.e. n!) and I have received some comments about performance. In my post Compute factorials using Java 8 streams, I presented a number of ways to implement an n-factorial method and in a more recent post, Java 8, Master Permutations, I used one of those methods in the main solution for generating permutations.

In this post I present a very simple (or even trivial), yet high performance, n-factorial support class for Java 8.

Implementation


If a factorial method is to return a long, there are only 21 valid input values that can be used (read more about why in this post) namely 0, 1, ..., 20.  This fact allows us to pre-calculate all results and just use a lookup array like this:

public class Factorials {

    private Factorials() {
    }

    private static final long[] FACTORIALS = {
        1L,
        1L,
        2L,
        6L,
        24L,
        120L,
        720L,
        5040L,
        40320L,
        362880L,
        3628800L,
        39916800L,
        479001600L,
        6227020800L,
        87178291200L,
        1307674368000L,
        20922789888000L,
        355687428096000L,
        6402373705728000L,
        121645100408832000L,
        2432902008176640000L
    };

    public static long factorial(int n) {
        return FACTORIALS[n];
    }
    
    public static LongStream stream() {
        return LongStream.of(FACTORIALS);
    }

}
As can be seen, the factorial method will complete in O(1) time (i.e. in constant time regardless of the input parameter). In addition to the factorial() method, I have also added a stream() function that allows us to conveniently obtain a stream of all n-factorials.

If we use an argument outside the definition set, an ArrayIndexOutOfBoundsException will be thrown. You might want to clean up this behavior and throw a more relevant exception like this:
public static long factorial(int n) {
    if (n > 20 || n < 0) throw new IllegalArgumentException(n + " is out of range");
    return FACTORIALS[n];
}

Conclusion


When the definition set for a method is limited, it may sometimes be a good idea to eagerly pre-calculate all the values.






1 comment:

  1. Thanks for providing this! I was looking for something that would take me beyond the !20 threshold, and using your example, I came up with this:

    public static BigDecimal factorial(int n)
    return LongStream.rangeClosed(2, n)
    .parallel()
    .asDoubleStream()
    .mapToObj(BigDecimal::new)
    .reduce(BigDecimal::multiply)
    }

    I'm not a performance expert, but it seems fairly fast. I'm not sure what the practical application might be for it though...

    ReplyDelete