# Eager Evaluation: n-factorial in O(1)

# Eager Evaluation: n-factorial in O(1)

### A limited set of methods can be implemented using eager evaluation, thereby providing very high performance.

Join the DZone community and get the full member experience.

Join For Free**Sensu is an open source monitoring event pipeline. Try it today.**

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 titled 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 that is based on the concept of eager evaluation. This scheme is only applicable when there is a finite and relatively small set of valid inputs (i.e., the input domain is small).

Evidently, handling larger *n!* values than in the example below requires something more than just a `long`

(like, for example, a `BigInteger`

). Larger domains can be handled by pre-computing "support" values at regular intervals.

Examples of methods that can be eagerly computed are factorials, primes, squares, powers, and the likes.

## 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 final class 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];
}
private Factorials() {}
}
```

As can be seen, the factorial method will complete in O(1) time (i.e., in constant time regardless of the input parameter).

If we use an argument outside the definition set, an `ArrayIndexOutOfBoundsException`

will be thrown. We 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 domain for a method is limited, it may sometimes be a good idea to eagerly precalculate all (or a subset of) the values. Eagerly calculated methods will have high performance but the tradeoff is the corresponding memory consumption.

**Sensu: workflow automation for monitoring. Learn more—download the whitepaper.**

Published at DZone with permission of Per-Åke Minborg , DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

## {{ parent.title || parent.header.title}}

## {{ parent.tldr }}

## {{ parent.linkDescription }}

{{ parent.urlSource.name }}