# Project Euler "Even Fibonacci numbers" in Java 8

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() {

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.

• 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. Commented Feb 21, 2014 at 23:01
• @rolfl Added all code on request. Commented Feb 22, 2014 at 12:56
• 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. Commented Feb 22, 2014 at 18:16
• @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? Commented Feb 22, 2014 at 18:19
• 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). Commented Feb 22, 2014 at 18:20

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...

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:

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

No reason to do anything here....

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
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() {

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);
}
}
}
• 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! Commented Feb 22, 2014 at 21:47
• 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. Commented Feb 22, 2014 at 21:50

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)