[boost] [Boost-bugs] [ boost-Bugs-798357 ] rational operator< can overflow

From: SourceForge.net (noreply_at_[hidden])
Date: 2003-08-31 21:57:13

Bugs item #798357, was opened at 2003-09-01 02:57
Message generated for change (Tracker Item Submitted) made by Item Submitter
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=107586&aid=798357&group_id=7586

Category: None
Group: None
Status: Open
Resolution: None
Priority: 5
Submitted By: Derrick Bass (derrickbass)
Assigned to: Nobody/Anonymous (nobody)
Summary: rational operator< can overflow

Initial Comment:
I recently discovered that the operator< for the rational 

template is prone to overflow. It is noted in the design 

documentation that some care was taken to prevent 

overflows for most operators, but apparently not for this 

one.

The basic problem comes from the fact that it checks if

n1/d1 is less than n2/d2 by checking if n1 d1 < n2 d1. Those 

products can easily overflow.

I suggest an algorithm that first checks the integer parts of 

the quotients. If they are equal, then the algorithm could be 

based on the observation: for n1<d1 and n2<d2 and 

everything positive and d1<d2, then

n1/d1 < n2/d2 iff n1/d1 < n2-n1/d2-d1.

So if we write d2 = q d1 + r then

n1/d1 < n2/d2 iff n1/d1 < n2-q n1/r

One would then recursively check this inequality. Obviously, 

a similar observation would have to be made for d2<d1.

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

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

-------------------------------------------------------
This sf.net email is sponsored by:ThinkGeek
Welcome to geek heaven.
http://thinkgeek.com/sf
_______________________________________________
Boost-bugs mailing list
Boost-bugs_at_[hidden]
https://lists.sourceforge.net/lists/listinfo/boost-bugs