Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Posting-Version: version B 2.10.2 9/18/84; site peora.UUCP Path: utzoo!watmath!clyde!burl!ulysses!bellcore!decvax!decwrl!pyramid!pesnta!peora!jer From: jer@peora.UUCP (J. Eric Roskos) Newsgroups: net.arch,net.lang,net.math Subject: Integer division: a winner declared Message-ID: <1970@peora.UUCP> Date: Thu, 13-Feb-86 09:11:12 EST Article-I.D.: peora.1970 Posted: Thu Feb 13 09:11:12 1986 Date-Received: Sat, 15-Feb-86 02:42:08 EST References: <11610@ucbvax.BERKELEY.EDU> <5100003@ccvaxa> <548@ism780c.UUCP> Followup-To: net.lang Organization: Concurrent Computer Corporation, Orlando, Fl Lines: 92 Keywords: semi-:-) re the winner, Knuth, Ada, C Xref: watmath net.arch:2517 net.lang:2104 net.math:2840 > The architectural issue is how should division round. Since posting a request for mathematical substantiation for the different approaches to integer division, I've been investigating this issue. (Not in net.arch, however, where nothing new seems to have been accomplished :-)). I got only one reply from a mathematician (and I wrote to him to ask him), and there were no further comments in net.arch other than continuing to go around and around, so I did some library research. First, regarding the line quoted above, because integer division gives an integer quotient and an integer remainder, there should not be any "rounding" involved. "Rounding" suggests that you are deriving an inexact result by forcing some of the digits of the result to zero in order to limit the number of significant figures. Integer division with a remainder is exact, on the other hand; it gives you exactly the result of the division, with no precision lost. Unfortunately, it appears that this is an issue of such disagreement because the "authorities" themselves disagree. Donald Knuth in _Fundamental_Algorithms_ defines a "mod" function x mod y = x - y * floor(x/y) if y!=0; x mod 0 = x and goes on to show (by dividing the RHS through by y) that if y > 0, then 0 <= x mod y < y if y < 0, then 0 >= x mod y > y He goes on to show that x mod y is the same as the remainder when x is divided by y. Then, finally, he states that "mod" is *not* the same as the meaning of the word "modulo" in number theory. So there you have a well known authority in computer science defining "mod" in the "unpopular" way. However, Knuth's definition runs up against an immutable obstacle: the Ada Programming Language's definition of the functions. Ada defines "rem" and division [and remember that Knuth said "rem"=="mod"] this way: Integer division and remainder are defined by the relation a = (a/b) * b + (a rem b) where (a rem b) has the sign of a and an absolute value less than the absolute value of b. Integer division satisfies the identity (-a)/b = -(a/b) = a/(-b) The result of the modulus operation is such that (a mod b) has the sign of b and an absolute value less than the absolute value of b; in addition this result must satisfy the relation a = b*n + (a mod b) for some [arbitrary] integer value of n. So there you have it. Ada defines "mod" as distinct from "rem", and defines division (and thus "mod") in the "intuitive" way, contradicting Knuth. So you have basically two apparently consistent definitions of integer division (internally consistent, different from each other of course); the arguments that have been advanced for one are "it's mathematically correct" (and, Knuth defines it that way), whereas the arguments for the other are that it's "intuitive" and that it's how it's defined in Ada, which unlike C, doesn't leave the definition open for debate. Furthermore, the C Reference Manual (Appendix A of K&R) clearly defines % to be the *remainder* function (thus arguments about the definition of "%" not being a normal mathematical function, but rather something like the word "glory", appear to be invalid), so when arguing about what "%" means, we're arguing Knuth's "mod" against Ada's "rem". The problem is, as far as the implementation of machines is concerned, Ada is likely to be the driving force for the forseeable future -- any company doing an implementation is faced with either complying with Ada, or suffering a performance penalty making the Ada compiler adapt the results of the division (in software) to suit the Ada definition. Due to the DoD's requirement for Ada, it seems likely that most manufacturers would choose the Ada definition for the divide operations in their instruction sets. Furthermore, there seems to be no evidence that either definition yields any inconsistencies in arithmetics built upon them; at least, none has been advanced here. And, finally, the C standard currently in existence simply leaves the question open altogether, contributing nothing either way. [Note that the Ada standard was open for public comment through many revisions, so if there was a strong opinion about division, it should have been (and probably was) voiced then.] Thus it looks like the "intuitive" Ada definition wins. -- UUCP: Ofc: jer@peora.UUCP Home: jer@jerpc.CCUR.UUCP CCUR DNS: peora, pesnta US Mail: MS 795; CONCURRENT Computer Corp. SDC; (A Perkin-Elmer Company) 2486 Sand Lake Road, Orlando, FL 32809-7642