Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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.

share|improve this question
add comment

4 Answers 4

up vote 5 down vote accepted

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 :)

share|improve this answer
add comment

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.

share|improve this answer
3  
Binet's formula is painful to use for anything other than the first few fibonnaci numbers, due to floating-point inaccuracy and, well, floating-point. It's possible to compute them efficiently while staying in the integers, e.g. via reduced matrix form (using the matrix formula but cutting out some redundant work, and using square-and-multiply), though if you just need to generate all of them in sequence then nothing beats just doing it the naive way, obviously. –  Thomas Apr 24 at 13:09
    
@Thomas, you've missed the point. There's no need to compute any Fibonacci numbers. user58697 is proposing replacing the entire loop with a couple of calls to pow. –  Peter Taylor Apr 24 at 13:24
3  
@PeterTaylor And that's exactly it. pow is not ideal as it requires moving to floating-point, staying in integers gets rid of plenty of problems you will encounter (and is pretty much as efficient as pow if you do it right, if not more). Project Euler is also about writing elegant code that scales - as is this Q/A site, I think - even though most of the simpler problems can be brute-forced :) –  Thomas Apr 24 at 13:42
    
Sorry I was unclear. There is no need to calculate the result using Binet's. With Binet it is easy to see what the result is :it is a certain combination of a few (pretty large) Fibonacci numbers (is there LaTeX here?), which again can be calculated precisely and very fast. –  vnp Apr 24 at 18:33
add comment

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,1 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.


1 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.

share|improve this answer
    
Probably the habit of implementing operator!= in iterators. That's one of the functions I would always expect to exist for a given iterator. –  Morwenn Apr 24 at 12:36
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.