Re: Sign conventions for remainder

From: David Eppstein (eppstein_at_ics.uci.edu)
Date: 06/17/04 

Date: Thu, 17 Jun 2004 13:30:29 -0700

In article <200406171732.i5HHWRG37280@mickey.empros.com>,
 mstemper@siemens-emis.com (Michael Stemper) wrote:

> Just for fun, I've been implementing a package to perform arithmetic on
> integers of arbitrary size. Addition, subtraction, and multiplication
> were all pretty straight-forward. (Subtraction was the easiest!) But,
> when I prepared to implement division, I realized that I'm not aware of
> the conventions for remainders.
>
> If the divisor and the dividend are both positive, I know that my result
> should be d = n*q+r, with 0<=r<n. What if one of them is negative? Should
> the remainder still be in that range? Should it be in the negative of that
> range? What about if both the divisor and the dividend are negative?
>
> Yes, I am aware that there is no "right" answer to this, there are only
> conventions. But, that's exactly what I'm looking for. Conventions are
> usually established because they're useful.

If the divisor is positive, the remainder should still be in the range
0<=r<n, and d=nq+r should still be true. If the divisor is negative,
it's less clear to me what the right convention is -- the choice taken
by Python is to use the same sign as the divisor, which seems reasonable
enough to me.

The C-C++-Java convention of remainder having the same sign as dividend
is wrong and should be avoided. 

-- 
David Eppstein                      http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science

Relevant Pages

  • Re: Dividing 512 bit number by 128 bit number in C program
    ... calculating the quotient and the remainder before returning. ... In one of the inner loops, the divisor is positioned so that its most ... A bit-wise subtraction of divisor from dividend is performed ... bool borrow = false; ...
    (sci.crypt)
  • Re: Sign conventions for remainder
    ... Addition, subtraction, and multiplication ... What about if both the divisor and the dividend are negative? ... The remainder is a piece of the dividend; ...
    (sci.math)
  • Sign conventions for remainder
    ... Addition, subtraction, and multiplication ... the conventions for remainders. ... If the divisor and the dividend are both positive, ...
    (sci.math)
  • Re: Sign conventions for remainder
    ... What about if both the divisor and the dividend are negative? ... > If the divisor is positive, the remainder should still be in the range ... options in your package for the several possible sensible behaviours. ...
    (sci.math)
  • Re: How to perform integer div with SIMD?
    ... First, use the approximate reciprocal lookup to generate a set of starting values, then one or two NR iterations (also in SIMD fp mode) to get a more precise value. ... If negative, subtract one from the result, add divisor to remainder. ...
    (comp.lang.asm.x86)