Getting Only Even Numbers in C++

Question

I'm currently attempting to go through Project Euler to increase my understanding of C++, but I'm stumped on problem 2 on the part of how to get only even numbers in a Fibonacci sequence. I'm 99% sure that you have to use the % operator just from things I've looked at online, but all I understand of it is that it takes the remainder of something (ex 11/3 = 9 w/ remainder of 2), and so I have no idea on how to incorporate it into the code.

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

using namespace std;

int main()
{
int first = 1;
int second = 2;
int next;

cout << first << endl;
cout << second << endl;
if (next < 4000000)
{
    for (int i = 0; i < 500000; i++)
    {
        next = first + second;
        first = second;
        second = next;
    }
}


cout << next << endl;

return 0;
}

What is the value of `next` when `if (next < 4000000)` is first executed? — chux - Reinstate Monica, Mar 03 '17 at 21:33
"I'm currently attempting to go through Project Euler to increase my understanding of C++" - Euler may improve your maths skills, but it's unlikely to increase your understanding of C++, or any other programming language, significantly. — , Mar 03 '17 at 21:34
Every third Fibonacci number is even (1st, fourth, 7th, etc) — Peter, Mar 03 '17 at 21:50
@Logan87654321 Agree `next` should be 0, then why does code not set it to 0 rather than leave it uninitialized? — chux - Reinstate Monica, Mar 03 '17 at 21:57
@chux i'm dumb and forgot to set it to 0. ended up setting it to 0, moving the if statement inside the for statement, moving the contents of the for statement inside the aforementioned if statement, and making a new if statement with next % 2 == 0 to find the evens. — , Mar 03 '17 at 21:59

score 1 · Accepted Answer · answered Mar 03 '17 at 21:46

1

You need to check the evenness of number using modulo operator.

for (int i = 0; i < 500000; i++) {
    next = first + second;
    if(next%2 == 0) {
        cout << next << "\n";
    }
    first = second;
    second = next;
}

For more details about modulo operator please read the given link.

answered Mar 03 '17 at 21:46

Shravan40

8,922
6
28
48

Division is expensive. A better solution is to use the binary '&' operator and test the LSB: `if (!(number & 1)){ ...` – frasnian Mar 03 '17 at 21:51
2

@frasnian `next%2 == 0` and `next&1 == 0` may emit the exact same code. This micro optimization of "Division is expensive" does not hold with modern compilers. Further, on rare one's complement machines `next&1` is not a correct even test for negative numbers. See http://stackoverflow.com/q/160930/2410359 – chux - Reinstate Monica Mar 03 '17 at 22:00
@frasnian -- [No division is done for either method](https://godbolt.org/g/8WrqOM). Compiler writers for decades have known how to recognize and optimize division when possible. – PaulMcKenzie Mar 03 '17 at 22:33
@frasnian a better solution is to write the code in the most straightforward way possible and then if it's too slow to benchmark it and adjust as needed. As you can see, no division performed, instead it calls "test 1" which does a bitwise and against 1: https://godbolt.org/g/XeZoKs – xaxxon Mar 04 '17 at 05:44
@xaxxon - For me, though, & is as intuitive as %. Also, I still do a fair amount in assembly, so it's a pretty deeply ingrained reflex response. That said, I agree. – frasnian Mar 04 '17 at 23:37
@frasnian regardless, you are suggesting doing it for performance reasons, which is both technically incorrect and the wrong motivation behind choosing a style, regardless. – xaxxon Mar 05 '17 at 04:40

Getting Only Even Numbers in C++

1 Answers1