[boost] [Boost-bugs] [ boost-Patches-1438991 ] rational::operator<(rational) fails due to overflow

From: SourceForge.net (noreply_at_[hidden])
Date: 2006-11-02 11:28:14

Patches item #1438991, was opened at 2006-02-26 07:54
Message generated for change (Comment added) made by dlwalker
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=307586&aid=1438991&group_id=7586

Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: None
Group: None
>Status: Closed
>Resolution: Duplicate
Priority: 5
Private: No
Submitted By: David Benbennick (dbenbenn)
Assigned to: Jonathan Turkanis (turkanis)
Summary: rational::operator<(rational) fails due to overflow

Initial Comment:
Consider boost::rational<long>.  Pick two objects of
that type at random (that's well defined, since there
are only finitely many objects of that type), and pick
them to both have the same sign.  Call them a and b. 
Then the expression "a < b" returns the wrong value 50%
of the time!  The problem is that the calculation in
rational.hpp can overflow, and that overflow actually
happens most of the time.

Here's a patch that implements operator< without
overflow.  It's somewhat less efficient (I haven't
benchmarked it) but it gives the right answer.

Possibly the new version of operator< has bugs.  I've
run a few hundred million random tests, with the right
answer every time (I've used bc to check the answers),
but there might be a subtle problem.  In particular,
the new code assumes that integer division always
truncates towards 0, even when dividing negative
integers.  Perhaps that is not true on some obscure
platforms/compilers?

----------------------------------------------------------------------

>Comment By: Daryle L. Walker (dlwalker)
Date: 2006-11-02 11:28

Message:
Logged In: YES 
user_id=551024

The problem was also described as bug #798357.
Your issue should be fixed since I've fixed the other
bug. I used continued-fraction expansion, with the
components found by the Euclidean GCD algorithm
and forcibly floor-rounding division & modulus.

----------------------------------------------------------------------

Comment By: David Benbennick (dbenbenn)
Date: 2006-03-07 16:08

Message:
Logged In: YES 
user_id=95581

Here's a new patch that uses std::numeric_limits to select
the more efficient, direct comparison method for unbounded
types, and only uses the overflow-avoiding method for types
that can overflow.

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=307586&aid=1438991&group_id=7586

-------------------------------------------------------------------------
Using Tomcat but need to do more? Need to support web services, security?
Get stuff done quickly with pre-integrated technology to make your job easier
Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642
_______________________________________________
Boost-bugs mailing list
Boost-bugs_at_[hidden]
https://lists.sourceforge.net/lists/listinfo/boost-bugs