Minborg

Minborg
Minborg

Wednesday, November 5, 2014

Compute factorials using Java 8 streams


Background

N factorial (also denoted N!) means computing 1*2*3*...*N and is a classical problem used in computer science to illustrate different programming patterns. In this post I will show how one can use Java 8's Streams to calculate factorials. But first, I will show two other ways that were previously used before Java 8 appeared.

Recursion

From our computer science classes, we all remember the classical way of computing factorial(). The following method illustrates the concept:
    public long factorial(int n) {
        if (n > 20) throw new IllegalArgumentException(n + " is out of range");
        return (1 > n) ? 1 : n * factorial(n - 1);
    }
Because long overflows for n > 20, we need to throw an exception to avoid faulty return values. If we are within the valid input range, we check for the basic case where n is 1 or less for which factorial is 1, otherwise we recurse by returning n multiplied with factorial(n-1). Eventually, we will reach factorial(1) and the recursion stops.

Imperative 

You can also use the standard imperative way of doing it using an intermediate value that is used in a loop, like this:
    public long factorial(int n) {
        if (n > 20) throw new IllegalArgumentException(n + " is out of range");
        long product = 1;
        for (int i = 2; i < n; i++) {
            product *= i;
        }
        return product;
    }

Look at the loop and you might be surprised to see that we start from 2. We could as well have started from 1, but then again, multiplying with 1 always gives back the same result, doesn't it? So we optimize away that case.

Streams

Using Java 8's stream methods we can implement factorial() in another way as depicted here:
    public long factorial(int n) {
        if (n > 20) throw new IllegalArgumentException(n + " is out of range");
        return LongStream.rangeClosed(2, n).reduce(1, (a, b) -> a * b);
    }
Using the LongStream.rangeClosed(2, n) method we create a Stream of longs with the content 2, 3, ... , n. Then we take this Stream and successively applies the reduction (a, b) -> a * b meaning that for each pair a and b we multiply them and return the result. The result then carries over to a for the next round. The value "1" used in the reduced method is the identity value, i.e. the value that is used as a starting value for a for the first iteration.

This way, we abstract away the implementation and instead focus on what to do. For example, the Stream could be made parallel and that way we could calculate the value using several threads.  Perhaps not so useful in this particular example where n < 20, but certainly for other applications with longer iteration chains.

Consider using Streams when iterating over values!

1 comment:

  1. Now there is a new post (http://minborgsjavapot.blogspot.com/2015/07/an-o1-n-factorial-support-class-for.html) devising an O(1) factorial method using an array lookup scheme.

    ReplyDelete