Java puzzle (Sum of even Fibonacci numbers)
Write a function which calculates the sum of even Fibonacci numbers.
public static void main(String... args) {
for(int i=1;i<22;i++)
System.out.print(sumEvenFibonacci(i) + " ");
}
public static long sumEvenFibonacci(int n) {
// add code here.
return sum;
}
prints
0 0 2 2 2 10 10 10 44 44 44 188 188 188 798 798 798 3382 3382 3382 14328For bonus points, optimise the sumEvenFibonacci method so it contains only one condition and doesn't test for even or odd. [Click for sample solution]
This should works
ReplyDeletepublic static long sumEvenFibonacci(int n) {
long sum = 0;
long f1 = 0;
long f2 = 1;
for (int i = 0; i < n / 3; i++) {
f1 += 2 * f2;
f2 = 2 * f1 - f2;
sum += f1;
}
return sum;
}
@Eugen, That's a good solution. Can you do it without division or multiplication? ;) (Only the division wouldn't be optimised by the JIT)
ReplyDeleteA more traditional approach with some unsafe counter handling (to reduce the code size):
ReplyDeletelong sum = 0;
int f1 = 1;
int f2 = 0;
int counter = 1;
for (int i = 0; i < n; i++) {
if (counter % 3 == 0)
sum += f1;
f1 += f2;
f2 = f1 - f2;
counter++;
}
return sum;
But I really-really like Eugen's solution :)
Here's the safest solution:
ReplyDeleteif (counter % 3 == 0) {
counter = 0;
sum += f1;
}
if (counter == 3)
ReplyDeleteAn absolute divisionless condition. Okok. I'm stopping now :)
Similar problem can be found at Project Euler. Solve to unlock "official" solution and discussion.
ReplyDelete@Lexandro, It uses two conditions, do you need a "counter" if you have "i" ;)
ReplyDeleteThis is the solution I came up with.
ReplyDeletepublic static long sumEvenFibonacci(int n) {
long a = 1, b = 1, sum = 0;
for (int i = n; i > 2; i -= 3) {
long c = a + b;
sum += c;
a = b + c;
b = a + c;
}
return sum;
}
I don't know why, but when I use this for loop:
ReplyDeletefor (int i = 2; i < n; i += 3);
the code is 4% faster.
Finally I did a last test with a jre 7 and the same class files; in this case the fastest loop is:
ReplyDeletefor (int i = n; i > 2; i -= 3);
The JIT compilation result change from one VM to an other.
This comment has been removed by a blog administrator.
ReplyDeleteThis comment has been removed by the author.
ReplyDelete