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

[marc.glisse at normalesup dot org]

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

--- Comment #7 from Marc Glisse <marc.glisse at normalesup dot org> 2011-03-02 09:59:52 UTC ---
(In reply to comment #6)
> 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.

> 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.

> 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.

> Are we *really* sure the
> boost::rational implementation is equivalent to GCC and weaker than what you
> are proposing: the first time I looked into it I remember seeing a
> normalization happening earlier toward the end, per the last two lines of that
> comment:
> 
>  // Which proves that instead of normalizing the result, it is better to
>  // divide num and den by gcd((a*d1 + c*b1), g)

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.