This is the mail archive of the
gcc-bugs@gcc.gnu.org
mailing list for the GCC project.
[Bug libstdc++/42622] New: [C++0x] Improve std::ratio_less to not overflow
- From: "paolo dot carlini at oracle dot com" <gcc-bugzilla at gcc dot gnu dot org>
- To: gcc-bugs at gcc dot gnu dot org
- Date: 5 Jan 2010 12:11:14 -0000
- Subject: [Bug libstdc++/42622] New: [C++0x] Improve std::ratio_less to not overflow
- Reply-to: gcc-bugzilla at gcc dot gnu dot 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