# Project Euler #2 Efficiency

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 N, find the sum of the even-valued terms.

I'd like to reduce the complexity of my code.

import java.math.BigInteger;
import java.util.Scanner;

public class Solution {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);
int testCases = sc.nextInt();
for (int i = 0; i < testCases; i++) {
BigInteger input = sc.nextBigInteger();
System.out.println(calculate(input));
}
}

public static BigInteger calculate(BigInteger input) {
BigInteger fib1 = new BigInteger("0");
BigInteger fib2 = new BigInteger("1");
BigInteger sum = new BigInteger("0");

BigInteger fib = new BigInteger("0");
while (input.compareTo(fib)>0) {

if (fib.doubleValue() % 2 == 0)
fib1 = fib2;
fib2 = fib;

}

return sum;
}

}

• The Project Euler solution guide regarding this problem gives an improvement that reduces runtime by a factor of (at least) 3. True, it's not an order of magnitude, but watching those constants will help you in other problems. – apnorton Oct 19 '14 at 12:19
• There have been answers (now deleted) questioning the sharing of project euler solutions. There is a meta post about project euler solutions here (and more generally here) (to summarize: it is know that they would prefer solutions not to be shared, but CodeReview will still accept them. Stating that it is a project euler solution in the title is encouraged, so that people who don't want spoilers can avoid them). – tim Oct 19 '14 at 16:59

The test

if (fib.doubleValue() % 2 == 0)


does not produce the correct result for numbers with more than 17 digits, because that exceeds the precision of a double. Actually it returns true for 8944394323791464 and all subsequent Fibonacci numbers. That is not relevant for the concrete problem here (see below), but if you want to work with BigInteger then you should replace this with

if (fib.remainder(bigTwo).equals(BigInteger.ZERO))


where bigTwo is defined as

BigInteger bigTwo = new BigInteger("2");


Project Euler Problem #2 asks for the sum of all even-valued Fibonacci values not exceeding 4 million, so using BigInteger is not really necessary. All numbers fit into the range of int, and the above test simplifies to

if (fib % 2 == 0)


(I also planned to tell that using int instead of BigInteger makes the program more efficient, but it turned out that the difference in running time is not significant.)

First off, I'm not sure whether you are targeting Java 7 or Java 8.

If you are targeting Java 7, this looks like a nice solution. The only things I can see are a small nit (the if statement should have curly braces around the consequent) and that the names for fib, fib1, and fib2 could be more descriptive. Possibly fibNext, fibCurrent, and fibPrevious respectively?

If you are targeting Java 8, you can use Streams to decouple each individual step. You'd need to make a FibbonachiIterator class that implements Iterator<BigInteger> which just generates Fibonacci numbers, turn it into a stream, filter out the odd Fibonacci numbers, and then reduce with BigInteger.add. It'll be longer, and implementing Iterator could be seen as more complex, but the usage of the iterator is simpler.