Minborg

## 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...