23.3.3 Changing Value Type?

Perhaps a solution lies in using a different value type. Obviously, using uint64_t is only going to be a small bandage over the problem, allowing us to enumerate 93 steps and get to 7,540,113,804,746,346,429. And once we're there, we still precipitate a contract violation, indicating abuse of the sequence.

Maybe floating point is the way to go? (This implementation corresponds to Fibonacci_sequence_3.hpp on the CD.) Alas, no—32-bit float enters INF territory at 187 entries, 64-bit double at 1,478. Furthermore, since the entries in the sequence are not nicely rounded 10N values, rounding errors creep in as soon as the exponent value reaches the extent of the mantissa.

Conceivably, a BigInt type using coded decimal evaluation would be able to go infinite, but it would have correspondingly poor performance. (Readers are invited to submit such a solution. In reward I can promise the unquantifiable fame that will come from having your name on the book's Web site.)

23.3.4 Constraining Type

To avoid floating-point inaccuracies, we would like to constrain the value type to be integral. To avail ourselves of the maximum range of the type and to catch overflow, we would like to constrain the value type to be unsigned. These constraints are achieved by providing a destructor for the sequence for this very purpose, as shown in Listing 23.5.

Listing 23.5 Constraints Enforced in the Destructor

Fibonacci_sequence::~Fibonacci_sequence() throw()
{
  using stlsoft::is_integral_type; // Using using declarations . . .
  using stlsoft::is_signed_type;   // . . . to fit in book. ;-)
  STLSOFT_STATIC_ASSERT(0 != is_integral_type<value_type>::value);
  STLSOFT_STATIC_ASSERT(0 == is_signed_type<value_type>::value);
}

You might think it strange to put in such constraints in a non-template class. The reason is simple: Maintenance programmers (including those who maintain their own code, hint, hint) are wont to change things without putting in all the big-picture research (i.e., reading all documentation). By putting in constraints, you are literally constraining any future changes from violating the design assumptions, or at least from doing so without extra thought.

Tip: Use constraints even in non-template classes to restrict and inform future maintenance activities.

I prefer to place constraints in the destructor of template classes because it's the method we can most rely on being instantiated. In non-template classes, I continue to use it for consistency.

23.3.5 Throw std::overflow_error?

One possible approach is to change the precondition enforcement assertion to be a legitimate runtime condition and to throw an exception. (The implementation shown in Listing 23.6 corresponds to Fibonacci_sequence_4.hpp on the CD.)

Listing 23.6 Version 4: Preincrement Operator

class_type& Fibonacci_sequence::const_iterator::operator ++()
{
  if(m_i1 < m_i0)
  {
    throw std::overflow_error("Exhausted integral type");
  }
  value_type  res   = m_i0 + m_i1;
  . . . // Same as Version 2

Although, in strict terms, this is a legitimate approach, it really doesn't appeal. The so-called exceptional condition is not an unpredictable emergent characteristic of the system at a particular state and time but an entirely predictable and logical consequence of the relationship between the modeled concept and the type used to hold its values. Using an exception in this case just smacks of Java hackery.

I think it's clear at this point that we should either decide to represent the Fibonacci sequence as something that is genuinely infinite, with suitable indicators, or provide a mechanism for providing finite endpoints.

23.4 Discoverability Failure

Although the limit of a Fibonacci sequence for a given unsigned integral type is predictable and constant, requiring users of a type to know this either a priori or a posteriori is a bit rich, to say the least. Quite simply, people would not use such a component.

Our three current candidate implementations present unappealing alternatives.

1. Define the sequence without end(). This precludes any use of (begin(), end()) arguments to algorithms, but it does not preclude two iterators derived from begin() being used with algorithms. Further, there's nothing stopping users from gaily advancing their begin()-derived iterator past the point of overflow, and nothing to guide them in avoiding this.

2. Define the sequence with end() and rely on users' common sense not to use end() for anything at all. If they go into overflow, their program will die in a contract violation.

3. Throw an exception when overflow occurs. Despite this giving a tepid feeling of robustness, it's just as much a discoverability transgression as the other two options, and it also encourages a style of programming that is rightly confined to the world of virtual machines and seven-figure installation and deployment consultancy contracts.

Tip: Avoid using exceptions for failures that are a predictable result of the normal use of a component.

So, either the Fibonacci sequence is not something we should attempt to play with in an STL kind of way, or we need to apply some "finity" to it.

23.5 Defining Finite Bounds

There are two clear and related solutions to this problem.

1. Have end() return an iterator in the range [begin(), ?) whose value does not overflow the value type.

2. Allow the user to specify an upper limit for the effective range provided by the sequence, represented in the value returned by end(). This value would have to be within the valid range.

A good implementation would provide both, where solution 1 is merely the default form of solution 2. We'll examine this by looking at the user-specified limits first.

23.5.1 Iterators Rule After All?

Before we proceed, I must cover an issue that some readers may now be considering. Earlier I ruled out the representation of Fibonacci sequences as independent iterators. The cunning linguists among you may be considering a form that does exactly that, as in:

std::copy(Fibonacci_iterator(), Fibonacci_iterator() + 40
    , std::ostream_iterator<Fibonacci_sequence::value_type>(std::cout
                                                          , " "));

In this case, the putative Fibonacci_iterator would implement the addition operator, such that the expression Fibonacci_iterator() + 40 would evaluate to an instance that would terminate the iteration of a default-constructed iterator on its fortieth increment. At first blush this seems like an adequate solution to the problem.

However, the problem is that use of the addition operator on an iterator indicates that the iterator type is a random access iterator. Further, random access iterators have constant time complexity. To be sure, we're perforce violating pure STL requirements here and there in STL extension. But such violations are never done without due care and particular attention to the effects on discoverability and the Principle of Least Surprise. For example, it's hard to imagine that users of the InetSTL findfile_sequence class (Section 21.1), an STL collection that provides iteration of remote FTP host directory contents, will assume any particular complexity guarantees, given the vagaries of Internet retrieval. However, I suggest that it's far more likely that someone would assume constant time seeing pointer arithmetic syntax on an iterator.

Further, since a user will reasonably expect to be able to type *(Fibonacci_iterator() + 40) if he or she can type Fibonacci_iterator() + 40, we'd have to implement full random access semantics. But, as far as I know, there's no constant-time function integral formula with which you can determine the Nth value of the Fibonacci sequence. (There are a couple of formulas that may be used, but they rely on the square root of five, which would rely on floating-point calculation. One of them is ((1 + sqrt(5)) / 2) - ((1 - sqrt(5)) / 2) ^ n. I'm just enough of a computer numerist to know that I know far too little about floating point to be confident of writing a 100% correct sequence using floating-point calculations.)

Thus we would have to perform a number of forward or backward calculations to arrive at the required value, which is a linear-time operation. This would be a very unobvious violation of a user's expectations and is, in my opinion, unacceptable.

Tip: Beware of changing the complexity of built-in operators, particularly for random access iterators.

(Of course, we could provide amortized constant time by storing the calculated values in an array. We could go further and provide a static member array with precalculated values. We could even use template metaprogramming and effect compile-time calculation. But the purpose of this chapter is pedagogical. Feel free to do any of these, and let me know how it goes. I'll gladly post interesting solutions on the book's Web site.)