Re: Sign conventions for remainder

From: Sean O'Leathlobhair (jwlawler_at_yahoo.com)
Date: 06/18/04 

Date: 18 Jun 2004 04:29:13 -0700

David Eppstein <eppstein@ics.uci.edu> wrote in message news:<eppstein-C64F96.13302917062004@news.service.uci.edu>...
> 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.

Are you talking about the Java primitive numeric types or the classes
BigInteger and BigDecimal?

The documentation for BigInteger does not seem to be very clear on the
exact details of the remainder and I have never had the need to check.
 I may knock a simple test program and post the results.

The class BigDecimal approaches the problem a different way. The
divide method has a plethora of options on how to round divisions. So
it dumps the problem onto the user. You could copy this idea and have
options in your package for the several possible sensible behaviours.

One behaviour that is common but I don't like is round towards zero.
Non-mathematicians seem to like it since they seem to expect that -5 /
4 should be similar to 5 / 4 except for the sign i.e. +/- 1 rem 1.
The reason that I don't like it is that the graph of x rem n has an
anomaly at x = 0 which sometimes messes up functions built on top of
it.

Opinions vary, give your users the choice.

Here is a link to the Java API docs:
http://java.sun.com/j2se/1.3/docs/api/

Seán O'Leathlóbhair

Relevant Pages

  • [SUMMARY] Long Division (#180)
    ... is done repeatedly dividing the divisor into each digit of the ... dividend combined with the remainder of the previous division step. ... And so our quotient is 0372, usually written without leading zeros as ...
    (comp.lang.ruby)
  • Re: FORMULA THAT CALCULATES HH:MM ON THIRD SHIFT(BETWEEN TWO DAYS)
    ... it's damn handy for figuring the difference between two times spanning ... The result has the same sign as divisor", ... If 11 is divided by 3, the remainder is 2. ... when both divisor and dividend are positive, 2. ...
    (microsoft.public.excel.misc)
  • 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)
  • Re: relationship between divisor and dividend in CRC codes
    ... between divisor and dividend in CRC codes ... Dividend and divisor are ... The remainder is the polynomial, ...
    (sci.crypt)
  • 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)