Another even Fibonacci numbers implementation

Question

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:

1. Do iterators and algorithms produce a net loss or gain for this particular code?
2. Is it problematic that the iterator's operator != actually does a < comparison internally, on the basis that it's looking for the end of a logical range, but doesn't expect you to necessarily know the exact value of the Fibonacci number at the end of the range you care about?

Version 1:

#include <iostream>
#include <time.h>

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 <iostream>

template <class T=unsigned>
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 temp = first + second; 
        first = second; 
        second = temp; 
        return *this; 
    }
    bool operator!=(fib_iterator const &r) { return first < r.first; }
};

template <class InIt, class F, class T>
T accumulate_if(InIt b, InIt e, T accum, F f) {
    while (b != e) {
        if (f(*b))
            accum += *b;
        ++b;
    }
    return accum;
}

int main() {
    std::cout << accumulate_if(fib_iterator<>(), fib_iterator<>(4000000),
        0U, [](unsigned v) { return v % 2 == 0; });
}

Of course, the questions I've asked above are not intended to limit the scope of reviews--only to add to the normal review I'd hope for when posting any code here.

Answer 1

I only have a few remarks concerning the second version:

• Why does fid_iterator::operator* return an int? Shouldn't it return a T instead since the class is templated? You also declared temp as int. Since you are only adding numbers, you don't need it to be signed, so I don't understand why it is not T.
• You should add the public types value_type, reference, etc... to fib_iterator so that it is compatible with std::iterator_traits and generic algorithms using it. I believe that iterator_category would be std::forward_iterator_tag.
• To fully satisfy the ForwardIterator concept, fib_iterator needs to implement operator++(int).
• You should rename F to Predicate to clarify the intent of the function passed to accumulate_if.

At first, computing mathematical formula thanks to iterators did not seem intuitive (to me). However, I totally do understand why you chose iterators instead of returning a collection; it's probably much more memory efficient and it is easy to create a wrapper function to return a container if one really wants to.

I generally prefere code that looks like math formula when I have to write math-related code, but in this particular case, I find that the iterators and the modern C++ feel are rather suited :)

Answer 2

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.

Answer 3

That's not a fair comparison of programming styles, as you haven't attempted to make everything else equal. If I were to translate Version 2 into a C-style loop, I would write:

#include <iostream>

int main() {
    unsigned sum = 0;
    for ( unsigned first = 1, second = 1, temp;
          first < 4000000;
          temp = first + second, first = second, second = temp ) {
        if ((first + second) % 2 == 0) sum += (first + second);
    }
    std::cout << sum << std::endl;
}

That's the entire program. The readability is so-so, but the conciseness could be considered a virtue.

My translation makes it clear that the termination condition of your Version 2 is probably not what you intended. The last number you add could very well be over 4 million. You're lucky that 5702887 and 9227465 are both odd.

---

In my opinion, the middle ground would be optimal.

The Fibonacci sequence is an infinite stream of numbers. Expressing it as an iterator would be the most natural way to model the problem. The iterator class adds verbosity to the code, but I can see benefits.

However, I'm not a fan of accumulate_if(). A conventional for-loop uses no advanced language features such as lambda. It doesn't even require fib_iterator<T>::operator!=(…), which, as you pointed out, is misleading,¹ and as I pointed out, is buggy. Furthermore, to specify the condition to terminate iteration, you have to construct a fib_iterator<>(4000000, 1). Even though the 1 is implicit rather than explicit, I still find it icky.

A for-loop accomplishes the task with less code. Most importantly, the code is laid out in the most easily recognizable format possible to any C/C++ programmer: as a loop rather than a long line of parameters to some function I'm not familiar with. Since loop condition tests *it, the same number that we add to the sum, it's foolproof.

int main() {
    unsigned sum = 0;
    for (auto it = fib_iterator<>(); *it < 4000000; ++it) {
        if (*it % 2 == 0) sum += *it;
    }
    std::cout << sum << std::endl;
}

I wouldn't say that the accumulate_if() concept has no merit, but I don't think that it is justified for this simple problem.

---

¹ By the way, why did you choose to implement and use fib_iterator<T>::operator!=(…) rather than fib_iterator<T>::operator<(…)? The latter doesn't require you to lie.

Answer 4

I think that the first version is somewhat more straightforward and would be understandable by those not familiar with the latest C++ constructs.

However, I do rather like the idea of implementing the Fibonacci sequence as an iterator. It makes some sense, although I have some quibbles with how it's implemented:

1. Every instance of int in the iterator should probably be T
2. I'd have avoided the use of temp in operator++
3. operator* and operator!= should be declared const
4. using < in definition of != isn't necessarily bad, but odd

I'd also eliminate accumulate_if entirely and use std::accumulate instead:

std::accumulate(fib_iterator<>(), fib_iterator<>(4000000U), 0U, 
    [](unsigned accum, unsigned v) { return accum + (v & 1 ? 0 : v); })

To my eye, it's a little easier to understand, since you're using a lambda anyway.

Also, I'd be at least slightly concerned about numerical overflow for both versions. Seems like it might be worth throwing an exception rather than silently returning bad answers.