From: Nickolay Mladenov (nikiml_at_[hidden])
Date: 2001-01-12 10:33:56
What is wrong with the negative reminders?
Shouldn't one just check the result(before return) for it's sign?
Has anybody done any comparison of the speed of gcd if r is substituted
with the min(abs(r) ,abs(m-r),abs(m+r) )?
Stephen Silver wrote:
> Dean Sturtevant wrote:
> > And the comparison within the algorithm is a
> > little strange: Why would n % m be < 0 ? I would have thought that
> > any reasonable def of '%' would always yield non-negative numbers?
> Unfortunately, the definition is not reasonable. The original ANSI C
> standard did not specify the direction of rounding in integer division
> if either operand is negative, and the C++ standard simply adopts
> this lax approach. Worse still, the C99 standard actually requires
> truncation towards zero, and this is what most current C++ compilers
> do in practice. Quotients and remainders are linked by the formula
> (a/b)*b + a%b == a
> so truncation towards zero inevitably leads to negative remainders.
> Also note that the boost::rational documentation says "division should
> truncate", which I take to mean "towards zero" (although perhaps this
> should be clarified).
> But if gcd() started by taking the abs() of its arguments, then it
> would have no need to make this negativity test inside the loop.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk