In my
last post, I shared my passion for functional programming. Luckily, with the new features in Java 8 you can embrace the functional style without using a pure functional language like Haskell or Lisp.
Learn Java Functional Style in Style
There's plenty of articles on the functional features in Java 8 around the net. In this blog post I offer you a different learning path: by example.
I'll show you a problem and solve it step by step using the Java 8 functional features naturally. I'll point out the interesting aspects of the solution so that you have some anchor points for your further research. That's learning Java functional style programming in style!
The Problem
So here's the problem to solve: calculate the number π to a precision of 20 decimal digits. I'll do the coding work so that you can focus on another things: understanding how the solution works and figuring out for yourself if you embrace this style in your daily Java coding.
Nilakantha Sequence
First we need a method how to calculate π. For the sake of simplicity I've chosen to use the Nilakantha sequence, the Indian mathematician's discovery dating back to the 15th century:
First Bite: Infinite Alternating Sequence
You're probably familiar with the notorious advice:
"How do you eat an elephant? One bite at a time."
Our first bite when eating the elephant (umm I mean producing the Nilakantha sequence) will be creating a
Stream of
BigDecimal's containing elements of this alternating sequence:
2, -4, 6, -8, 10, -12, 14, -16, ...
This turns out to be a bit more difficult than it seems, since the sequence generation needs to address two aspects of the above sequence:
- the iteration through all even numbers
- the alternation of the sign of the elements
While it's possible to use a fine crafted expression to address both aspects of this sequence, I personally find it's better to address those two aspects also separately in the code. When I was giving a Java 8 hands-on course using this very exercise one student came up with this very elegant solution:
Note that the above code very neatly separates all concerns of the sequence generation:
- on line 2 an infinite stream of positive members of the sequence is generated using Stream#iterate
- on line 3 a negative counterpart for each positive member of the sequence is added using Stream#of and Stream#flatMap
- on line 4 the stream of integers is converted to a stream of BigDecimal's using Stream#map (we need BigDecimal's because otherwise the double arithmetics would fail to provide the fractional elements of the sequence with the necessary precision)
Let me further explain the
flatMap call. What would happen if I just used
map instead? The result would be a stream with every element being a stream of two elements.
Let's visualize this scenario using the following alternative way to produce the root sequence:
The comments on the right hand side show what the stream looks like after each intermediate step. The
flatMap invocation takes an
identity function as parameter, which effectively means that the
flatMap call only flattens the stream - the resulting stream contains the same numbers but in a flat structure.
Key Takeaways
- Infinite streams can be created with iterate
- map vs flatMap:
- Use map to replace each element with some other element
- Use flatMap to replace each element with an arbitrary number of other elements
- When using map the number of elements in the stream will never change. With flatMap the resulting stream can have different number of elements than the original stream.
Second Bite: Infinite Nilakantha Sequence
Our second bite will be creating all fractional elements of the Nilakantha sequence:
This can be solved by transforming the elements using the
map method we already encountered in the previous bite:
This code replaces each of the root sequence elements (2, -4, 6, ...) with the corresponding fraction - which is specified in the lambda expression passed to the
map method. The fraction expression also contains the specification of the rounding mode (without it a runtime exception occurs since the JVM cannot calculate the fraction precisely).
Third Bite: Calculating the Sum
The third bite is the calculation of the sum of the Nilakantha sequence elements. But hey, the sequence is infinite so how are we going to calculate the sum after all? Of course, the more elements we take for the calculation, the closer we get to the exact value of π. So the question actually is - how many elements do we need to take to get the number π with the precision of 20 digits? The answer lies within the code:
Let's have a look at the new stuff here:
- on line 3 the infinite stream is turned into a finite one by telling the stream to stop generating more elements after 6,578,000 elements have been generated
- in case you wonder how the limit call affects the sequence generation, which occurs as the first method in the code, the answer is laziness: Java 8 streams are lazy so no operations are actually triggered before a terminal operation is applied on the stream. Limit itself is not a terminal operation but the very next operation on the stream - reduce - is a terminal one, and when it runs, the stream is already marked to contain a limited number of elements.
- on line 4 the sum of all elements in the sequence is calculated by starting with 3 and then adding each elements of the sequence
- on line 5 the required precision is set
And voila, that's it! The above method computes π to 20 digits!
Key Takeaways
- Infinite streams can be truncated to contain a finite number of elements with Stream#limit.
- Streams are lazy:
- any intermediate operation is only performed when a terminal operation is initiated
- stream elements are generated only when they are needed
- Combine all elements in the stream with a specified binary operation to produce a single result using Stream#reduce.
The Dessert: Parallelizing the Calculation
We did manage to eat the elephant in three bites, but I've got a bonus - since there's no piece of elephant left I'll call it a dessert: let's make the calculation more efficient by employing parallelism. It is very straightforward to make a Java 8 stream process in parallel - you only need to invoke
parallel on the stream.
I chose to make the stream parallel after the initialization, before the fractions and their sum are calculated - see line 3 in the following Gist:
Unfortunately this first try does not yield the expected result - the test is now broken!
~/ws/java-8-way $ mvn -Dtest=LifeOfPiTest test
...
Failed tests:
LifeOfPiTest.calculate:33 expected:<[3].1415926535897932384...> but was:<[249].1415926535897932384...>
WTF? (note: this is not bad language but
a valid measurement of code quality) The fractional part is correct but the part before the decimal point is wrong. To solve this little mystery we have to reiterate how the elements of the sequence are added: with
reduce(THREE, BigDecimal::add). So here is what happens: since the computation is now parallel, the reduce operation is also done on multiple threads and hence the initial value, THREE, is added way too many times. On your computer, you may get a different result before the decimal point, but it is guaranteed to be a multiple of three!
Once the problem is identified it is easy to fix:
The above code adds three as the final step - all reduce operations add the sequence elements starting with the initial sum of zero.
Now the test is fixed but unfortunately the execution times don't seem to be much different between the sequential (first line) and the parallel (second line) version:
Time elapsed: 4.98 sec - in de.blogspot...LifeOfPiTest
Time elapsed: 5.064 sec - in de.blogspot...LifeOfPiTest
The reason why parallelism gave us no gain (yet) is that the stream is
ordered - which defies any benefits that the parallel processing might yield. Since the sum of the sequence elements does not depend on their order, we can specify that the stream should be
unordered declaratively:
With this modification, finally, we get some benefit from parallelism:
Time elapsed: 2.559 sec - in de.blogspot...LifeOfPiTest
Key Takeaways
- Parallel streams can be tricky - so make sure you understand what you're doing. If you don't need to optimize then don't bother to introduce parallelism.
- Using unordered streams may significantly improve parallel processing performance, but you can only use them if the semantics of your problem does not depend on the ordering.
- Not every problem is embarrassingly parallel. The virtual machine I ran this example in has four CPU cores yet the parallel version runs barely twice as fast as the sequential version.
Conclusion
I hope you enjoyed learning Java 8 features on the example of π calculation. If you did enjoy the math I can assure you that you are in a good company: also Isaac Newton used infinite series to compute π to 15 digits, later writing "I am ashamed to tell you to how many figures I carried these computations".
Don't be ashamed yourself to carry some more computations! Feel free to further experiment with the code:
LifeOfPi.java
Of course, you can download, clone or fork the entire project from GitHub. Have fun!
