Error in Long integer output

Question

Below is one of the solutions to the Project Euler challenges (Problem 2). This has been sitting in a folder on my HD for a few months and I tried to compile/run it today. When I did I noticed I only got an output of 4613732 for each value (except 0 which returns 0). I'm not sure what's going on here, and if memory serves me correctly this did work when I wrote it up. Can anyone point out the flaw? Thanks.

#include <iostream>
/*
 * 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.
 */
long int Fib(long int n) //This is a separate function, called Fib(). It is called in the main function below.
{
    if (n < 2)
    {
        return 1;
    }
    else
    {
        return Fib(n-1) + Fib(n-2);
    }
}

int main()
{
    long int sum = 0;
    long int upper;
    std::cout << "Enter an upper bound for the Fibonacci sequence: ";

    /* The Fibonacci sequence will hit 4,000,000 between 35 and 40
    *  iterations.
    */ 

    std::cin >> upper;
    std::cout << std::endl;

    for (int i = 1; i < upper; i++)
    {
        for (Fib(1); Fib(i) < 4000000; i++)
        {
            if ((Fib(i) % 2) == 0 )
            {
                sum = sum + Fib(i);
            }
        }
    }
    std::cout << std::endl;
    std::cout << sum << std::endl; //This is the correct sum for the problem.
    return 0;
}

Answer 1

Your using the same variable in both your for loops, and incrementing it in both. A simple solution would be to modify your first for loop, and remove the second:

for (int i = 1; i < upper && fib(i) < 4000000; i++)
    {
        if ((Fib(i) % 2) == 0)
        {
            sum = sum + Fib(i);
        }
    }

As a side note: Your method is extremely inefficient, as you are calculating fib(i) between one and three times per loop. The first method to reduce the calculation time is pretty simple:

for (int i = 1; i < upper && fib(i) < 4000000; i++)
    {
        int tempFib = Fib(i);
        if (tempFib % 2) == 0)
        {
            sum = sum + tempFib;
        }
    }

This new code saves the fib when it is first calculated in the loop, meaning its only called twice. You can move the fib(i) < 4000000 statement outside the for loop line and into its own line to reduce it to one Fibonacci call per loop. However this is still far from optimal as you are still calling it once per loop.

After reviewing your code somewhat more, I don't see why you have the prompt for an upper bound. You already have the boundary of fib(i) < 4000000.

My hint is to have one loop calculating the Fibbonaci numbers that at the same time is calculating the sum. This method will result in one Fibbonci calculation, rather than around thirty five.

Iterative method of Fibonacci:

//Calculates the nth Fibonacci number (excluding the first one)
int prev = 1;
int cur = 2;
for( int i = 2; i <= n; ++i){
    int temp = prev + cur;
    prev = cur;
    cur = temp;
}
return cur;

Answer 2

You're incrementing i in both for loops. I don't see what the second for loop is for. I'd do this instead:

for (int i = 1; i < upper; i++)
{
    if (Fib(i) >= 4000000)
    {
        break;
    }

    if ((Fib(i) % 2) == 0 )
    {
        sum = sum + Fib(i);
    }
}

Answer 3

Even after fixing the double-loop issue mentioned by the other posts, upper seems to be only a fast way to bail out, before reaching the four million mark. As the four million mark is reached with an input of 32, all numbers above 32 will simply show the final result: 4613732

I have absolutely no idea how your code was getting a right result.