More efficient solution: Project Euler #2: Even Fibonacci Numbers

Question

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.

My code: (which works fine)

public static void main(String[] agrs){
    int prevFirst=0;
    int prevSecond=1;
    int bound=4_000_000;
    int evenSum=0;

    boolean exceed=false; //when fib numbers > bound
    while(!exceed){
        int newFib=prevFirst + prevSecond;
        prevFirst = prevSecond;
        prevSecond = newFib;

        if(newFib > bound){
            exceed=true;
            break;
        }

        if(newFib % 2 == 0){
            evenSum += newFib;
        }
    }

    System.out.println(evenSum);

}

I'm looking for a more efficient algorithm to do this question. Any hints?

If you have working code that you would like to improve, consider posting/migrating this to [Code Review SE](http://codereview.stackexchange.com). A general "How can I improve this" *might* be considered by some to be too broad for Stack Overflow. — awksp, Jun 30 '14 at 05:09
A `while(true)` is sufficient since you `break` out of the loop anyway. — laune, Jun 30 '14 at 05:34
@laune: yes, but a `break` is not advisable. Most compiler will poorly optimize such code. For instance in a loop, the compiler will consider the chance of *repeating* the loop higher than breaking the loop (since in most cases a loop is repeated if iterating over arrays, etc.). In an `if`-statement, some compilers argue that the chance of executing the body is higher than not... This has impact on how compilers structure code and some processors as well. — Willem Van Onsem, Jun 30 '14 at 05:57
@CommuSoft jumps in any form are poor coding style more often than not. I just wanted to point out that exceed is superfluous. — laune, Jun 30 '14 at 06:12
@laune: That's of course the "goto statement is considered harmful" vs. "goto statement is considered harmful is considered harmful" discussion :P — Willem Van Onsem, Jun 30 '14 at 06:15
The final comment: comparing the original implementation with @CommuSoft's algorithm: execution time goes down from 7.7 to 2.6, down to 33%. (Although, it doesn't register with a single execution.) — laune, Jun 30 '14 at 06:17
@user262945 after get rid of the modulo (by & or by computing 3 numbers per sum) is this too easy for modern machines. I get 2-3us computation time, if I increase N 100 times I still get the same time (so the overhead of time measurement, system calls and C++ engine is bigger then computation itself) ... so I do not see any point to further improvement (unless you compute very big N which is not the case for problem 2). PS I use old 32-bit compiler from Borland/Embarcadero with optimizations off for this! — Spektre, Jun 30 '14 at 07:05

score 13 · Accepted Answer · edited Jun 20 '20 at 09:12

13

When taking the following rules into account:

even + even = even

even + odd = odd

odd + even = odd

odd + odd = even

The parity of the first Fibonacci numbers is:

o o e o o e o o e ...

Thus basically, you simply need to do steps of three. Which is:

(1,1,2)
(3,5,8)
(13,21,34)

Given (a,b,c) this is (b+c,b+2*c,2*b+3*c).

This means we only need to store the two last numbers, and calculate given (a,b), (a+2*b,2*a+3*b).

Thus (1,2) -> (5,8) -> (21,34) -> ... and always return the last one.

This will work faster than a "filter"-approach because that uses the if-statement which reduces pipelining.

The resulting code is:

int b = 1;
int c = 2, d;
long sum = 0;
while(c < 4000000) {
    sum += c;
    d = b+(c<<0x01);
    c = d+b+c;
    b = d;
}
System.out.println(sum);

Or the jdoodle (with benchmarking, takes 5 microseconds with cold start, and on average 50 nanoseconds, based on the average of 1M times). Of course the number of instructions in the loop is larger. But the loop is repeated one third of the times.

edited Jun 20 '20 at 09:12

Community

1
1

answered Jun 30 '14 at 05:26

Willem Van Onsem

443,496
30
428
555

"This will work faster than a "filter"-approach because that uses the if-statement which reduces pipelining" ? you still have to calculate a,b,c in every iteration in order to be able to calculate the next iteration. how is that more efficient ? – Nir Alfasi Jun 30 '14 at 05:31
Well an if statement will break the pipeline in a CPU. In most cases a CPU has a pipeline of length six. As a consequence the throughput will be reduced by the `if`-statement. That's why for instance Graphics programs try to solve a lot of things with bit-manipulation instead of using `if` statements. Except for interpreted languages, `if`-statements are slow compared to other instructions. – Willem Van Onsem Jun 30 '14 at 05:33
2

+1 - I do like a little math reasoning prior to just churning out the code ;-) – laune Jun 30 '14 at 05:37
@alfasin: I'm intersted in the benchmarks of a program with `if`-statements. I performed tests on jdoodle and this results in 5 microseconds... – Willem Van Onsem Jun 30 '14 at 05:37
1

@laune That's generally how Project Euler goes; especially when you start getting into the higher levels – Dennis Meng Jun 30 '14 at 05:37
Well, a `while` is (according to a compiler) an `if` as well with a jump instruction. I am wondering however what the difference is with your approach. Of course the magnitude of the execution time won't change. – Willem Van Onsem Jun 30 '14 at 05:45
1

well, you'll get +1 from me because you **did** save a modulo check! – Nir Alfasi Jun 30 '14 at 05:48

Nir Alfasi · Answer 2 · 2014-06-30T05:51:02.467

You can't improve it much more, any improvement that you'll do will be negligible as well as depended on the OS you're running on.

Example:
Running your code in a loop 1M times on my Mac too 73-75ms (ran it a few times).
Changing the condition:

if(newFib % 2 == 0){

to:

if((newFib & 1) == 0){

and running it again a few times I got 51-54ms.

If you'll run the same thing on a different OS you might (and probably will) get different results.
even if we'll consider the above as an improvement, divide ~20ms in 1M and the "improvement" that you'll get for a single run is meaningless (~20 nanos).

score 3 · Answer 3 · answered Jun 30 '14 at 09:47

3

assuming consecutive Fibonacci numbers

a, b,
c =  a +  b,
d =  a + 2b,
e = 2a + 3b,
f = 3a + 5b,
g = 5a + 8b = a + 4(a + 2b) = a + 4d,

it would seem more efficient to use
ef₀ = 0, ef₁ = 2, ef_n = ef_n-2 + 4 ef_n-1

answered Jun 30 '14 at 09:47

greybeard

2,249
8
30
66

Smart, very smart! :D – Silviu Burcea Jun 30 '14 at 10:18

Spektre · Answer 4 · 2014-07-01T19:44:25.307

as I mentioned in my comment there is really no need to further improvement. I did some measurements

looped 1000000 times the whole thing
measure time in [ms]
ms / 1000000 = ns
so single pass times [ns] are these:
1. [176 ns] - exploit that even numbers are every third
2. [179 ns] - &1 instead of %2
3. [169 ns] - &1 instead of %2 and eliminated if by -,^,&
  [edit1] new code
4. [105 ns] - exploit that even numbers are every third + derived double iteration of fibonaci [edit2] new code
5. [76 ns] - decreased operand count to lower overhead and heap trashing
the last one clearly wins on mine machine (although I would expect that the first one will be best)
all was tested on Win7 x64 AMD A8-5500 3.2GHz
App with no threads 32-bit compiler BDS2006 Trubo C++
1,2 are nicely mentioned in Answers here already so I comment just 3:
```
s+=a&(-((a^1)&1));
```
(a^1) negates lovest bit
((a^1)&1) is 1 for even and 0 for odd a
-((a^1)&1)) is -1 for even and 0 for odd a
-1 is 0xFFFFFFFF so anding number by it will not change it
0 is 0x00000000 so anding number by it will be 0
hence no need for if
also instead of xor (^) you can use negation (!) but that is much slower on mine machine

OK here is the code (do not read further if you want to code it your self):

//---------------------------------------------------------------------------
int euler002()
    {
    // 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.
    int a,a0=0,a1=1,s=0,N=4000000;
/*
    //1. [176 ns]
    a=a0+a1; a0=a1; a1=a;   // odd
    a=a0+a1; a0=a1; a1=a;   // even
    for (;a<N;)
        {
        s+=a;
        a=a0+a1; a0=a1; a1=a;   // odd
        a=a0+a1; a0=a1; a1=a;   // odd
        a=a0+a1; a0=a1; a1=a;   // even
        }

    //2. [179 ns]
    for (;;)
        {
        a=a0+a1; a0=a1; a1=a;
        if (a>=N) break;
        if ((a&1)==0) s+=a;
        }
    //3. [169 ns]
    for (;;)
        {
        a=a0+a1; a0=a1; a1=a;
        if (a>=N) break;
        s+=a&(-((a^1)&1));
        }
    //4. [105 ns] // [edit1]
    a0+=a1; a1+=a0; a=a1;       // 2x
    for (;a<N;)
        {
        s+=a; a0+=a1; a1+=a0;   // 2x
        a=a0+a1; a0=a1; a1=a;   // 1x
        }
*/
    //5. [76 ns] //[ edit2]
    a0+=a1; a1+=a0;             // 2x
    for (;a1<N;)
        {
        s+=a1; a0+=a1; a1+=a0;  // 2x
        a=a0; a0=a1; a1+=a;     // 1x
        }

    return s;
    }
//---------------------------------------------------------------------------

[edit1] faster code add

CommuSoft suggested to iterate more then 1 number per iteration of fibonaci to minimize operations.
nice idea but code in his comment does not give correct answers
I tweaked a little mine so here is the result:
[105 ns] - exploit that even numbers are every third + derived double iteration of fibonaci
this is almost twice the speedup of 1. from which it is derived
look for [edit1] in code or look for //4.

[edit2] even faster code add - just reorder of some variable and operation use for more speed - [76 ns] decreased operand count to lower overhead and heap trashing

I definitely agree this problem is too easy for modern machines, but the question is interesting to learn how to optimize code. :) — Willem Van Onsem, Jun 30 '14 at 08:20
@CommuSoft yes but Project Euler does this gradually there are many problems there more then once but with much bigger payload and usually after all the techniques required is presented in previous problems. I stop optimizing if solution is faster or around 1 ms in runtime. So my point is do not waste time on unnecessary optimization there will be much more time for that in future problems where without optimizations the code will not work in 'finite' time... — Spektre, Jun 30 '14 at 08:31
What happens when you replace the nine instructions in case one with `a=a0+(a1<<0x01); a1 += a+a0; a0 = a;`? One would expect the number of primitive instructions in the loop to be reduced. — Willem Van Onsem, Jul 01 '14 at 15:34
@CommuSoft it is possible your way could be faster (if you mean to do it in code 1.) was too lazy to evaluate that equation. BTW how did you get code formatting into comment? — Spektre, Jul 01 '14 at 18:44
You put code between backquotes (`) not to be confused with quotes ('), you can use this in answers and questions as well. — Willem Van Onsem, Jul 01 '14 at 18:53
@CommuSoft your equation is wrong somewhere (gives wrong result) I did mine an it works ... have edited answer (added `[edit1]`). Tripple iteration would be even faster but I cant get it to work ... (silly simple math is usually the worst :) ) — Spektre, Jul 01 '14 at 19:30
@CommuSoft after little tweaking I think `[edit2]` is final. [76 ns] runtime. — Spektre, Jul 01 '14 at 19:46

score 1 · Answer 5 · edited Oct 21 '16 at 13:42

if you check Fibonacci series, for even numbers 2 8 34 144 610 you can see that there is a fantastic relation between even numbers, for example:

34 = 4*8 + 2,
144 = 34*4 + 8,
610 = 144*4 + 34;

this means that next even in Fibonacci can be expressed like below

Even(n)=4*Even(n-1)+E(n-2);

in Java

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int t = in.nextInt();
    for(int a0 = 0; a0 < t; a0++){
        long n = in.nextLong();
        long a=2;
        long b=8;
        long c=0;
        long sum=10;
        while(b<n)
        {
            sum +=c;
            c=b*4+a;
            a=b;
            b=c;     
        }
        System.out.println(sum);
    }
}

Freeze Francis · Answer 6 · 2016-05-30T12:08:48.153

F(n) be the nth Fibonnaci number i.e F(n)=F(n-1)+F(n-2)
Lets say that F(n) is even, then
F(n) = F(n-1) + F(n-2) = F(n-2) + F(n-3) + F(n-2)
F(n) = 2F(n-2) + F(n-3)
--This proves the point that every third term is even (if F(n-3) is even, then F(n) must be even too)

F(n) = 2[F(n-3) + F(n-4)] + F(n-3)
= 3F(n-3) + 2F(n-4)
= 3F(n-3) + 2F(n-5) + 2F(n-6)

From eq.1:
F(n-3) = 2F(n-5) + F(n-6)
2F(n-5) = F(n-3) - F(n-6)

F(n) = 3F(n-3) + [F(n-3) - F(n-6)] + 2F(n-6)
= 4F(n-3) + F(n-6)

If the sequence of even numbers consists of every third number (n, n-3, n-6, ...)

Even Fibonacci sequence:

E(k) = 4E(k-1) + E(k-2)

Fib Sequence F= {0,1,1,2,3,5,8.....}
Even Fib Sequence E={0,2,8,.....}
CODE:

 public static long findEvenFibSum(long n){
     long term1=0;
     long term2=2;
     long curr=0;
     long sum=term1+term2;          
        while((curr=(4*term2+term1))<=n){
            sum+=curr;
            term1=term2;
            term2=curr;             
        }
  return sum;
  }

Late in presenting this sequence without non-even elements - in my eyes, helpful answers are never late. If you don't think it spoiling the fun, work out the sequence giving the result directly. — greybeard, May 30 '16 at 07:57

score -1 · Answer 7 · edited Apr 23 '16 at 21:41

-1

The answer for project Euler problem 2 is(in Java):

int x = 0;
int y = 1;
int z = x + y;
int sumeven = 0;
while(z < 4000000){
    x = y;
    y = z;
    z = x + y;
    if(z % 2 == 0){
        sumeven += z; /// OR sumeven = sumeven + z
    }
}
System.out.printf("sum of the even-valued terms: %d \n", sumeven);

This is the easiest answer.

edited Apr 23 '16 at 21:41

Jose Gómez

3,110
2
32
54

answered Apr 23 '16 at 20:24

M. Paranhos

1

If this is the plainest solution to Project Euler problem #2, how does it answer `More efficient solution`? – greybeard Apr 24 '16 at 07:39

More efficient solution: Project Euler #2: Even Fibonacci Numbers

7 Answers7

E(k) = 4E(k-1) + E(k-2)