patterncppMinor
Another even Fibonacci numbers implementation
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:
Version 1:
...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
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.
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.