1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. May 5, 2012 #1
    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. jcsd
  3. May 5, 2012 #2

    Borek

    User Avatar

    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
  4. May 5, 2012 #3
    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.
     
  5. May 5, 2012 #4

    Borek

    User Avatar

    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?
     
  6. May 5, 2012 #5
    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
     
    Last edited: May 5, 2012
  7. May 6, 2012 #6
    ups....
     
  8. May 8, 2012 #7
    Code (Text):
    s=0
    for n=0 ... 4000000
        if is.even( fibonacci(n) )
            s += fibonacci(n)
    print s
    [tex]\approx 5.404785360620536653971914908\cdot 10 ^{1204119}[/tex]
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Project Euler Problem 002: Fibonacci sequence (in C++)
  1. C++ Problem (Replies: 6)

  2. C++ problem (Replies: 3)

Loading...