ratio_add currently computes something like: gcd=gcd(den1,den2) num=num1*(den2/gcd)+num2*(den1/gcd) den=den1*(den2/gcd) gcd2=gcd(num,den) num/=gcd2 den/=gcd2 In cases where gcd2 is not 1, the computation may overflow whereas the final result would fit. Even without that, it is possible that one or both of the terms added in num are too large but their sum is not. As a quality of implementation issue, it would be nice to reduce those cases a bit. But that comes far far behind the ratio_less improvement described in PR 42622.
Looks like there is a pretty simple (eg, no continued fractions & co) way to do this: http://www.boost.org/doc/libs/1_46_0/boost/rational.hpp
(In reply to comment #1) > Looks like there is a pretty simple (eg, no continued fractions & co) way to do > this: The continued fraction thing for ratio_less may actually be easier: - compare the integral parts - if they are equal, remove that integer and compare the inverses - have a terminating criterion (when denominators are 1?) > http://www.boost.org/doc/libs/1_46_0/boost/rational.hpp The runtime fraction addition in this file is what gcc currently does. I also looked at ratio.hpp (and what it includes), which factors out the gcd of the numerators and multiplies back with it at the end. That's a slight but fairly limited improvement, I'm sure we can do better.
Well, if you could come up with some code... By the way, I don't think what Boost does right now for operator+= is *exactly* the same, see the last two lines of the comment. I'm unassigning myself for now.
By the way, a couple of testcases, would not hurt.
Created attachment 23509 [details] Overkill I was having a hard time making it nice and clean, so I went for totally overkill. It might be a bit scary to have 200 lines of code just to implement an addition. And questionable whether avoiding a few overflows is worth the complication. On the plus side, it makes it possible to give a simpler implementation of ratio_less. And __safe_add can be removed (24 lines). I'll try again to come up with a simpler solution.
Thanks again for your help on this. Preliminarily, a few observations: 1- Please make sure the code is minimally documented (are the comments in longlong.h enough?); 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. 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? 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)
(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.
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.
(In reply to comment #8) > Right. Mine was sort of a general comment: the comments in ratio_less are also > rather terse ;) I'll try to expand a bit on them. > 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. If intmax_t is guaranteed to be one of int/long/long long, then it seems that it has to be equivalent to long long. I was more afraid that it might be a bigger type than long long. (by the way, __builtin_clz takes an unsigned argument) > 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. I think there is nothing wrong with the implementation of ratio_add currently in libstdc++ (shipping it as it is seems fine), but we could indeed easily avoid all unnecessary denominator overflows (attachment in a minute). The factorization of the gcd of numerators is a heuristic that sometimes helps but doesn't really close a category of overflow, so I am more reluctant to add it, but it is really easy if you think it should be done.
Created attachment 23512 [details] avoid denominator overflows (untested)
Thanks for the attachment. Do you have a small testcase for it? I would test here, commit, and then we can proceed with more serious changes for post 4.6...
About int/long/long long I see what you mean, but we should double check that __builtin_clzll is unconditionally available and the same as __builtin_clz if intmax_t == int (etc): at the moment I'm not 100% sure.
(In reply to comment #11) > Thanks for the attachment. Do you have a small testcase for it? I would test > here, commit, and then we can proceed with more serious changes for post 4.6... constexpr intmax_t m=(intmax_t)1<<(4*sizeof(intmax_t)-1); ratio_add<ratio<1,(m-1)*(m-2)>,ratio<1,(m-3)*(m-2)> > fails with the current libstdc++, works with the small patch, works with boost.
Excellent.
Author: paolo Date: Wed Mar 2 14:57:57 2011 New Revision: 170616 URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=170616 Log: 2011-03-02 Marc Glisse <marc.glisse@normalesup.org> PR libstdc++/47913 * include/std/ratio (ratio_add): Avoid denominator overflow. * testsuite/20_util/ratio/operations/47913.cc: New. Added: trunk/libstdc++-v3/testsuite/20_util/ratio/operations/47913.cc Modified: trunk/libstdc++-v3/ChangeLog trunk/libstdc++-v3/include/std/ratio
Done. Then we can add more tests to 47913.cc.
Some more examples. Using the constants: m=INTMAX_MAX; n=INTMAX_MAX/2; p=((intmax_t)1<<(4*sizeof(intmax_t)-1))-3 (m,2)-(m,3)==(m,6) boost should manage this one (m/7*5-1,5)-(m-2,7) __big_mul would be enough (__big_div is the hard thing) (n-5,15)+(n,35) one could cheat by removing the integral part (p^2,(2*p-3)*(p-2))-(p+2,(p-1)*(p-2)) one may be able to write gcd=(p-2), p^2 as (p+2)*gcd+4 and the computation of the numerator becomes gcd*((p+2)*(p-1)-(2*p-3))+4*(p-1)-4*(2*p-3) and both computations (p+2)*(p-1)-(2*p-3) and 4*(p-1)-4*(2*p-3) fit in a intmax_t. But with a larger gcd, they may not (I'll try to add an example later).
(In reply to comment #17) > Some more examples. Using the constants: > m=INTMAX_MAX; > n=INTMAX_MAX/2; > p=((intmax_t)1<<(4*sizeof(intmax_t)-1))-3 > > (m,2)-(m,3)==(m,6) boost should manage this one I'm not sure to understand, I was under the impression that right now GCC is essentially equal to boost::rational?!?
(In reply to comment #18) > I'm not sure to understand, I was under the impression that right now GCC is > essentially equal to boost::rational?!? That's the heuristic I was mentioning at the end of comment #9. I could add it if you like. I am reluctant because, as I said, it is just a heuristic that doesn't close a class of problems but only a few random cases.
Ah, ok then: when I looked a bit into boost::rational it seemed pretty simple, didn't notice that additional simplification. Thanks for the additional set of tests, anyway, as soon as 4.6 is out of the door, we'll move ahead.
Created attachment 24182 [details] first iteration in patch format Inserted in <ratio>, with some cleanup of dead code, rewrite of ratio_less. The static_assertions should help notice problems (in particular the __big_div ones should be good). I haven't tested much, but it seems to pass the current testsuite. Additional tests (no time to format or check them now) are available: * at the end of the "overkill" attachment * in comment #13 and comment #17
Thanks a lot Marc. Let me work on this, add all the testcases we have around, regression test again.
Nit (for the future): library patches are diffed from where the library ChangeLog is.
Author: paolo Date: Wed May 4 23:23:54 2011 New Revision: 173400 URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=173400 Log: 2011-05-04 Marc Glisse <marc.glisse@normalesup.org> PR libstdc++/47913 (again) * include/std/ratio (ratio_add, ratio_less): Rewrite. * testsuite/20_util/ratio/operations/47913.cc: Extend. * testsuite/20_util/ratio/cons/cons_overflow_neg.cc: Adjust dg-error line numbers. * testsuite/20_util/ratio/operations/ops_overflow_neg.cc: Likewise. Modified: trunk/libstdc++-v3/ChangeLog trunk/libstdc++-v3/include/std/ratio trunk/libstdc++-v3/testsuite/20_util/ratio/cons/cons_overflow_neg.cc trunk/libstdc++-v3/testsuite/20_util/ratio/operations/47913.cc trunk/libstdc++-v3/testsuite/20_util/ratio/operations/ops_overflow_neg.cc
Completely done for 4.7.0.