(infinite) sequences using recurrence relations

From: Eric Ford (eford_at_[hidden])
Date: 2001-08-04 06:49:00

I created a directory "recurrence relation iterator" which has my
first crack at pseudo iterator and container classes for
(mathematical, not stl) sequences generated on the fly using a
recurrence relation (e.g. infinite sequences).  If people are still
interested, I'd be interested in getting comments.

Here's the README...

Earlier there was some discussion of sequences that are not
necessarily stored in a real stl container, but rather generated on
the fly.  However, I didn't notice much code coming out of this.
Here's my first crack...

Simply using a std::list or std::vector of numbers is one obvious way
to store the elements of a sequence.  Infinite sequences can not fit
into memory all at once.  Further, infinite sequences are quite common
in mathematics when a recurrence relation allows one element to be
quickly calculated based on some other elements using some type of
recurrence relation.  It would be nice if there were some type of
pseudo-iterator and pseudo-container that could accomodate such
sequences.  I say pseudo, because I don't think all of the STL
specifications for a sequence really make senes for what
mathematicians call a sequence.  Similarly, an STL container doesn't
really make sense for an infinite sequence.  So there will probably be
some nomenclature and design decisions to be made.  Personally, I'm
much more interested in design decissions than nomenclature arguments.

Example 1: For the infinite sequences 1, x, x^2, x^3, x^4, ..., x^n,
you can calculate each term by multiplying the last term by x.
Obviously, this is much faster than doing all the multiplications for
each term or calling std::pow repeatedly.  Additionally, there's no
need to store lots of these in memory.  In this case, x needs to be
avaliable whenever a new term is computed.  BTW- In this case, the
iterator could probably be nearly bidirectional.  Since a*x/x isn't
guarenteed to equal a for float-like types, there may need to be some
discussion about this.

Example 2: The Fibbonaci sequence 1, 1, 2, 3, 5, 8, 13, 21, 34,
... can be quickly computed using the recurrence relation a_{n+1} =
a_n + a_{n-1}.  In this case, the current state depends on both the
previous term and the "previous previous" term, so the state is a
little more complicated.  Since there are no parameters, it's
necessary to specialize for a parameter type of void.

Adding a new sequence.  To add a new infinte sequence requires at
least ttwo classes: a state class and a recurrence relation class.  I
normally find it convient to make a third class for the sequence.  The
state class stores all the information that is necessary to calculate
another term in the sequence.  It needs to have a constructor with no
required arguments, but may have optional arguments.  The default
arguments are presently used to specify the "beginning" of the
sequence, but this may change as it doesn't always make sense.  The
state class also needs to define operator()() which returns the
current element of the sequence.  Additional member functions may be
desirable for more complicated recursion relations.  The recurrence
relation class must implement a function next (and optionally prev)
which tates the current state (in the form of the previously mentioned
state class) and returns the state for the next (previous) term in the
sequence.

If that didn't make sense, just look at the exmaples, and that should
make it more clear.  Sorry, but documentation isn't my strong point.