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

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

[paolo dot carlini at oracle dot com]

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

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

[paolo dot carlini at oracle dot com]

-- 

paolo dot carlini at oracle dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2010-01-09 22:53:26
               date|                            |


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

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

[paolo.carlini at oracle dot com]

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

--- Comment #9 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-03-02 15:06:29 UTC ---
Applied, thanks.

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

[marc.glisse at normalesup dot org]

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

--- Comment #8 from Marc Glisse <marc.glisse at normalesup dot org> 2011-03-02 14:58:06 UTC ---
Created attachment 23514
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=23514
4 lines of comments...

It might be better to write a single paragraph explaining the algo instead of a
couple lines at each step.

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

[paolo.carlini at oracle dot com]

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

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.6.0

--- Comment #7 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-02-28 16:48:57 UTC ---
Done.

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

[paolo at gcc dot gnu.org]

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

--- Comment #6 from paolo at gcc dot gnu.org <paolo at gcc dot gnu.org> 2011-02-28 16:46:28 UTC ---
Author: paolo
Date: Mon Feb 28 16:46:23 2011
New Revision: 170567

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=170567
Log:
2011-02-28  Paolo Carlini  <paolo.carlini@oracle.com>

    * testsuite/20_util/ratio/comparisons/comp3.cc: New.

2011-02-28  Marc Glisse  <marc.glisse@normalesup.org>

    PR libstdc++/42622
    * include/std/ratio (ratio_less): Reimplement to never overflow.
    * testsuite/20_util/ratio/comparisons/comp2.cc: Extend.

Added:
    trunk/libstdc++-v3/testsuite/20_util/ratio/comparisons/comp3.cc
Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/std/ratio
    trunk/libstdc++-v3/testsuite/20_util/ratio/comparisons/comp2.cc

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

[paolo.carlini at oracle dot com]

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

--- Comment #5 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-02-28 14:51:08 UTC ---
Well, I can check, but if you sent already the form, it should be matter of 1-2
weeks max for you to get back via email the pdf of your assignment. When did
you send the form signed?

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

[marc.glisse at normalesup dot org]

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

--- Comment #4 from Marc Glisse <marc.glisse at normalesup dot org> 2011-02-28 14:45:42 UTC ---
(In reply to comment #3)
> I think the patch is small enough
> to go in at your name without Copyright Assignment.

I believe I am supposed to have the paperwork in order now. Would you mind
checking so I don't write anything else if it is not the case?

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

[paolo.carlini at oracle dot com]

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

--- Comment #3 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-02-28 14:32:09 UTC ---
Testing at my end went well. I guess I'm going to apply the patch for 4.6.0,
together with an handful of additional tests. I think the patch is small enough
to go in at your name without Copyright Assignment. Thanks again! Please, if
you notice something wrong over the next weeks, before the release of 4.6.0,
please let me know ASAP.

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

[paolo.carlini at oracle dot com]

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

--- Comment #2 from Paolo Carlini <paolo.carlini at oracle dot com> 2011-02-28 11:15:44 UTC ---
Thanks Marc, let me have a closer look to the code and some testing.

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

[marc.glisse at normalesup dot org]

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

--- Comment #1 from Marc Glisse <marc.glisse at normalesup dot org> 2011-02-28 07:49:42 UTC ---
Created attachment 23487
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=23487
proposed fix

Not thoroughly tested, but it seems to pass comp1.cc and comp2.cc.