From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 21254 invoked by alias); 5 Jan 2010 12:11:26 -0000 Received: (qmail 21204 invoked by uid 48); 5 Jan 2010 12:11:14 -0000 Date: Tue, 05 Jan 2010 12:11:00 -0000 Subject: [Bug libstdc++/42622] New: [C++0x] Improve std::ratio_less to not overflow X-Bugzilla-Reason: CC Message-ID: Reply-To: gcc-bugzilla@gcc.gnu.org To: gcc-bugs@gcc.gnu.org From: "paolo dot carlini at oracle dot com" 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: 2010-01/txt/msg00512.txt.bz2 This is just an internal reminder: we should implement the following suggestion from Howard on the library reflector. Maybe Chris is interested... ///////////////// I just recently became aware that it is possible to do this comparison without any chance of overflow. This is accomplished by converting each ratio to a continued fraction, term by term so that the memory used is O(1): stack based - not O(N): heap based. And then you compare the terms of the continued fractions, as they are created, and then forget them. This process does not involve multiplication, only / and %, thus no overflow. Boost rational uses this technique, and I have implemented it in a example implementation. The complexity of it is approximately the same amount of code I used in my previous implementation which did go to great lengths to avoid overflow as much as I knew how at the time. Both my previous implementation and my current implementation are much more involved than simply evaluating R1::num * R2::den < R2::num * R1::den (on the order of 60 lines of code instead of 3 lines of code). All cost is incurred at compile time, not run time. For my money, the compile-time cost is worth it. Other implementations (or clients of those implementations) may or may not feel that way. Here is an algorithm for comparing continued fractions: http://perl.plover.com/yak/cftalk/TALK/slide045.html Algorithms for converting rationals to continued fractions are common and found elsewhere/everywhere. -- Summary: [C++0x] Improve std::ratio_less to not overflow Product: gcc Version: 4.5.0 Status: UNCONFIRMED Severity: enhancement Priority: P3 Component: libstdc++ AssignedTo: unassigned at gcc dot gnu dot org ReportedBy: paolo dot carlini at oracle dot com http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42622