Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!unmvax!deimos.cis.ksu.edu!uxc!garcon!uicsrd.csrd.uiuc.edu!mcdaniel
From: mcdaniel@uicsrd.csrd.uiuc.edu (Tim McDaniel)
Newsgroups: comp.lang.c
Subject: Re: mp (Multiple Precision Integer Arithmetic Package)
Summary: With integers, you can't have everything
Keywords: integer division rounding
Message-ID: <1053@garcon.cso.uiuc.edu>
Date: 18 May 89 22:07:45 GMT
References: <640@stag.math.lsa.umich.edu>
Sender: news@garcon.cso.uiuc.edu
Reply-To: mcdaniel@uicsrd.csrd.uiuc.edu (Tim McDaniel)
Organization: Center for Supercomputing R&D (Cedar), U. of Ill.
Lines: 86
Distribution:

In article <640@stag.math.lsa.umich.edu> jeremy@math.lsa.umich.edu
(Jeremy Teitelbaum) writes:
>I recently discovered that our SUN 3.4 OS version of the MP library, which
>does exact integer arithmetic, has a bug in its division routines.
>In particular, dividing N by M, where M is negative, yields
>a remainder with incorrect sign.

Well, I just tried a test under "BSD 4.2 SUN version 3.5", which I
guess would be "SUN 3.5 OS", and got these results using MP:

 7/ 3  =>   2 remainder  1
-7/ 3  =>  -2 remainder -1
 7/-3  =>  -2 remainder -1
-7/-3  =>   2 remainder  1

Is this what you got, Jeremy?  If so, it's not clear to me that these
results are wrong, because the man page for MP says
    "Mdiv assigns the quotient and remainder, respectively, to its
    third and fourth arguments."
It does not say "modulus", it says "remainder".  Unfortunately, it
says "THE quotient" and "THE remainder", and there is no unique answer
for integers.  In algebra, "9/4" is 2.25 -- should we store it as 2 or
3?  How about "11/4" -- 2.75?  "10/4"?  How about "-7/3"?


A digression for a moment: originally, K&R C didn't say anything about
the results of / and %.  In pANS C, the result of "/" is not defined
very strictly (K&R, 2nd edition, page 205).  pANS C says that
1:         (A/B)*B + A%B == A
if B != 0.  If A and B are both positive, it is guaranteed that
2a:        0 <= A%B < B
Otherwise, it is guaranteed only that
2b:        abs(A%B) < abs(B)

If A and B are positive, there's a unique result: A/B is the truncated
integer portion of the quotient, and A%B is A mod B.  When I use
"mod", I mean the mathematical modulo, 0 <= A mod B < B where B > 0.

Otherwise, it's not so clear.  If B divides A evenly, the result is
obvious and unique.  However, if B does not divide A evenly, an
implementation can choose either of
        A%B =           A mod abs(B)
        A%B = -abs(B) + A mod abs(B)
since they both fit constraint 2b.  We just have to be sure to to fit
constraint 1 by defining "/" as
        A/B == (A - A%B) / B

For example, Q = 7/-3 and R = 7%-3 have two possible results: Q == -3
and R == -2; or else Q == -2 and R == 1.  These both fit the pANS C
constraints:
        -3*-3 - 2 == 7          -2*-3 + 1 == 7
        abs(-2) < abs(-3)       abs(1) < abs(-3)

Note that the MP library didn't get these answers on the SUN
(violating constraint 1):
        7/-3*-3 + 7%-3 = -2*-3 - 1 = 5 != 7

In other words, if you convert code from using "/" to using mdiv, your
answers will change.  So how could MP be so broken?  It's following
a different set of constraints.  If A > 0 and B > 0, MP uses

3:      -A/B == A/-B == -(A/B)
4:      -A%B == A%-B == -(A%B)
5:      sign(A%B) == sign(A/B)

(It's a simple implementation: strip off the signs, do the math, put
the same signs on / and %.)  *These* constraints may be violated at
will by pANS C implementations; some people would say that these
constraints are more intuitive and useful than constraint 1.

Basically, there are a whole lot of possible identities that would be
useful to have for integer division.  However, since it involves
integers, you can't satisfy all of them simultaneously.  pANS C made
one choice, and the implementors of the MP library made another.  In
some meta-sense, both are equally "right" or "wrong".

I think that the MP library should be made consistent with pANS C.

--
"6:20 O Timothy, keep that which is committed to thy trust, avoiding
profane and vain babblings, and oppositions of science falsely so
called: 6:21 Which some professing have erred concerning the faith."

Tim, the Bizarre and Oddly-Dressed Enchanter  |  mcdaniel@uicsrd.csrd.uiuc.edu
            {uunet,convex,pur-ee}!uiucuxc!uicsrd!mcdaniel
            mcdaniel%uicsrd@{uxc.cso.uiuc.edu,uiuc.csnet}