Project Euler #2 Even Fibonacci numbers

Question

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.

Solution:

#include <stdio.h>
#include <stdlib.h>

void print_answer(int limit){

    int a = 1; //1st term
    int b = 2; //2nd term
    int even_fibbonaci = 0; //start as zero,because of the loop
    int sum = 2;//sum of even up to 2nd term
    int steps_taken = 0;
    do{
        sum += even_fibbonaci;
        even_fibbonaci = 2*a + 3*b; //even fibbonaci
        a += 2*b; //fibbonaci just before even fibbonaci
        b = even_fibbonaci;
        steps_taken++;
    }while(even_fibbonaci<limit);

    printf("Sum of the even-valued fibbonaci below %d\n",limit);
    printf("Answer = %d, Steps Taken = %d\n",sum,steps_taken);

}

int main(int argc, char ** argv){

    if(argc!=2){
        printf("Invalid number of arguments\n");
        printf("Usage a.exe [limit]\n");
        return -1;
    }

    int limit = atoi(argv[1]);

    if(limit < 3){
        printf("Invalid input\n");
        printf("Enter a limit of 3 or more\n");
        return -1;      
    }

    print_answer(limit);

    return 0;
}

For limit = 4000000

Execute as {executable} [limit]

Sum of the even-valued fibbonaci below 4000000

answer = 4613732, steps taken = 11

Compiler:

Answer 1

I'd suggest a couple of things.

Firstly, this is a typical Euler problem example in that Euler usually provides an example test case. Build that into your code so that you confidently refactor.

Secondly, I recommend separating the algorithm from the reporting of its results; this again supports writing built in tests without generating unwanted output.

Taking this approach, you remove the need for a command line or inputs; just keep adding test cases to the code.

I've also taken the liberty of removing/renaming a and b from the loop, but some may consider your original more readable in this respect. What is worth doing is making sure all your variable names are meaningful.

int sumOfEvenFibonaccis(int limit, int* steps)
{
    int prior = 1; 
    int even_fibbonaci = 2; 
    int sum = 0;//sum of even up to 2nd term
    int steps_taken = 0;
    do{
        sum += even_fibbonaci;
        prior += 2 * even_fibbonaci;
        even_fibbonaci = 2 * prior - even_fibbonaci;         
        steps_taken++;
    } while (even_fibbonaci<limit);
    if (steps != NULL)
        *steps = steps_taken;
    return sum;
}

struct TestCase
{
    int limit;
    int result;
}; 

struct TestCase testCases[] = 
{
    { 89, 2 + 8 + 34 }
};

int numTestCases = sizeof(testCases) / sizeof(testCases[0]);

void runTests()
{
    for (unsigned i = 0; i != numTestCases; ++i)
    {
        int testResult = sumOfEvenFibonaccis(testCases[i].limit, 0);
        int expectedResult = testCases[i].result;
        assert(testResult == expectedResult);
    }
}

int main(int argc, char ** argv)
{

    runTests();

    int steps = 0;
    int result = sumOfEvenFibonaccis(4000000, &steps);
    printf("Result: %d using %d steps", result, steps);

    return 0;
}

Answer 2

Some algorithm comments. Your Fibonacci table is incorrect. See wikipedia. \$F_0 = 0\$. While it actually doesn't affect the solution, it is just a minor detail that should be corrected.

Even Fibonacci numbers have their own recurrence relation if you only care about the even values. From the definition of the Fibonacci sequence, we know

1. \$F_0 = 0\$,
2. \$F_1 = 1\$,
3. \$F_{n+1} = F_n + F_{n-1}\$.

Looking over the Fibonacci sequence, we see that our Even Fibonacci Numbers appear every 3rd element. We can define

1. \$G_n = F_{3n}\$,
2. \$G_0 = F_{0} = 0\$,
3. \$G_1 = F_{3} = 2\$.

From here, we can use our definitions to find \$G_{n+1}\$ in terms of \$G_{n}\$ and \$G_{n-1}\$.

$$ $$\begin{align*} G_{n}&= F_{3n}\\ G_{n+1}&= F_{3n+3}\\ &= F_{3n+1} + F_{3n+2}\\ &= F_{3n-1} + F_{3n} + F_{3n} + F_{3n+1}\\ &= F_{3n-3} + F_{3n-2} + F_{3n} + F_{3n} + F_{3n-1} + F_{3n}\\ &= G_{n-1} + F_{3n-2} + F_{3n-1} + 3 G_{n}\\ &= G_{n-1} + 4 G_{n} \end{align*}$$ $$

Now that we know \$G\$ is a recurrence relation, we can define the sequence \$G_n\$ of Even Fibonacci numbers as the recurrence relation \$G_{n} = G_{n-2} + 4G_{n-1}\$, with seed values \$G_0 = 0, G_1 = 2\$. This allows you to remove the calculation in your program of \$F_{3n+2}\$, the odd fibonacci value before an even fibonacci. Now we can calculate all of the Even Fibonacci numbers dependent only on the previous Even Fibonacci numbers.