HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppMinor

Another even Fibonacci numbers implementation

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
implementationfibonaccinumbersanothereven

Problem

This is intended as something of a comparative study. I'm including not just one, but two separate implementations of code to implement the Project Euler problem to sum the even Fibonacci numbers up to 4,000,000. The first is a very C-like implementation. The second attempts to make much more use of modern C++. To do so, it includes a specialized iterator to generate Fibonacci numbers, and a generic algorithm for summing items from a range conditionally (and uses a lambda expression to specify the condition).

If we include that generic algorithm, the latter is (marginally) longer than the former (though I've also included some timing code in the former that's currently absent in the latter). I'm curious to know what people think of them--whether the latter is really an improvement, which style you'd prefer to see in your code base, and so on.

More specific questions:

  • Do iterators and algorithms produce a net loss or gain for this particular code?



  • Is it problematic that the iterator's operator != actually does a



Version 1:

#include 
#include 

int main() {
    clock_t start = clock();
    unsigned long long total;
    int max_reps = 10000;

    for (int reps = 0; reps < max_reps; reps++) {
        total = 0;
        unsigned long long first = 1;
        unsigned long long second = 1;
        unsigned long long fib = first + second;

        while (fib < 4000000) {
            if ((fib % 2) == 0)
                total += fib;
            first = second;
            second = fib;
            fib = first + second;
        }
    }
    clock_t stop = clock();

    std::cout << total 
              << "\ntime: " 
              << (1000.0 * (stop - start)) / double(CLOCKS_PER_SEC * max_reps) << "ms\n";
}


...and version 2:

``
#include

template
class fib_iterator {
T first, second;
public:
fib_iterator(T v1=1, T v2 = 1) : first(v1), second(v2) {}
int operator *() { return first + second; }
fib_iterator &operator++() {
int

Solution

Sorry if I sound Fortranish. Project Euler is about math, not programming.

A Fibonacci number is even if its index is \$3n+2\$. A Binet's formula reduces their sum to the sum of 2 geometric progressions. That, and some error estimation, is pretty much it.

Context

StackExchange Code Review Q#48023, answer score: 8

Revisions (0)

No revisions yet.