[Bug libstdc++/47913] [C++0x] improve ratio_add to overflow less often

["paolo.carlini at oracle dot com" <gcc-bugzilla@gcc.gnu.org>]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47913

--- Comment #8 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-03-02 10:59:06 UTC ---
Hi,

> > 1- Please make sure the code is minimally documented (are the comments in
> > longlong.h enough?)
> 
> Ok, I wasn't sure it was worth it if the code was unlikely to ever make it.

Right. Mine was sort of a general comment: the comments in ratio_less are also
rather terse ;)

> > 2- I see stuff like __builtin_clzll(__d) on __d a uintmax_t, I'm not sure it's
> > always ok, on any 32-bit and 64-bit target.
> 
> Do you have a better alternative in mind? Should I reimplement it using
> templates? It shouldn't be too hard, but I would check on the gcc ML first.

I don't think you should really handcode something, just pick the right
__builtin_* depending on the actual type of uintmax_t (after all it's just a
typedef for one of the builtin types). Thus, if we aim for something really
general here, use just a bit of templates to pick the best match among the
various available __builtin_*, via make_signed on uintmax_t and then three
special cases for int, long, long long. Granted, probably on widespread 32-bit
and 64-bit machines, long long it's indeed a safe bet.

> > More generally - I'm asking to Marc the mathematician
> > here, not Mark the libstdc++ contributor - do we have a clear characterization
> > of which specific overflows can be avoided?
> 
> All of those where both the input and the output are legal std::ratio.

Right. I was just curious to understand whether we can somehow characterize the
inputs which are going anyway to overflow either numerator or denominator. I'm
trying to figure out what the brute force approach boils down to: is it just
matter of attempting simplification at each arithmetic operation, or we have to
do also something else, of a more global nature in order to achieve the goal?
Whatever we do, I think eventually we need something in a comment before the
code anyway...

> Boost isn't exactly equivalent to gcc. Making a mix of their ratio and rational
> (and possibly extrapolating a bit), they avoid some overflows of the numerator
> by factoring out the gcd of the numerators, and they avoid all overflows of the
> denominator by reducing the numerator with the gcd of the denominators so they
> can compute directly the right denominator. They still fail on 2 types of
> numerator overflow, either when the numerator is too large before
> simplification with the gcd, or when the 2 products are large but their sum is
> small. The example at the end of the attached file shows the second case.

Understood. Since 4.6.0 is approaching, do you think it would make sense for
this release series to modify only a bit the GCC code, to the point that we are
as good or even slightly better, if possible, than Boost, without requiring too
much new code? I fear regressions, as you of course can easily understand.
Ideally, we should add, mano a mano, testcases for each "subclass" of inputs
which we are able to process without overflowing.