Comp Sci Project Euler Problem 002: Fibonacci sequence (in C++)

[newfeeling]

Homework Statement

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.

Homework Equations

n/a

The Attempt at a Solution

#include <cstdlib>
#include <iostream>
using namespace std;

int main()
{

int n;
int fibnum;
int sum;
int num2;
int num1;
int limit;

num2 = 1;
num1 = 0;
fibnum = 0;
sum = 0;

cout << "n?" << endl;
cin >> limit;


for(n = 0; n < limit; n += 1)
{
fibnum = num2 + num1;
if(fibnum % 2 == 0)
{
sum += fibnum;
}

num1 = num2;
num2 = fibnum;

}

cout << sum << endl;

return EXIT_SUCCESS;

}This chunk of code allows me to get the correct sum when "limit" is a relatively small number (e.g. 10 will return 44 and 5 will return 10), but doesn't work for really big numbers...like 4,000,000. I'm not looking for a solution; I know that if my algorithm were designed correctly I would have already gotten the correct answer, but clearly there is some glaring flaw that I'm not noticing. Am I on the right track with this method at least, or am I wasting my time beating my head over my desk with this approach?

 

[Borek]

What do you mean by "doesn't work"? What's happening?

Have you checked how large Fibonacci numbers get?

 

[newfeeling]

What do you mean by "doesn't work"? What's happening?

Have you checked how large Fibonacci numbers get?

When I punch in sufficiently large number for the program, I get clearly bogus results like -98123786458 for example; this problem does not arise with numbers that are not particularly big. And yes I have checked how large Fibonacci numbers get O_O.

 

[Borek]

You are using either a 32 or 64 bit integers, are they sufficiently large to store Fibonacci numbers? How many bits needed to store 4000000th Fibonacci number?

 

[RoshanBBQ]

Homework Statement

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.

Homework Equations

n/a

The Attempt at a Solution

#include <cstdlib>
#include <iostream>
using namespace std;

int main()
{

int n;
int fibnum;
int sum;
int num2;
int num1;
int limit;

num2 = 1;
num1 = 0;
fibnum = 0;
sum = 0;

cout << "n?" << endl;
cin >> limit;


for(n = 0; n < limit; n += 1)
{
fibnum = num2 + num1;
if(fibnum % 2 == 0)
{
sum += fibnum;
}

num1 = num2;
num2 = fibnum;

}

cout << sum << endl;

return EXIT_SUCCESS;

}This chunk of code allows me to get the correct sum when "limit" is a relatively small number (e.g. 10 will return 44 and 5 will return 10), but doesn't work for really big numbers...like 4,000,000. I'm not looking for a solution; I know that if my algorithm were designed correctly I would have already gotten the correct answer, but clearly there is some glaring flaw that I'm not noticing. Am I on the right track with this method at least, or am I wasting my time beating my head over my desk with this approach?

It asks for the sum of every part of the sequence that does not exceed 4 million. It doesn't ask for the sum of the first 4 million in the sequence.

For example, if I had a sequence
s_n = 2^n, n from 0 to infinity

then the sum of the first 5 would be
1 + 2 + 4 + 8 + 16
whereas the sum of all values that do not exceed five in the sequence would be
1 + 2 + 4

Do you see the difference?

In this circumstance, you should probably look into doing a while loop since you do not know exactly how many iterations you will need to do.

On a side note, you can initialize a value to a variable when you declare it, e.g.
int num2 = 1;

And to answer the question of why your code fails with such an insane limit, take a look at this:
http://www.wolframalpha.com/input/?i=fibonacci[11%2C1]
So you plug in n+1 to see what the nth fib is. Let's plug in 100...
http://www.wolframalpha.com/input/?i=fibonacci[101%2C1]
The answer is 573147844013817084101

Your finite-sized integers are overflowing. They simply cannot hold a number that large.

Let's see what Wolfram says 4,000,000 is:
http://www.wolframalpha.com/input/?i=fibonacci[4000001%2C1]
2.63331342366565668198735005895985564737121509 × 10^835950

 

[Xitami]

ups...

 

[Xitami]

s=0
for n=0 ... 4000000
    if is.even( fibonacci(n) )
        s += fibonacci(n)
print s

\approx 5.404785360620536653971914908\cdot 10 ^{1204119}