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

1. May 5, 2012

newfeeling

1. The problem statement, all variables and given/known data
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.

2. Relevant equations
n/a

3. 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?

2. May 5, 2012

Staff: Mentor

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

Have you checked how large Fibonacci numbers get?

Last edited: May 5, 2012
3. May 5, 2012

newfeeling

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.

4. May 5, 2012

Staff: Mentor

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?

5. May 5, 2012

RoshanBBQ

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]

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

Last edited: May 5, 2012
6. May 6, 2012

ups....

7. May 8, 2012

Xitami

Code (Text):
s=0
for n=0 ... 4000000
if is.even( fibonacci(n) )
s += fibonacci(n)
print s
$$\approx 5.404785360620536653971914908\cdot 10 ^{1204119}$$