Re: [boost] Re: Re: [rational] Announcing new maintainer -- call for feature requests

From: Andras Erdei (aerdei_at_[hidden])
Date: 2005-04-12 11:26:48

On Apr 9, 2005 3:11 PM, Andy Little <andy_at_[hidden]> wrote:

> The use of decimal point representation is not an ideal means to
> represent a rational number.

of course not, i just did not bother with looking up the the original example
which was rational<short> with 191/181 (=1.055...) + 197/193 (=1.021...)
resulting in 6984/-30603 (=-0.229...) on my PC

[the correct result is 72520/34933 (=2.076...) and the rounding implementation
gives 3197/1540, precise to 7 decimal digits]

> Use of a bigger int would solve the overflow issue.

if you mean a bigger, but still finite int, then no it doesn't; with a 16 bit
short rational<short> can represent roughly 2^29 different values, out of
which let's say 2^13 can be used safely (added together without "overflow"),
which is less than 0.002% of them; if you try to solve this by switching to
rational<int> (assuming 32 bit ints), you will be able to add together all
your rational<short>s, *but not the results of these additions* (only about
2*10^-8 percent of those results are still "addable"); so yes, you can make a
single operation work, but that is far from having a useful arithmetic, where
you can add together even three or four numbers

if you mean "bigint" -- i did not want to fight on several fronts, but it
looks like we really have to discuss everything at the same time:

exact (unlimited precision) precision arithetic is a different issue, which
may or may not have something to do with the discussion about rational<>

if we want an exact type (and we do want it) the tasks are to reach an
agreement about the interface and semantics of the type, and to provide an
implementation, where we have several options including some kind of
rational<bigint> and also unlimited "fixed point", something based on
continued fractions and a lot of more esoteric ones (like linear fractional
transformations, iterated exponential functions etc)

imho the interface and semantics in any case should allow using expression
templates (unlike the current rational rational proposal made for the
standard) and possibly some kind of lazy arithmetic (i'm not sure about this
latter one), and they definitely should allow _any_ conceivable
implementation, and not limit it to rational<bigint>

the single rational<bigint> implementation itself should not determine the
looks of our exact type

imho the finite precision rational<> (which is useful in itself and is a
viable alternative for float) is a separate issue from having an exact
arithmetic type

> I disagree. . boost::rational  provides services such as conversion and i/o
> which otherwise one has to manually code. It makes the intent clearer
> and is one
> less thing to worry about.( you may also require division).  You may see
> this as
> a trivial use.. but  I would certainly prefer to use it in this context,
> because
> it models the problem well.

this is true, and i actually thought about mentioning it in my post, but then
decided to let it go -- rational<> can be used as this kind of convenience
class regardless of the issues (rounding) we are discussing

> The imperial lengths example is one where the gcd  for different units
> != 1.
> My use of a rational number would be to store the units only (because of
> the
> overflow issues) and use a double for the value.  To find the scaling value
> between units involves only a division. As in the above case one could
> use an integer, with "a tiny bit more work".

ok, got it now

>>> I would guess that these are the major uses of rational and all have
>>> values in quite a small range.

as you can see in the example at the top, the values being small (whenever
you mean by this that the actual values are small, or that the numerators and
denominators used in the representation are small) is no guarantee against the
kind of "overflow" we have been discussing

also, imho naive users will not expect things like operator< to "overflow" as
they do in the current boost::rational<>

imho basically everything overflows, all the time, and in the few cases where
it doesn't, you don't gain anything by using the non-rounding legacy
implementation

> The heart of the issue seems to be  accuracy of analogue numbers. This is
> obviously a big and important ( and neverending ) topic but I cant help
> feeling
> it is a bit bigger than boost::rational. How about a boost::irrational
> or some
> other name?

not sure i got this one; are you proposing to leave the current
boost::rational<> as it is, and introducing some other name instead for the
rounding type?

>> it is not necessary to limit rational<> to use the same type for
>> representing the numerator and denominator, so there is no single
>> value_type/int_type to publish
>>
>> it is not necessary to limit rational<> to represent the numerator and
>> denominator in separate members (i've posted a much more efficient
>> implementation of the current boost::rational<> which requires both the
>> numerator and denominator to be stored in the same data member to be
>> efficient), so the published value_type/int_type may not convey any
>> useful information for the users of rational<>, as you cannot define
>> how is it related to rational<>

> One would require it to interact with other types (presumably inbuilt
> types) at least for purposes of initialisation and conversion.  You need
> to know what types to use as initialisers.

but that is again a different issue: of course it has to export the types
returned by numerator() and denominator(), but iirc you were referring to some
other use (something like determining whether the given rational is
implemented using built-in types) -- am i wrong?

>>> As far as errors due to overflow, the problem is not actually in the
>>> domain of rational  but of the value_type as has been stated before.

>> stated, but not convincingly explained :O)

> This is simply the finite_int, versus bigint issue. Use a bigint to avoid
> overflow. Use an int for speed and small footprint, where you have a
> small range in numerator, denominators values.

imho use an exact type where computations need to be exact, and use finite
precision rationals where floats are crap (or rather, use them by default, and
switch to floats when speed requires it, and you are sure you wont be hurt by
them)

>>> rational shouldnt need to know anything about the behaviour of its
>>> value_types operations.

>> but that requirement results in rational<>s that are both inefficient and
>> useless (cannot round)

> Is a rational number implementation that has been rounded, a rational
> number?...  Yes, but not the one you expected.

can you rephrase this (most likely i don't get this one because of my english)

> How do you know if it has been rounded?

one option is to use the rational<> variant which maintains an exactness flag
(should worth mentioning here i'm not sure i've chosen the right word, the
flag can mean both a rounded result of an operation on exact values and a
value which comes from some inexact source, like a measurement)

the other option is not to bother with it, just like you do in every other
case of finite aritmetic (ints and floats)

> Will the rounding be the same on different implementations.

yes

for finite precision rationals there is "natural" rounding which is
well-defined, independent of the actual implementation, and has tons of nice
mathematical and practical properties

this is in contrast with rounding in radix-based arithmetic (fixed and
floating point) where the rounding can be very suprising (e.g. the default
rounding method used by your PC is to round to the nearest number, but it is
the nearest *binary* number, so 1/3=0.3333... is 0.33..34, not 0.33..33 as it
would be with decimal representation, which comes as quite a shock to most
people)

also, different rational systems are "embedded" in each other, so if you make
conversions between two such systems (be it rational<short> and rational<int>
on one machine, or between rational<int>s on different machines) there is at
most one step where the number changes (gets rounded to a value in the less
precise system)

in contrast, converting a number from decimal scientific notation into the
best binary floating point approximation cannot be done using finite
arithmetic (this is why the IEEE standard does not require the result to be
the best approximation), and iirc repeated conversion between two floating
point systems can even result in diverging results

this may sound as an esoteric problem, after all who uses non-binary machines?
but in fact we all do -- computations are made on binary representations, but
i/o (including storing/transferring your numbers for non-human consumption) is
usually done using decimal representation

> Keep
> rational for use on 'rational numbers'  where absolute predicability,
> repeatability and accuracy is required.

i'm not sure if you mean by this to 'keep the name rational for exact
arithmetic' or 'keep the name rational for the legacy boost implementation'

> OTOH You have requirements for a type that has some of the theoretical
> properties of rational

imho boost::rational<> does not have the theoretical properties of rationals
(whatever those are), but can mislead people into thinking it does

imho boost::rational<bigint> has the theoretical properties of an exact
arithmetic type, but there are implementation details leaked into the
interface, and it is not a very efficient implementation of an exact type (as
it is not very efficient implementation of an unlimited precision rational
type, because it makes a half-hearted attempt at being both a finite and an
unlimited arithmetic type)

> but also with some of the properties of a float
> (approximate representation of numbers which may or may not be rational
> numbers). That is not rational but is interesting. Perhaps it would be

that is not a rational, but a finite precision rational

> interesting to talk about how this type might be implemented and what its
> properties and requirements might be.

trying to do that :O)

br,
andras