Re: [boost] Formal Review for Interval Library- getting intervals of constants

From: Sylvain Pion (pion_at_[hidden])
Date: 2002-09-06 14:39:57

Salut Gaby,

First I'd like to say that I feel guilty for the confusion.  I should not have
mixed the two separate issues that arise in the IA library wrt this topic.

The first issue #1 is how to create the compile-time constants for the best
lower and upper bounds of PI for the float, double, long double.

The second issue #2 is the dynamic rounding mode usage (which are not available
in LIA-1/C++ but in IEEE/C), used at run time (by almost all current
Rounding_policy classes) in the IA library to do its computations.

These two issues are almost completely unrelated.
This is actually the first issue that worries me the most here (the original
one that I mentionned).

For the second issue, I definitely can see an implementation using only LIA-1
(which could easily be provided as a Rounding_policy class), based on
rnd_epsilon for example.  I still claim it would be sub-optimal wrt what can be
done in hardware if you allow access to dynamic rounding modes available with
IEEE (hence the reason why the default, which targets common hardware, which
supports IEEE, uses IEEE).  The framework of IEEE is maybe not precisely
enough for that, but I'm ready for #ifdefs of particular platforms to get it
working around quircks.

Now for the first issue, the question is not related to dynamic rounding modes
at all, since I want to generate compile-time constants.  The question is how
to generate them.  They have to be correct (lower bound <= PI, and upper bound
>= PI) up to the last digit, and if possible (it's kind of important, hence I
add this in my constraits), be the best bounds for PI with a given FP type.

On Fri, Sep 06, 2002 at 10:41:31AM +0200, Gabriel Dos Reis wrote:
> | For example, changing dynamic rounding modes is not something available in
> | standard C++ (it is in ISO C though).
> | So we could implement an IA based on LIA-1 only I guess (via a Rounding_policy
> | class), using numeric_limits::rnd_epsilon, but that would make the intervals
> | larger than necessary (because LIA-1 has no counter part to IEEE's inexact
> | flag for once), and/or it would be inefficient.
> 
> I think you're misinterpreting something.  
> 
>   1) LIA-1 makes conformance to IEEE-754 optional.  In C++, the
>      binding is that if in addition of conforming to LIA, an executing
>      environnement wants to support IEEE-754, then
>      numeric_limits<>::is_iec559 is true.

OK.

>   2) LIA-1 requires way to detect the rouding styles.  C++ defines
>      integral constants expressions to access them.

Yes, that's fine.  I just claim it's basically useless for me for both issues.
LIA-1 only knows about a fixed, static, rounding mode anyway, so out for #2.
Note that a good IA implementation usually relies on _dynamic_ rounding modes
(that you can select for each arithmetic operation done at run time).
In the framework of LIA-1 (if we ever get to implement a Rounding_policy based
on LIA-1), knowing the round_style will maybe help slightly, I agree.

>   3) The above by themselves don't make the think suoptimal for the
>      particular problem at hand.

For issue #2, I still claim that relying on LIA-1 only (i.e. no dynamic
rounding modes) if you can access IEEE is usually sub-optimal in sharpness of
the intervals, as well as probably in performance.
I'd be happy to be proven wrong with some code !

> | > | To recall, what I want is the sharpest interval bounds (for float, double,
> | > | long double) on PI (other constants might follow, but this one is needed for
> | > | the trigonometric functions).
> | > | 
> | > | As mentionned above, the standard doesn't impose any particular rounding style,
> | > | so you can't assume a particular one,
> | > 
> | > Certainly, however the standard does list the possibilities.  And
> | > those are given by integral constant expressions.  So the picture is
> | > not that dark.
> | 
> | It still doesn't help at all in practice : if I want to support platforms with
> | round_style=indeterminate I do have to handle the worst, painful case.
> 
> Again, I think you're misinterpreting something.  
> 
>   1) Obviously if you *want* to support platforms with
>      round_style=round_indeterminate, then you're willing to do the
>      necessary work to provide the support, i.e. you *want* to do the
>      painful case.  So what?

The question is for issue #1 here.
For issue #1, we are at compile-time, there's no question of efficiency.
So it is of no use to know round_style since I have to target the lowest
common denominator.  If I did use the knowledge of round_style, I could write
a simpler version for my constants probably (remains to be proved, see later), 
but then I would also need to have the other version, which would be more
general (will be usable for the case where I know round_style is nice).
So using this knowledge if only useful if _additionnaly_ I also know that I
won't have to support the non-nice round_style platforms, because then I can
get rid of some code.  If I can't assume that, I have to keep 2 versions of
the code, one being strictly more general than the other, hence making the
specialized case useless.
Do you get now why I say this knowledge is useless to me ?

You argue for using only LIA-1 for portability concerns.  Is it that the same
argument (of portability to platforms with round_style=round_indeterminate)
which I use, is not relevant to you ?
It's not that I *want*, it's that I *have* to support it anyway.

>   2) the case round_indeterminate represents just 1/5 of all possibilities
>      (assuming they all have the same probaibilities).

So what ?  I have to take it into account.
I doesn't help me to know it.
It would help if I knew that all desired platforms had round_style=nearest.
That's not the case.

>   3) round_indeterminate doesn't mean anarchy.  It means the rounding
>      style is indeterminable as a compile-time constant.

Agreed.
So, always my original question : how do I generate my compile-time constants ?

> | > | Is there a cleaner way to do that ?
> | > 
> | > Figure out how a good approximate value can be computated as a
> | > function of digits, and other parameter.  IMO, that is much more
> | > scalable and robust.
> | 
> | ... and sub-optimal !
> 
> I think you missed my point.  Obviously, when you asked Maple (or
> whatever programs) to give you a number, then print them using a
> specified format, the answer was a function of the specified format.
> My point is to use the underlying algorithm to generate the constants.
> There is nothing sub-optimal in that.

You missed _my_ point : I have no problem to using any algorithm to generate
these constants.  BUT, given that I want COMPILE-TIME constants, I need a
COMPILE-TIME algorithm.  That's my point.  So what is this algorithm ?  Please
give it to me if it's so obvious to you.

The naive approach (which I guess is what you had in mind) is to use a RUN-TIME
algorithm, and make it dump enough precision in decimal (e.g. Maple), and just
use this.
But this DOES NOT work : it is not reliable enough given the precise
constraints that I have given.
Read again my quote of the C++ standard from [2.13.3.1].
The key remark in this paragraph is that if the decimal scaled value is NOT
representable (which is what you highly probably get with the naive approach),
then the necessary rounding which is done by the compiler at compile-time is
implementation-defined.  So, as I want to be sure of the correct FP values that
I get, I need to fall back on a decimal value which is EXACTLY representable
in the compiler's FP format (which I can know via numeric_limits::digits and
radix).  Which is what led me to my proposal : testing in a compile-time switch
(several ?: ) using numeric_limits::digits (and this method should also switch
on radix to be complete).

If you don't agree, please give me your solution.
I'd love to have one which is simpler than mine.

-- 
Sylvain