Addition of Even Fibonacci Numbers

Question

I'm trying to solve the 2nd problem on Project Euler where I have to print the sum of all even Fibonacci numbers under 4 million. I'm using the following code but the program is not returning any value. When I replace 4000000 by something small like 10, I get the sum. Does that mean my program is taking too long? What am I doing wrong?

#include <iostream>
using namespace std;

int fibonacci(int i) {
    if (i == 2)
        return 2;
    else if (i == 1)
        return 1;
    else return fibonacci(i - 1) + fibonacci(i - 2);
}

int main() {

    int currentTerm, sum = 0;
    for (int i = 1; i <= 10; i++) {

        currentTerm = fibonacci(i);
        if (currentTerm % 2 == 0)
            sum += currentTerm;
    }
    cout << sum;
    return 0;
}

Answer 1

Problem 2 of project Euler asks (emphasis mine)

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Doing

for (int i = 1; i <= 4000000; i++)
{
     currentTerm = fibonacci(i);
     // ...
}

You are trying to calculate up to the 4,000,000^th Fibonacci number, which is a very big beast, while you should stop around the 33^th instead.

The other answers already pointed out the inefficiency of the recursive approach, but let me add some numbers to the discussion, using this slightly modified version of your program

#include <iostream>
#include <iomanip>

int k = 0;

// From https://oeis.org/A000045 The fibonacci numbers are defined by the
// recurrence relation F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1.
// In the project Euler question the sequence starts with 1, 2, 3, 5, ...
// So in the following I'll consider F(1) = 1 and F(2) = 2 as The OP does.
long long fibonacci(long long i)
{
    ++k;
    if (i > 2)
        return fibonacci(i - 1) + fibonacci(i - 2);
    else
        return i;
}

int main()
{
    using std::cout;
    using std::setw;
    const long limit = 4'000'000;
    long sum = 0;

    cout << "  i      F(i)       sum      calls\n"
            "-----------------------------------\n";
    for (int i = 1; ; ++i)
    {
        long long F_i = fibonacci(i);

        if ( F_i > limit )             // <-- corrected end condition
            break;

        if (F_i % 2 == 0)
        {
            sum += F_i;

            cout << setw(3) << i << setw(10) << F_i
                 << setw(10) << sum << setw(11) << k << '\n';
        }
    }

    cout << "\nThe sum of all even Fibonacci numbers less then "
         << limit << " is " << sum << '\n';
    return 0;
}

Once executed (live here), you can notice that the recursive function has been called more than 10,000,000 times, to calculate up to the 33^th Fibonacci number.

That's simply not the right way. Memoization could help, here there's a quick benchmark comparing the recursive functions with a toy implementation of the memoization technique, which is represented by the histogram that you can't see. Because it's 300,000 times shorter than the others.

Still, that's not the "correct" or "natural" way to deal with this problem. As noted in the other answers you could simply calculate each number in sequence, given the previous ones. Enthus3d also noted the pattern in the sequence: odd, odd, even,   odd, odd, even, ...

We can go even further and directly calculate only the even terms:

#include <iostream>

int main()
{
    const long limit = 4'000'000;

    // In the linked question the sequence starts as 1, 2, 3, 5, 8, ... 
    long long F_0 = 2, F_3 = 8, sum = F_0 + F_3;

    for (;;)
    {
        // F(n+2) = F(n+1) + F(n)
        // F(n+3) = F(n+2) + F(n+1) = F(n+1) + F(n) + F(n+1) = 2F(n+1) + F(n)
        // F(n+6) = F(n+5) + F(n+4) = F(n+4) + F(n+3) + F(n+3) + F(n+2)
        //        = 2F(n+3) + F(n+4) + F(n+2) = 3F(n+3) + 2F(n+2)
        //        = 3F(n+3) + 2F(n+1) + 2F(n) = 3F(n+3) + F(n+3) - F(n) + 2F(n)
        long long F_6 = 4 * F_3 + F_0;

        if ( F_6 > limit )
            break;

        sum += F_6;
        F_0 = F_3;
        F_3 = F_6;
    }

    std::cout << sum << '\n';    // --> 4613732
    return 0;
}

Live here.

Answer 2

You can use the Binet formula in your calculations - this will allow you to abandon the slow recursive algorithm, another option may be a non-recursive algorithm for calculating fibonacci numbers. https://en.wikipedia.org/wiki/Jacques_Philippe_Marie_Binet. Here is an example of using the Binet formula, it will be much faster than the recursive algorithm, since it does not recalculate all previous numbers.

#include <iostream>
#include <math.h>
using namespace std;
int main(){
    double num{},a{(1+sqrt(5))/2},b{(1-sqrt(5))/2},c{sqrt(5)};
    int sum{};
    for (auto i=1;i<30;++i){
        num=(pow(a,i)-pow(b,i))/c;
        if (static_cast<int>(num)%2==0)
            sum+=static_cast<int>(num);
    }
    cout<<sum;
return 0;
}

variant 2

int fib_sum(int n)
{
    int sum{};
    if (n <= 2) return 0;
    std::vector<int> dp(n + 1);
    dp[1] = 1; dp[2] = 1;
    for (int i = 3; i <= n; i++)
    {
       dp[i] = dp[i - 1] + dp[i - 2];
       if(dp[i]%2==0) 
         sum+=dp[i];
    }
    return sum;
}

Answer 3

If you need multiple Fibonacci numbers, and especially if you need all of them, do not use the recursive approach, use iteration instead:

var prev=0;
var curr=1;
var sum=0;
while(curr<4000000){
  if(curr%2==0)
    sum+=curr;
  var temp=prev;
  prev=curr;
  curr+=temp;
}
console.log(sum);

The snippet is JavaScript (so it can run here), but if you make var-s to int-s, it will be C-ish enough.

But the actual problem was the loop: you do not need to calculate the first n (4000000) Fibonacci numbers (which would lead to various overflows), but the Fibonacci numbers which are smaller than 4000000.

Answer 4

If you want a bit of magic, you can also build on the fact that every 3rd Fibonacci number is even, on the basis of "even+odd=>odd", "odd+even=>odd", and only "odd+odd=>even":

0 1 1 2 3 5 8...
E O O E O O E
            ^ O+O
          ^ E+O
        ^ O+E
      ^ O+O

var prev=1;
var curr=2;
var sum=0;
while(curr<4000000){
  sum+=curr;
  console.log("elem: "+curr,"sum: "+sum);
  for(var i=0;i<3;i++){
    var temp=prev;
    prev=curr;
    curr+=temp;
  }
}

---

And if the question would be only the title, Addition of even fibonacci numbers (let's say, n of them), pure mathematics could do the job, using Binet's formula (described in @Silerus' answer) and the fact that it is an (a^n-b^n)/c thing, where a^n and b^n are geometric sequences, every 3rd of them also being a geometric sequence, (a^3)^n, and the sum of geometric sequences has a simple, closed form (if the series is a*r^n, the sum is a*(1-r^n)/(1-r)).

Putting everything together:

// convenience for JS->C
var pow=Math.pow;
var sqrt=Math.sqrt;
var round=Math.round;

var s5=sqrt(5);
var a=(1+s5)/2;
var a3=pow(a,3);
var b=(1-s5)/2;
var b3=pow(b,3);
for(var i=0;i<12;i++){
  var nthEvenFib=round((pow(a3,i)-pow(b3,i))/s5);
  var sumEvenFibs=round(((1-pow(a3,i+1))/(1-a3)-(1-pow(b3,i+1))/(1-b3))/s5);
  console.log("elem: "+nthEvenFib,"sum: "+sumEvenFibs);
}

Again, both snippets become rather C-ish if var-s are replaced with some C-type, int-s in the first snippet, and mostly double-s in this latter one (the loop variable i can be a simple int of course).

Answer 5

You can speed up brutally by using compile time precalculations for all even Fibonacci numbers and sums using constexpre functions.

A short check with Binets formula shows, that roundabout 30 even Fibonacci numbers will fit into a 64bit unsigned value.

30 numbers can really easily been procealculated without any effort for the compiler. So, we can create a compile time constexpr std::array with all needed values.

So, you will have zero runtime overhead, making you program extremely fast. I am not sure, if there can be a faster solution. Please see:

#include <iostream>
#include <array>
#include <algorithm>
#include <iterator>


// ----------------------------------------------------------------------
// All the following wioll be done during compile time
// Constexpr function to calculate the nth even Fibonacci number
constexpr unsigned long long getEvenFibonacciNumber(size_t index) {
    // Initialize first two even numbers 
    unsigned long long f1{ 0 }, f2{ 2 };

    // calculating Fibonacci value 
    while (--index) {
        // get next even value of Fibonacci sequence 
        unsigned long long f3 = 4 * f2 + f1;

        // Move to next even number
        f1 = f2;
        f2 = f3;
    }
    return f2;
}

// Get nth even sum of Fibonacci numbers
constexpr unsigned long long getSumForEvenFibonacci(size_t index) {
    // Initialize first two even prime numbers 
    // and their sum 
    unsigned long long f1{ 0 }, f2{ 2 }, sum{ 2 };

    // calculating sum of even Fibonacci value 
    while (--index) {
        // get next even value of Fibonacci sequence 
        unsigned long long f3 = 4 * f2 + f1;

        // Move to next even number and update sum 
        f1 = f2;
        f2 = f3;
        sum += f2;
    }
    return sum;
}

// Here we will store ven Fibonacci numbers and their respective sums
struct SumOfEvenFib {
    unsigned long long fibNum;
    unsigned long long sum;
    friend bool operator < (const unsigned long long& v, const SumOfEvenFib& f) { return v < f.fibNum; }
};

// We will automatically build an array of even numbers and sums during compile time
// Generate a std::array with n elements taht consist of const char *, pointing to Textx...Texty
template <size_t... ManyIndices>
constexpr auto generateArrayHelper(std::integer_sequence<size_t, ManyIndices...>) noexcept {
    return std::array<SumOfEvenFib, sizeof...(ManyIndices)>{ { {getEvenFibonacciNumber(ManyIndices + 1), getSumForEvenFibonacci(ManyIndices + 1)}...}};
};

// You may check with Ninets formula
constexpr size_t MaxIndexFor64BitValue = 30;

// Generate the reuired number of texts
constexpr auto generateArray()noexcept {
    return generateArrayHelper(std::make_integer_sequence<size_t, MaxIndexFor64BitValue>());
}

// This is an constexpr array of even Fibonacci numbers and its sums
constexpr auto SOEF = generateArray();
// ----------------------------------------------------------------------


int main() {


    // Show sum for 4000000
    std::cout << std::prev(std::upper_bound(SOEF.begin(), SOEF.end(), 4000000))->sum << '\n';

    // Show all even numbers and their corresponding sums
    for (const auto& [even, sum] : SOEF) std::cout << even << " --> " << sum << '\n';
    
    return 0;
}

Tested with MSVC 19, clang 11 and gcc10

Compiled with C++17

Answer 6

Welcome to Stack Overflow :)

I have only modified your code on the loop, and kept your Fibonacci implementation the same. I've verified the code's answer on Project Euler. The code can be found below, and I hope my comments help you understand it better.

The three things I've changed are:

1) You tried to look for a number all the way until the 4,000,000 iteration rather than for the number that is less than 4,000,000. That means your program probably went crazy trying to add a number that's insanely large (which we don't need) <- this is probably why your program threw in the towel

2) I improved the check for even numbers; we know that fibonacci sequences go odd odd even, odd odd even, so we only really need to add every third number to our sum instead of checking if the number itself is even <- modulus operations are very expensive on large numbers

3) I added two lines that are commented out with couts, they can help you debug and troubleshoot your output

There's also a link here about using Dynamic Programming to solve the question more efficiently, should anyone need it.

Good luck!

#include <iostream>
using namespace std;

int fibonacci(int i) {
    if (i == 2)
        return 2;
    else if (i == 1)
        return 1;
    else return fibonacci(i - 1) + fibonacci(i - 2);
}

int main() {
    // need to add the sum of all even fib numbers under a particular sum
    int max_fib_number = 4000000;
    int currentTerm, sum = 0;
    currentTerm = 1;
    int i = 1;

    // we do not need a for loop, we need a while loop
    // this is so we can detect when our current number exceeds fib
    while(currentTerm < max_fib_number) {
        currentTerm = fibonacci(i);
        //cout << currentTerm <<"\n";

        // notice we check here if currentTerm is a valid number to add
        if (currentTerm < max_fib_number) {
            //cout << "i:" << i<< "\n";

            // we only want every third term
            // this is because 1 1 2, 3 5 8, 13 21 34,
            // pattern caused by (odd+odd=even, odd+even=odd)
            // we also add 1 because we start with the 0th term
            if ((i+1) % 3 == 0)
                sum += currentTerm;
        }
        i++;        
    } 
    cout << sum;
    return 0;
}

Answer 7

Here's Your modified code which produce correct output to the project euler's problem.

#include <iostream>
using namespace std;

int fibonacci(int i) {
    if (i == 2)
        return 2;
    else if (i == 1)
        return 1;
    else return fibonacci(i - 1) + fibonacci(i - 2);
}

int main() {
    int currentsum, sum = 0;
    for (int i = 1; i <= 100; i++) {
        currentsum = fibonacci(i);
        //here's where you doing wrong 
        if(sum >= 4000000) break; //break when sum reaches 4mil
        if(currentsum %2 == 0) sum+=currentsum;  // add when even-valued occurs in the currentsum
    }

    cout << sum;
    return 0;
}

Output 4613732

Here's my Code which consists of while loop until 4million occurs in the sum with some explanation.

#include <iostream>
using namespace std;

int main()
{
    unsigned long long int a,b,c , totalsum;
    totalsum = 0;
    a = 1; // 1st index digit in fib series(according to question)
    b = 2; // 2nd index digit in fib series(according to question)
    totalsum+=2; // because 2 is an even-valued term in the series 
   while(totalsum < 4000000){ //loop until 4million
        c = a+b; // add previous two nums
        a = b;  
        b = c;  
       if(c&1) continue; // if its odd ignore and if its an even-valued term add to totalsum
       else totalsum+=c; 
    }
    cout << totalsum;
    return 0;
}

for people who downvoted, you can actually say what is wrong in the code instead downvoting the actual answer to the https://projecteuler.net/problem=2 is the output of the above code 4613732 , competitive programming itself is about how fast can you solve problems instead of clean code.