Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

DZone's Guide to

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

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

· Performance Zone ·
Free Resource

Comment (2)

Save
{{ articles[0].views | formatCount}} Views

xMatters delivers integration-driven collaboration that relays data between systems, while engaging the right people to proactively resolve issues. Read the Monitoring in a Connected Enterprise whitepaper and learn about 3 tools for resolving incidents quickly.

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.

Discovering, responding to, and resolving incidents is a complex endeavor. Read this narrative to learn how you can do it quickly and effectively by connecting AppDynamics, Moogsoft and xMatters to create a monitoring toolchain.

Topics:
performace ,factorials ,evaluations

Comment (2)

Save
{{ articles[0].views | formatCount}} Views

Published at DZone with permission of

Opinions expressed by DZone contributors are their own.