Fibonacci and Lucas sequence generator using Boost and GMP

Question

I implemented this console application that generates Fibonacci and Lucas sequence numbers using boost and GMP for multiprecision.

There is an iterator-like class which can do any sequence based on the recursive rule F(n) = F(n-1) + F(n-2).

Then there are two functions which can compute Fibonacci and Lucas numbers given their position as for random access of the sequences.

I am using operator<< to feed the iterator with one of these functions so it can align itself with given start position in the given sequence.

The iterator can actually iterate backwards, because there is nothing that prevents it. You can invoke the behaviour by passing negative limit to the console app. This actually allows to go below zeroth element of the sequences.

I welcome any constructive criticism on my code and also suggestions how to make it more general in terms providing potentialy more sequences, using different number representations and having the iterator actualy do the random access (+=,-=,...) using those functions without loosing the ability to act on them and not knowing which function is used for the random access... And of course whatever other improvement comes to your mind :)

I am not sure whether I am using anything C++17 specific, but that is as high as I can go.

#include <iostream> #include <algorithm> #include <boost/multiprecision/gmp.hpp> /** * Provides iterator over fibonacci family sequences. * That is those sequences generated by recursive formula: * F(n) = F(n-1) + F(n-2) */ template <class T = long, class TIndex = T> struct pair_sum_iterator { public: typedef std::bidirectional_iterator_tag iterator_category; typedef T value_type; typedef TIndex difference_type; typedef T* pointer; typedef T& reference; T current, next; TIndex index; pair_sum_iterator() : current(0), next(0), index(0) {} pair_sum_iterator(const TIndex& index) : current(0), next(0), index(index) {} pair_sum_iterator(const T& first, const T& second) : current(first), next(second), index(0) {} pair_sum_iterator(const T& first, const T& second, const TIndex& index) : current(first), next(second), index(index) {} const T& operator*() const { return current; } pair_sum_iterator & operator++() { ++index; T tmp = current; current = next; next += tmp;; return *this; } pair_sum_iterator operator++(int) { pair_sum_iterator old(*this); ++(*this); return old; } pair_sum_iterator & operator--() { --index; T tmp = current; current = next - current; next = tmp; return *this; }; pair_sum_iterator operator--(int) { pair_sum_iterator old(*this); --(*this); return old; } pair_sum_iterator & operator+=(const TIndex& diff) { TIndex d(diff); while (d > 0) { ++(*this); --d; } while (d < 0) { --(*this); d += 1; //bug in boost - cannot use ++d } return *this; } pair_sum_iterator & operator-=(const TIndex& diff) { return *this += -diff; } pair_sum_iterator operator+(const TIndex& diff) const { pair_sum_iterator result(*this); return result += diff; } pair_sum_iterator operator-(const TIndex& diff) const { pair_sum_iterator result(*this); return result -= diff; } pair_sum_iterator& operator<<(T (*f)(const TIndex&)) { current = f(index); next = f(index + 1); return *this; } }; template <class T, class TIndex> bool operator==(const pair_sum_iterator<T, TIndex> & a, const pair_sum_iterator<T, TIndex> & b) { return a.index == b.index; } template <class T, class TIndex> bool operator!=(const pair_sum_iterator<T, TIndex> & a, const pair_sum_iterator<T, TIndex> & b) { return a.index != b.index; } template <class T, class TIndex> bool operator<(const pair_sum_iterator<T, TIndex> & a, const pair_sum_iterator<T, TIndex> & b) { return a.index < b.index; } template <class T, class TIndex> bool operator<=(const pair_sum_iterator<T, TIndex> & a, const pair_sum_iterator<T, TIndex> & b) { return a.index <= b.index; } template <class T, class TIndex> bool operator>(const pair_sum_iterator<T, TIndex> & a, const pair_sum_iterator<T, TIndex> & b) { return a.index > b.index; } template <class T, class TIndex> bool operator>=(const pair_sum_iterator<T, TIndex> & a, const pair_sum_iterator<T, TIndex> & b) { return a.index >= b.index; } template <class T, class TIndex> TIndex operator-(const pair_sum_iterator<T, TIndex> & a, const pair_sum_iterator<T, TIndex> & b) { return a.index - b.index; } /** * Fibonacci and lucas sequence random accessors and related stuff */ typedef boost::multiprecision::mpz_int app_int; typedef boost::multiprecision::mpf_float_500 app_float; const app_float sqrt5 = boost::multiprecision::sqrt(app_float(5)); const app_float phi = (app_float(1) + sqrt5) / app_float(2); const app_float nphi = app_float(1) - phi; app_int fibonacci(const app_int & n) { app_float n_f(n); return boost::multiprecision::round(((boost::multiprecision::pow(phi,n_f) - boost::multiprecision::pow(nphi, n_f)) / sqrt5)).convert_to<app_int>(); } app_int lucas(const app_int & n) { app_float n_f(n); return boost::multiprecision::round(boost::multiprecision::pow(nphi, n_f) + boost::multiprecision::pow(phi, n_f)).convert_to<app_int>(); } /** * Console application parameters */ struct app_params { public: app_int start; app_int limit; app_int (*sequence)(const app_int &); bool show_usage; bool success; app_params() : start(0), limit(10), sequence(fibonacci), show_usage(false), success(true) {} void usage(bool success) { show_usage = true; this->success = success; } static app_params parse(int argc, char* argv[]) { unsigned int arg_offset = 1; app_params params; try { if (argc > 1) { std::string arg1(argv[1]); if (arg1 == "-h" || arg1 == "--help") { params.usage(argc == 2); } else { if (arg1 == "lucas") { ++arg_offset; params.sequence = lucas; } if (argc == 1 + arg_offset) { // custom limit params.limit = app_int(argv[arg_offset]); } else if (argc == 2 + arg_offset) { // custom limit and offset params.start = app_int(argv[arg_offset]); params.limit = app_int(argv[arg_offset + 1]); } else if (argc > arg_offset) { //argc==arg_offset -> default limit and offest for lucas, otherwise invalid params params.usage(false); } } } } catch (std::runtime_error error) { params.usage(false); } return params; } }; /** * Displays application usage information */ void print_usage(std::ostream & stream) { stream << "Usage:\n"; stream << "\tfibonacci [lucas] [[<start=0>] <limit=10>]\n"; } /** * Application entry point */ int main(int argc, char* argv[]) { auto params = app_params::parse(argc, argv); if (params.show_usage) { print_usage(params.success ? std::cout : std::cerr); return params.success ? EXIT_SUCCESS : EXIT_FAILURE; } pair_sum_iterator<app_int> f(params.start); pair_sum_iterator<app_int> end(params.start + params.limit); f << params.sequence; std::ostream_iterator<app_int> out(std::cout, "\n"); if (params.limit.sign() < 0) { std::reverse_copy(end, f, out); } else { std::copy(f, end, out); } return EXIT_SUCCESS; } 

To Compile:

g++ -std=c++17 -g main.cc -lboost_math_c99 -lgmp -o fibonacci 

$g++ --version g++ (Ubuntu 7.4.0-1ubuntu1~18.04.1) 7.4.0 

To Run:

fibonacci [lucas] [[<start=0>] <limit=10>] 

Answer 1

I recommend using more compiler warnings - they can highlight issues such as

232757.cpp: In static member function ‘static app_params app_params::parse(int, char**)’: 232757.cpp:221:30: warning: comparison of integer expressions of different signedness: ‘int’ and ‘unsigned int’ [-Wsign-compare] 221 | if (argc == 1 + arg_offset) { // custom limit | ~~~~~^~~~~~~~~~~~~~~~~ 232757.cpp:223:37: warning: comparison of integer expressions of different signedness: ‘int’ and ‘unsigned int’ [-Wsign-compare] 223 | } else if (argc == 2 + arg_offset) { // custom limit and offset | ~~~~~^~~~~~~~~~~~~~~~~ 232757.cpp:226:37: warning: comparison of integer expressions of different signedness: ‘int’ and ‘unsigned int’ [-Wsign-compare] 226 | } else if (argc > arg_offset) { //argc==arg_offset -> default limit and offest for lucas, otherwise invalid params | ~~~~~^~~~~~~~~~~~ 232757.cpp:232:37: warning: catching polymorphic type ‘class std::runtime_error’ by value [-Wcatch-value=] 232 | } catch (std::runtime_error error) { | ^~~~~ 

These particular ones are easy to address, and doing so improves the code, so no reason not to.

---

It seems strange that the template argument TIndex defaults to T. I think it's quite reasonable to use a floating-point and/or complex number for T, but TIndex really ought to be an integer type.

In newer C++, I would use Concepts to constrain the types accepted. It's possible to do the same using std::enable_if<> in C++17, but it's a lot less readable.

---

I don't think we should be exposing the data members publicly - although random modification from outside won't break our invariants (we don't have any), they would violate the promise we made as a bidirectional iterator (after modification, we iterate over a different set of values).

Make them private, and simplify the constructors by default-initialising them (which is probably better than assuming they can be constructed from 0 literal). Also, we can pass by value, which can eliminate an unnecessary copy. And we should use explicit to avoid this class becoming an implicit conversion target for just about everything.

struct pair_sum_iterator { T current = {}; T next = {}; TIndex index = {}; public: explicit pair_sum_iterator(TIndex index = {}) : index{std::move(index)} {} pair_sum_iterator(T first, T second, TIndex index = {}) : current{std::move(first)}, next{std::move(second)}, index{std::move(index)} {} 

---

Most C++ programmers would prefer using to the typedefs here. It's much easier to find where types are defined with using, in my opinion, since the thing being defined is toward the left, as with other declarations.

---

If T is expensive to copy, we can improve the increment operator by move-constructing the temporary:

 ++index; T tmp{std::move(current)}; current = next; next += tmp; return *this; 

Or we could re-use the values in-place, though making it a little harder to reason about:

 ++index; std::swap(current, next); next += current; return *this; 

---

The use of operator<< to initialise from a function is surprising and unintuitive. Consider making this another (explicit) constructor.

---

Consider whether we really need the full set of relational operators - standard algorithms use only <.

Newer C++ standards allow the compiler to synthesize these from a single <=> and a ==. I find them more readable as member functions (there should be no conversions of first argument, so no compelling case for non-member):

 bool operator<=>(const pair_sum_iterator& other) const { return index <=> other.index; } bool operator==(const pair_sum_iterator& other) const { return index == other.index; } 

---

TIndex might not be a good choice of return type from - operator, as it's quite likely to be an unsigned type. I'm not sure what to recommend instead, though. Perhaps std::make_signed_t<TIndex>?

---

Minor things

Because Fibonacci is a proper name, it should always be spelt with capital F in prose:

/** * Provides iterator over fibonacci family sequences. 

The same is true of Lucas:

/** * Fibonacci and lucas sequence random accessors and related stuff */ 

Reference types are written inconsistently, as pair_sum_iterator& and as pair_sum_iterator &. I find the former easier to read.

No good reason for empty statement here:

 next += tmp;; 

Typo in this comment:

 //argc==arg_offset -> default limit and offest for lucas