lxa221@snulbug.mtview.ca.us (The Lab Rat) (06/29/91)
When designing an integer arithmetic package, some interesting
qustions arise. In particular, what does one do in the case of signed
division.
The case for positive / positive is easy - quotient is the truncated
integer result of the division, and the remainder is the difference
between the dividend and (quotient * divisor). Example follows:
11 / 4 = 2, with remainder 3
In the case of negative dividend and/or divisor, things get a lot
murkier.
One way to perform the calculation could be to take the absolute values
of the divisor and dividend, perform the division as if unsigned,
correct the sign of the quotient, and match the sign of the remainder
to the sign of the dividend. Examples follow:
-11 / 4 = -2, remainder -3
11 / -4 = -2, remainder 3
-11 / -4 = 2, remainder -3
Another way to perform the division is to divide the dividend by the
absolute value of the divisor, with result rounded down (to -infinity).
The sign of the result is then corrected, and the sign of the remainder
is always positive. Examples follow:
-11 / 4 = -3, remainder 1
11 / -4 = -2, remainder 3
-11 / -4 = 3, remainder 1
Yet another way is to have the remainder always have the same sign as
the divisor. Examples follow:
-11 / 4 = -3, remainder 1
11 / -4 = -3, remainder -1
-11 / -4 = 2, remainder -3
There are probably other variations, but I can't think of any that make
sense.
Which system do you prefer to use? Do you have any good reasons why?
Thanks in advance!
---
The Lab Rat
lxa221@snulbug.mtview.ca.uschappell@symcom (Glenn Chappell) (06/30/91)
In article <a491695e@snulbug.mtview.ca.us> lxa221@snulbug.mtview.ca.us (The Lab Rat) writes: >When designing an integer arithmetic package, some interesting >qustions arise. In particular, what does one do in the case of signed >division. >One way to perform the calculation could be to take the absolute values >of the divisor and dividend, perform the division as if unsigned, >correct the sign of the quotient, and match the sign of the remainder >to the sign of the dividend. Examples follow: > -11 / 4 = -2, remainder -3 > 11 / -4 = -2, remainder 3 > -11 / -4 = 2, remainder -3 > >Another way to perform the division is to divide the dividend by the >absolute value of the divisor, with result rounded down (to -infinity). >The sign of the result is then corrected, and the sign of the remainder >is always positive. Examples follow: > -11 / 4 = -3, remainder 1 > 11 / -4 = -2, remainder 3 > -11 / -4 = 3, remainder 1 > >Yet another way is to have the remainder always have the same sign as >the divisor. Examples follow: > -11 / 4 = -3, remainder 1 > 11 / -4 = -3, remainder -1 > -11 / -4 = 2, remainder -3 >Which system do you prefer to use? Do you have any good reasons why? I would prefer it if everyone would use the second system (remainder always non-negative), since it conforms most closely to the usual way mathematicians use modular arithmetic. On the other hand, many integer math systems are already in use, and sometimes a less-than-perfect standard is better than no standard at all. I just tested it out (in "C") on a Sun, an Iris and a Cray, and all three use the first method. If this is typical of most integer math systems (does anyone know if it is?), then that is the method I would recommend. GGC <><
darcy@druid.uucp (D'Arcy J.M. Cain) (06/30/91)
In article <1991Jun29.172953.20536@ux1.cso.uiuc.edu> Glenn Chappell writes: >In article <a491695e@snulbug.mtview.ca.us> (The Lab Rat) writes: >>qustions arise. In particular, what does one do in the case of signed >>division. >> -11 / 4 = -2, remainder -3 >> 11 / -4 = -2, remainder 3 >> -11 / -4 = 2, remainder -3 >> >> -11 / 4 = -3, remainder 1 >> 11 / -4 = -2, remainder 3 >> -11 / -4 = 3, remainder 1 >> >> -11 / 4 = -3, remainder 1 >> 11 / -4 = -3, remainder -1 >> -11 / -4 = 2, remainder -3 > >I would prefer it if everyone would use the second system (remainder >always non-negative), since it conforms most closely to the usual way >mathematicians use modular arithmetic. Here is the rationale I used when tackling this problem: |---------------------------------------------------------------------------| | What does div and ldiv do with negative numbers? Working backwards from | | the observation that when positive numbers are involved, the remainder | | added to the product of the quotient and denominator should give the | | numerator, I get the following examples: | | | | num denom quot rem | | === ===== ==== === | | +13 +5 +2 +3 | | -13 +5 -2 -3 | | +13 -5 -2 +3 | | -13 -5 +2 -3 | | | | if denom is 0 then I return quotient as 0 and remainder as the numerator. | | That seems to fit the model: (0 * 0) + rem == num. | |---------------------------------------------------------------------------| Furthermore I have since found the following in K&R2 pp205: "Otherwise, [second operand not 0] it is always true that (a/b)*b + a%b is equal to a." which is another way of saying the above. -- D'Arcy J.M. Cain (darcy@druid) | D'Arcy Cain Consulting | There's no government Toronto, Ontario, Canada | like no government! +1 416 424 2871 |
bks@lima.berkeley.edu (Bradley K. Sherman) (07/01/91)
Someone says: ||I would prefer it if everyone would use the second system (remainder ||always non-negative), since it conforms most closely to the usual way ||mathematicians use modular arithmetic. I don't know if Donald Knuth counts as a mathematician, but in a book called _Concrete Mathematics_ he and two other authors say approximately: m mod n is well-defined for any integer values, positive and negative. (m mod 0 is often defined to be m.) Start with the relation: m mod n = m - n * floor(m/n) This insight yields this table [f(m/n) is floor(m/n)]: m n f(m/n) n*f(m/n) m mod n 13 5 2 10 3 -13 5 -3 -15 2 13 -5 -3 15 -2 -13 -5 2 -10 -3 Note that the sign of the result of m mod n matches the sign of the modulus. And someone else states (quoting K&R): | "Otherwise, [second operand not 0] it is always true that | (a/b)*b + a%b is equal to a." So combining the wisdom of Knuth, Kernighan and Richie we complete the table (here defining % to be the modulus operator as defined above): m n f(m/n) n*f(m/n) m%n m/n (m/n)*n + m%n 13 5 2 10 3 2 13 -13 5 -3 -15 2 -3 -13 13 -5 -3 15 -2 -3 13 -13 -5 2 -10 -3 2 -13 And everything hangs together. Note that % is _not_ defined as above in either K&R C or the ANSI standard. Both the remainder and division operations are machine dependent for negative operands and undefined if n is 0. % is referred to as the "remainder operator" in the standard. --------------------------------- Hope this helps, Brad Sherman (bks@alfa.berkeley.edu)