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

Eager Evaluation: n-factorial in O(1)

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.

Free Resource

Evolve your approach to Application Performance Monitoring by adopting five best practices that are outlined and explored in this e-book, brought to you in partnership with BMC.

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.

Evolve your approach to Application Performance Monitoring by adopting five best practices that are outlined and explored in this e-book, brought to you in partnership with BMC.

Topics:
performace ,factorials ,evaluations

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

Opinions expressed by DZone contributors are their own.

THE DZONE NEWSLETTER

Dev Resources & Solutions Straight to Your Inbox

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.

X

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

{{ parent.tldr }}

{{ parent.urlSource.name }}