From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 6106 invoked by alias); 2 Mar 2011 10:00:01 -0000 Received: (qmail 5966 invoked by uid 22791); 2 Mar 2011 10:00:00 -0000 X-SWARE-Spam-Status: No, hits=-2.8 required=5.0 tests=ALL_TRUSTED,AWL,BAYES_00 X-Spam-Check-By: sourceware.org Received: from localhost (HELO gcc.gnu.org) (127.0.0.1) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Wed, 02 Mar 2011 09:59:56 +0000 From: "marc.glisse at normalesup dot org" To: gcc-bugs@gcc.gnu.org Subject: [Bug libstdc++/47913] [C++0x] improve ratio_add to overflow less often X-Bugzilla-Reason: CC X-Bugzilla-Type: changed X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: gcc X-Bugzilla-Component: libstdc++ X-Bugzilla-Keywords: X-Bugzilla-Severity: enhancement X-Bugzilla-Who: marc.glisse at normalesup dot org X-Bugzilla-Status: UNCONFIRMED X-Bugzilla-Priority: P3 X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org X-Bugzilla-Target-Milestone: --- X-Bugzilla-Changed-Fields: Message-ID: In-Reply-To: References: X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/ Auto-Submitted: auto-generated Content-Type: text/plain; charset="UTF-8" MIME-Version: 1.0 Date: Wed, 02 Mar 2011 10:00:00 -0000 Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-bugs-owner@gcc.gnu.org X-SW-Source: 2011-03/txt/msg00149.txt.bz2 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47913 --- Comment #7 from Marc Glisse 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.