[Bug libstdc++/42622] New: [C++0x] Improve std::ratio_less to not overflow

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

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