Project Euler "Even Fibonacci numbers" in Java 8

Question

I'm looking for general advice on my code on the following problem:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

public class Problem2 extends Problem<Integer> {
 @Override
 public void run() {
 result = FibonacciGenerator.finiteStream(i -> (i <= 4_000_000))
 .filter(i -> (i % 2 == 0))
 .mapToInt(i -> i)
 .sum();
 }
 @Override
 public String getName() {
 return "Problem 2";
 }
}

---

public class FibonacciGenerator extends RestrictedGenerator<Integer> {
 private int beforePrevious = 0;
 private int previous = 1;
 protected FibonacciGenerator(final Predicate<Integer> predicate) {
 super(predicate);
 }
 @Override
 public boolean hasNext() {
 return predicate.test(previous);
 }
 @Override
 public Integer next() {
 int result = beforePrevious + previous;
 beforePrevious = previous;
 previous = result;
 return result;
 }
 public static Stream<Integer> finiteStream(final Predicate<Integer> predicate) {
 return RestrictedGenerator.toStream(new FibonacciGenerator(predicate), Spliterator.ORDERED);
 }
 public static Stream<Integer> infiniteStream() {
 return RestrictedGenerator.toStream(new FibonacciGenerator(i -> true), Spliterator.ORDERED);
 }
 public static Stream<Integer> finiteParallelStream(final Predicate<Integer> predicate) {
 return RestrictedGenerator.toParallelStream(new FibonacciGenerator(predicate), Spliterator.ORDERED);
 }
 public static Stream<Integer> infiniteParallelStream() {
 return RestrictedGenerator.toParallelStream(new FibonacciGenerator(i -> true), Spliterator.ORDERED);
 }
}

---

public abstract class RestrictedGenerator<T> implements Iterator<T> {
 protected final Predicate<T> predicate;
 protected RestrictedGenerator(final Predicate<T> predicate) {
 this.predicate = predicate;
 }
 @Override
 public abstract boolean hasNext();
 @Override
 public abstract T next();
 protected static <T> Stream<T> toStream(final RestrictedGenerator<T> generator, final int charasterics) {
 return StreamSupport.stream(
 Spliterators.spliteratorUnknownSize(generator, charasterics), false
 );
 }
 protected static <T> Stream<T> toParallelStream(final RestrictedGenerator<T> generator, final int charasterics) {
 return StreamSupport.stream(
 Spliterators.spliteratorUnknownSize(generator, charasterics), true
 );
 }
}

---

public abstract class Problem<T> implements Runnable {
 protected T result;
 public String getResult() {
 return String.valueOf(result);
 }
 abstract public String getName();
}

---

public class ProjectEuler {
 private final List<Problem<?>> problems = new ArrayList<>();
 private void init() {
 problems.add(new Problem1());
 problems.add(new Problem2());
 process();
 }
 private void process() {
 problems.stream().forEachOrdered(new ProblemConsumer());
 }
 /**
 * @param args the command line arguments
 */
 public static void main(String[] args) {
 new ProjectEuler().init();
 }
 private class ProblemConsumer implements Consumer<Problem<?>> {
 @Override
 public void accept(Problem<?> problem) {
 long start = System.nanoTime();
 problem.run();
 String result = problem.getResult();
 long end = System.nanoTime();
 long elapsed = end - start;
 System.out.println(problem.getName() + ": " + result + " (" + String.format("%,d", (elapsed / 1_000_000)) + " ms" + ")");
 } 
 }
}

Maybe I've gotten a bit over excited with the new options in Java 8, my main concern is readability, and for the rest just general advice.

• rolfl: Could you give some background on the Problem<T> class? Where is it from, what does it do? Is there a main() method somewhere? Thanks.
• skiwi: @rolfl Added all code on request.
• rolfl: Just saying ... I have your code loaded up, and I really appreciate the Problem model you have set up. I think I will 'borrow' it, if you don't mind.
• skiwi: @rolfl That's no problem at all, I'd be honered by that. I do have some other question though, I've changed by code a bit yet again, should I update this post or make a new one?
• rolfl: There are no answers (yet), so you can change your code. I am goin through your problem now, so don't take too long ;-) (I will do other things till you're done).

Answer 1

So a fair amount of Java8 is new to me, including the Stream API, which is, in essence, why this review is useful to me too. Bear with me...

Readability

You say "my main concern is readability". Now that I have spent some time looking in to what you are doing, what you are using, and reading up on some documentation, the answer is: yes!

The code does look strange, but that is only because the language structures are new. You are using them right, conforming to what few 'standards' there are... and it is fine.

General

RestrictedGenerator

public abstract class RestrictedGenerator<T> implements Iterator<T> {

This class is essentially useless. It is a container for a Predicate, which is accessed through it's protected nature anyway. Also, what about it is 'restricted'? Why does it have that name?

The static methods on it could be anywhere too. They have no business being on this class specifically.

Basically the class is irrelevant, and makes the class structure more complicated than it needs to be. Moving the functionality to FibonacciGenerator is trivial.

Problem<T>

I really like how you have set up a system for running your tests. This is a worthwhile investment. I have taken your system, and extended it quite a lot. I have made the performance tests a bit more structured. Also, I have rearranged the Problem<T> class. This is a compliment for your code... not a criticism... it's good. I just want to use it differently from you. On the other hand, you may like what I have done, so have a look.

I did find some problems... you are doing long-division on the time values:

String.format("%,d", (elapsed / 1_000_000))

As your code gets faster (warmed up), you will want to convert that to a floating-point:

String.format("%.5f", (elapsed / 1_000_000.0))

Functionality

I cannot find anything wrong with the algorithm. It works as advertized, but there are some places where the code is excessive, redundant, or 'artificial'. The RestrictedGenerator was the worst offender.

Performance

Right, Performance is where I really get interested in problems... I have modified your code and run it through some benchmarks, then I have made alternate systems, and benchmarked them too.

The first thing I noticed is that you are reporting the performance time of the first run. It is common knowledge that Java only starts getting 'fast' when it is 'warmed up'. You want to know what sort of difference it makes? Well, you say your code runs in 56ms (your benchmark code), but, I say it runs in 0.00100ms. Yeah, the numbers are really small. The problem is not particularly challenging.

But, I thought, "I always complain about people using autoboxing instead of primitives... surely the Streams API has primitive processing options?", and, when I looked, it does! So, I converted your code to use IntStream and other Int* constructs, instead of Stream<Integer>. This has helped with performance. There is an example of that code.

I also thought, what If I write it as I 'learn' Java8, and compare it to what I would have done in Java7.

So, I now have 4 implementations of the problem:

1. your version
2. your version converted to IntStream
3. my version in Java8
4. my version in Java7

---

Your Version

No reason to do anything here....

---

Your Version as IntStream

I have removed the code that's not relevant (including the RestrictedGenerator)

Problem2IntStream.java

public final class Problem2IntStream extends Problem<Integer> {
 public Problem2IntStream() {
 super("Problem 2 - IntStream", 1000, 100);
 }
 @Override
 public Integer execute() {
 return FibonacciIntGenerator.finiteStream(i -> (i <= 4_000_000))
 .filter(i -> (i % 2 == 0))
 .sum();
 }
}

FibonacciIntGenerator.java

public class FibonacciIntGenerator implements PrimitiveIterator.OfInt {
 private int beforePrevious = 0;
 private int previous = 1;
 private final IntPredicate predicate;
 protected FibonacciIntGenerator(final IntPredicate predicate) {
 this.predicate = predicate;
 }
 @Override
 public boolean hasNext() {
 return predicate.test(previous);
 }
 @Override
 public int nextInt() {
 int result = beforePrevious + previous;
 beforePrevious = previous;
 previous = result;
 return result;
 }
 public static IntStream finiteStream(final IntPredicate predicate) {
 return StreamSupport.intStream(Spliterators.spliteratorUnknownSize(new FibonacciIntGenerator(predicate), Spliterator.ORDERED), false);
 }
 public static IntStream infiniteStream() {
 return StreamSupport.intStream(Spliterators.spliteratorUnknownSize(new FibonacciIntGenerator(i -> true), Spliterator.ORDERED), false);
 }
}

---

My first Streams code ever

Note, this code works off a Spliterator instead of an Iterator... which, I think, removes a level of abstraction....

public final class Problem2Java8 extends Problem<Integer> {
 public Problem2Java8() {
 super("Problem 2 - rolfl java8", 1000, 100);
 }
 @Override
 public Integer execute() {
 return StreamSupport
 .intStream(new FibGenerator(i -> i <= 4000000), false)
 .filter(i -> (i & 1) == 0).sum();
 }
 private static class FibGenerator implements Spliterator.OfInt {
 private static final int CHARACTERISTICS = IMMUTABLE | ORDERED;
 int fib = 1;
 int prev = 1;
 private final IntPredicate predicate;
 public FibGenerator(IntPredicate pred) {
 predicate = pred;
 }
 @Override
 public boolean tryAdvance(IntConsumer action) {
 if (!predicate.test(fib)) {
 return false;
 }
 action.accept(fib);
 int tmp = fib;
 fib += prev;
 prev = tmp;
 return true;
 }
 @Override
 public long estimateSize() {
 return Long.MAX_VALUE;
 }
 @Override
 public int characteristics() {
 return CHARACTERISTICS;
 }
 @Override
 public java.util.Spliterator.OfInt trySplit() {
 return null;
 }
 }
}

---

Standard Java7 version

What if the code was implemented as a simple Java problem?

public final class Problem2Java7 extends Problem<Integer> {
 public Problem2Java7() {
 super("Problem 2 Java7", 1000, 100);
 }
 @Override
 public Integer execute() {
 int sum = 0;
 int fib = 1;
 int prev = 1;
 int tmp = 0;
 while (fib <= 4000000) {
 tmp = fib;
 fib += prev;
 prev = tmp;
 if ((fib & 1) == 0) {
 sum += fib;
 }
 }
 return sum;
 }
}

Conclusion

The performance results are somewhat revealing....

Problem 2 => 4613732 (hot 0.00095ms - cold 0.035ms (total 9.018ms))
Problem 2 - IntStream => 4613732 (hot 0.00071ms - cold 0.036ms (total 10.038ms))
Problem 2 - rolfl java8 => 4613732 (hot 0.00061ms - cold 0.023ms (total 14.494ms))
Problem 2 Java7 => 4613732 (hot 0.00018ms - cold 0.018ms (total 7.779ms))

To me, this means that, for this type of CPU-intensive work, the overhead of the streams is still significant. It is essentially 5 times faster than your code, and 3 times faster than the fastest Streams alternative.

This problem is a tiny problem though... the computations are really small, and the method overhead of the streams will be the bulk of the runtime. I don't know where the performance/usability curve will cross from being 'wasteful' to 'useful', but, it is not useful for this problem.

Also, because I am new to this, the standard Java is more readable ;-)

The Framework

I took the liberty of playing with your framework. This is what it looks like now in my environment:

Problem.java

public abstract class Problem<T> {
 private final String name;
 private final int warmup;
 private final int avgcnt;
 public Problem(String name, int warmups, int realruns) {
 this.name = name;
 this.warmup = warmups;
 this.avgcnt = realruns;
 }
 public String getResult() {
 return String.valueOf(execute());
 }
 public final int getWarmups() {
 return warmup;
 }
 public final int getRealRuns() {
 return avgcnt;
 }
 public final String getName() {
 return name;
 }
 public abstract T execute();
}

ProjectEuler.java

import java.util.ArrayList;
import java.util.List;
import java.util.function.Consumer;
public class ProjectEuler {
 private static final double MILLION = 1_000_000.0;
 private final List<Problem<?>> problems = new ArrayList<>();
 private final int longestname;
 public ProjectEuler() {
 // problems.add(new Problem1());
 problems.add(new Problem2IntStream());
 problems.add(new Problem2());
 problems.add(new Problem2Java7());
 problems.add(new Problem2Java8());
 int namelen = 0;
 for (Problem<?> p : problems) {
 namelen = Math.max(namelen, p.getName().length());
 }
 longestname = namelen;
 }
 private void process() {
 problems.stream().forEachOrdered(new ProblemConsumer());
 }
 /**
 * @param args
 * the command line arguments
 */
 public static void main(String[] args) {
 ProjectEuler pe = new ProjectEuler();
 pe.process();
 System.out.println("\n\nRound 1 Complete\n\n");
 pe.process();
 }
 private class ProblemConsumer implements Consumer<Problem<?>> {
 @Override
 public void accept(final Problem<?> problem) {
 final long basetime = System.nanoTime();
 final int wreps = problem.getWarmups();
 final int rreps = problem.getRealRuns();
 long btime = System.nanoTime();
 final String result = problem.getResult();
 btime = System.nanoTime() - btime;
 for (int i = wreps; i > 0; i--) {
 String actual = problem.getResult();
 if (!result.equals(actual)) {
 throw new IllegalStateException("Unexpected result "
 + actual);
 }
 ;
 }
 System.gc();
 final long start = System.nanoTime();
 for (int i = rreps; i > 0; i--) {
 problem.execute();
 }
 final long end = System.nanoTime();
 final long elapsed = end - start;
 String actual = problem.getResult();
 System.out.printf("%-" + longestname
 + "s => %s (hot %.5fms - cold %.3fms (total %.3fms))\n",
 problem.getName(), actual, (elapsed / MILLION) / rreps,
 btime / MILLION, (end - basetime) / MILLION);
 }
 }
}

• skiwi: That is quite a long response and I really appreciate it. Firstly, I did not intend this code for performance, though still appreciate the remarks on it. Secondly, really thanks a lot of finding the PrimitiveIterator.OfInt, I was searching for that one earlier today aswell!
• rolfl: Yeah, it is a long response ... and I missed a key thing anyway: you asked if the code was readable? Yes, Yes it is (now that I understand a bit more about it...) Let me edit.

Answer 2

It can be easily and clearly resolved by this:

UnaryOperator<BigInteger[]> fibonacci = (m) -> new BigInteger[]{m[1], m[0].add(m[1])};
Stream.iterate(new BigInteger[]{BigInteger.ONE,BigInteger.ONE}, fibonacci)
 .limit(32) 
 .map(n -> fibonacci.apply(n)[0])
 .filter(n->n.compareTo(BigInteger.valueOf(4000000))<1)
 .filter(n->n.mod(BigInteger.valueOf(2))==BigInteger.ZERO)
 .reduce((m,n)->m.add(n)).ifPresent(System.out::println);

First define the Fibonacci operation based on mathematical definition. After begin to iterate defining the seed (1,1). Here for simplicity, we used an array of BigInteger but we could have defined a class (e.g. Tuple). Finally you filter based on upper hypotesis that max value should be less than 4,000,000 and that we only retain odd number. We then sum all the values (reduce operation) and we output it to the user. Remind that all stream is infinite. In this case the operation continue until the limit(32) is defined. You can limit by maximux iteration in jdk8 or wait to jdk9 to limit it by value.