Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk