RE: [boost] Rational documentation

From: Paul Moore (gustav_at_[hidden])
Date: 2000-10-20 16:49:35

From: Herve Bronnimann [mailto:herve_at_[hidden]]On Behalf Of
> There is a whole field of number theory devoted to that (I think a
> keyword is Farey series).

I thought there would be... (Actually, I might look into this, out of
interest - I used to be a mathematician...)

> But back to the discussion: std::complex<NT> is supposed to
> be a wrapper around the number type NT, and it's clear that
> complex will only be as good in precision as NT. Since rational
> is NOT a number type, but a wrapper around a number type, just
> as complex, it will inherit the properties of its base type.
>
> My point is that if you want rational<int>, then you should be
> aware that this is not an exact type. But int itself is not an
> exact type, because of its limited range. So users who want
> "exact fraction" should use a base type NT which is exact.
>
> This is easily documentable and it draws an easy line between
> the responsabilities of rational<> and those of NT.

Well, yes. You can say that int is not a mathematical integer, so
rational<int> can't be assumed to be a mathematical rational. But the
correspondence between the limitations of int and the limitations of
rational<int> are quite complex, and depend on the internal representation,
and I believe that it is a necessary part of the documentation to explain
the issues. Much as complexity guarantees are part of the definition of
container classes.

> > There is no way to build a truly exact rational from a
> > limited-range integer (one of the reasons I'd like to see a
> > bigint class in boost is that rational<bigint> is the natural
> > rational number representation)
>
> My point is that I don't think at all of rational<bigint>
> as the "natural" rational number representation. There are
> zillions of bigint representations available, including
> high-quality easily accessible implementations like GMP and
> CLN, LEDA, CORE, you name it. I don't see why such a type
> should be in boost or in any general purpose library. Once you
> want exact (infinite precision) integers, you probably want
> to use them to justify the overhead, so they probably will be
> large. You have to think about using Karatsuba multiplication
> etc, in short, you know where the road starts but not where it
> ends. It's a BIG endeavor. I think you have to know what you're
> up against.

Hm. This is almost exactly what I was avoiding. I agree that for
"specialist" types of work, these types of implementation and technique are
necessary. But that isn't what I was after (and I agree with you that Boost
may not be the best place for such specialised libraries).

But the "average" programmer, writing code which has nothing to do with
numerical processing, still occasionally hits the limits of the built in
numeric types. I remember the days of 16-bit ints, when the number 32767 was
important and scary... With 32 bits, 4 billion seems relatively unlimited,
but maybe not. A bigint class may be appropriate for such users. And maybe
the appropriate performance characteristics for such a beast would be to be
nearly as fast as builtin ints for values up to 32 bits, degrading gradually
as the number of bits increases. A naive implementation will probably
provide this.

Similarly, for rationals, the target audience is people writing simple code
which needs to be able to rely on the idea that if n = 1/3, then 3*n is 1.
And floats cannot do that. Again, what is appropriate here differs from what
is appropriate for high-precision numerical libraries. It would be nice to
think that a naive implementation (which is what mine is) would deliver
appropriate guarantees. But I'm not certain yet that it does. It depends on
"normal use". And the sliding precision is sufficiently hard to characterise
that I worry that it may surprise the target audience. Hence my fixation
with keeping the options open for change. (And my liking for the "cop-out"
solution of rational<bigint> :-)

It's similar to the fact that people "know" that floating point is hard. But
it doesn't stop plenty of useful programs being written without a full
understanding of things like relative and absolute errors, error
propogation, etc.

> I think the class template rational<> can be quite useful even without
> the presence of a bigint type. It certainly complements std::complex and
> boost::interval very nicely.

Thank you. That was certainly the intention.

Paul

PS I must go back over these posts, and put the information together in a
"rationale" section of the documentation, as Beman suggested...