jeremy@math.lsa.umich.edu (Jeremy Teitelbaum) (05/18/89)
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. Has anyone either fixed these routines or written new ones which they would be willing to share? If so, please mail to me. Thanks, Jeremy -- Jeremy Teitelbaum Math Dept. U. of Michigan, Ann Arbor. teitelbaum@ub.cc.umich.edu OR jeremy@math.lsa.umich.edu
mcdaniel@uicsrd.csrd.uiuc.edu (Tim McDaniel) (05/19/89)
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}
banshee@ucscb.UCSC.EDU (Wailin Through The Nets) (06/26/89)
I am working on a 750 with 4.3 BSD. While playng about one
day, I found the mp multiple precision integer routines. I had long
put off actually writing something like this for myself.
My questions:
This looks like a hack job. It works, but was it the complete
after thought, or what?
Has anyone found problems with mp?
Has anyone written an arbitrary precision integer package for
themselves, who would care to share code?
Thanks in advance, please E-mail responses. I will post if interest is there.
---
John M Vinopal banshee@ucscb.UCSC.EDU
banshee@ucscf.UCSC.EDU
ucbvax!ucscc!ucsc{b,f}!banshee