Re: [boost] Re: (infinite) sequences using recurrence relations

From: John Max Skaller (skaller_at_[hidden])
Date: 2001-08-10 20:46:12

Eric Ford wrote:
> 
> >       History. Standard Template Library does not mean
> > 'all the templates in the C++ Library', it is a library
> > of _algorithms_ characterized by using iterators as
> > parameters. The containers are irrelevant to this library:
> > the whole point of STL is that it is container independent.
> > The set of algorithms is also much bigger than those actually
> > Standardised (about 2/3 of the algorithms were thrown out
> > to keep C++ small :-)
> 
> Evidently, the SGI STL programmer's guide really confused me onthese
> points.  Can you point me to an online document explaining what the
> STL standard really is?  

        No, and there is no STL Standard, only a C++ Standard.

> Also, an implementation of (and documentation
> for) the rest of the STL that isn't part of the C++ standard library
> avliable somewhere?

        I suppose Alex Stepanov has a copy. STL was originally
developed for Ada, not C++.

> Back to the problem of how to deal with infinite sequences generated
> from recurrsion relations...
> One of my big concerns was that two iterators which are meant to
> represent the same thing (e.g. the coefficient of the nth term in some
> series expansion) could return different values due to floating point
> arithmetic.  Am I correct is understanding your posts to mean, that it
> doesn't matter (at least wrt standards complaince) whether a
> comparison between such iterators returns false or true?

        I think what should happen is that two iterators
representing the n'th term of the same non-cyclic sequence should
compare equal if, and only if, they represent the same term.

        There's no requirement that i == j imply that

        *i == *j

Indeed, equality mightn't even be defined on the value type.
If it is, it could mean anything. Typically, numerical
routines should be based on constructive reals, 
NOT ZF set theoretic reals, and constructive reals do not
admit an equality relation. One then models the constructive
reals by floating approximations: such floats admit
equality, but the abstraction they're representing does not.

In C++, there is a notion that if

        i == j

then

        *i, *j

should denote the 'same value' but the meaning of 
'same value' is an abstraction in the users mind,
not something which can always be represented in C++,
and certainly not something for which any formal
requirements have ever been successfully written.
[Provably, such a requirement cannot be written:
since the value type might be a function, and we know
comparison of functions is undecidable in general]

IF the abstraction being modelled by the value
type admits an equality relation which is encoded
using operator ==, THEN the property

        *i == *j

should probably hold. This is NOT the case for constructive
reals, and quite a few other entities. note that
it IS the case for floating point values 'per se'.

What this means, I think, is that it depends
on precisely how you define your sequence.
If you specify floating values,
you have to assure that exactly the same
calculation is done for each state of an iterator.
If there is just a recurrence relation
the iterator is forward and you can ONLY
use the recurrence relation iteratively.

If you want to use a closed form to get a
random iterator you can do that, again for reals(floats),
but you then must use the closed form for all values.

If you want a hybrid, where you use the recurrence
relation for increment, and the closed form for
random access, you must change the notional value type
from 'floating point' to 'approximate real',
a type which does not have an exact equality
operator. IF you can in fact guarrantee a certain
accuracy, you can provide a comparison that
returns 'true' if two values are close enough.
Beware, however, that such a comparison is
NOT an equivalence relation, so its existence
does not imply algorithms that require an equivalence
relation can be applied using such a comparison.

Note that some algorithms 'overstate' their requirements.
For example sort claims to require a total order over
elements being sorted. This implies that the
relation

        a = b defined by not (a<b or b<a)

must be an equivalence relation. It doesn't
imply that operator== must be that comparison!
For example

        operator<(float,float)

will work fine with constructive reals modelled by floats
and leads to a 'pretty well ordered' result. OTOH, you cannot
apply 'unique', since there's no way to tell if two
constructive reals are equal. [< is not a total order
on constructive reals, but it _is_ on floats, so the algorithm
will terminate with a result which I believe you can show
will 'sort' the elements so that they're 'roughly in order']

-- 
John (Max) Skaller, mailto:skaller_at_[hidden] 
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
New generation programming language Felix  http://felix.sourceforge.net
Literate Programming tool Interscript     
http://Interscript.sourceforge.net