jer@peora.UUCP (J. Eric Roskos) (02/13/86)
> 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-7642avg@diablo.ARPA (Allen VanGelder) (02/16/86)
Ada clearly has it right. Knuth agrees, but spells "rem" differently.
Ada examples:
5/ 3 = 1 5 rem 3 = 2 5 mod 3 = 2
(-5)/ 3 = -1 -5 rem 3 = -2 -5 mod 3 = 1
5/(-3) = -1 5 rem -3 = 2 5 mod -3 = -2
(-5)/(-3) = 1 -5 rem -3 = -2 -5 mod -3 = -1
(a mod b) is the answer to the question,
"What element in the field Z_b is congruent to a?"
For b > 0, Z_b = {0,1,2,...,b-1} by standard definition. For b < 0
I am unaware of any standard definition, but we might as well define
Z_b = {0,-1,-2,...,b+1}. Note that b+1 is the multiplicative identity.
I can't imagine implementing -5/3 = -2. If you really need this, I
would assume you also need the Ada "mod" on the same numbers. So do
m = a mod b;
q = (a - m) / b;
with very little overhead.gwyn@brl-smoke.ARPA (Doug Gwyn ) (02/16/86)
In article <1970@peora.UUCP> jer@peora.UUCP (J. Eric Roskos) writes: > > 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. What he actually said was, "In number theory, the abbreviation `mod' is used in a different but related sense; ..." and then introduces the word "modulo" for what a number theorist would call "mod". All he meant by this was that one can define "modulo" in terms of "mod": We say "x == y (modulo m)" iff (x - y) mod m = 0. Knuth also does not "show that mod is the same as remainder"; he says (for pedagogical reasons) "the quantity x - (x mod y) is an integral multiple of y; and so we may think of x mod y as *the remainder when x is divided by y*." And, indeed, that is a good way to think about the meaning of "x mod y", so long as the exact definition is used in technical work. > 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: ... Knuth said no such thing. He has defined "mod" as any decent mathematician would, which is NOT the same as "rem" or C's %. > So there you have it. Ada defines "mod" as distinct from "rem", and defines > division (and thus "mod") in the "intuitive" way, contradicting Knuth. Wrong. Ada's "rem" is like C's % with more specific semantics, and its "mod" is like everybody's "mod" (C doesn't have "mod"). I think where you went wrong was in not reading carefully enough. For x mod y, what does y < 0 mean? Nobody has been arguing about that case in this debate; the discussion has centered on what happens when x < 0. "x" != "y".
weemba@brahms.BERKELEY.EDU (Matthew P. Wiener) (02/19/86)
In article <1970@peora.UUCP> jer@peora.UUCP (J. Eric Roskos) writes: >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. You may be interested that many of the largest defense companies/contractors consider Ada to be a complete joke and have no intention of making it available unless their programmers start screaming and begging for it. This includes Los Alamos National Labs, Lawrence Livermore Labs, the National Security Agency, NASA and Lockheed. Considering that all the biggies run UNIX on Cray-2s and are--if they are intelligent--moving towards workstations that will talk with the Cray-2s quite easily (read UNIX workstations), it looks like that a large portion of DoD programming will move towards C, not Ada. Incidentally, LLL and NSA both have their own private languages. >[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.] Yes and no. Several companies were asked to make suggestions and they laughed at the Ada idea even then. I for one do not care what the Ada standard is, and couldn't imagine why I would have wanted to contribute any strong feelings about language design to a language I couldn't care about. Besides, I wouldn't be surprised if they chose the boneheaded way of doing integer division for idiotic reasons anyway. >Thus it looks like the "intuitive" Ada definition wins. Hardy har har. [And to net.lang.ada readers: sorry for picking on Ada, but I realize many of you have no choice in the matter anyway.] ucbvax!brahms!weemba Matthew P Wiener/UCB Math Dept/Berkeley CA 94720
ladkin@kestrel.ARPA (Peter Ladkin) (02/21/86)
In article <11923@ucbvax.BERKELEY.EDU>, weemba@brahms.BERKELEY.EDU (Matthew P. Wiener) writes: > You may be interested that many of the largest defense companies/contractors > consider Ada to be a complete joke and have no intention of making it > available > unless their programmers start screaming and begging for it. This includes > Los Alamos National Labs, Lawrence Livermore Labs, > the National Security Agency, > NASA and Lockheed. Considering ADA to be flawed - not in one of your cases. Having no intention of making it available, again false in two of your quoted list. From first hand knowledge. There is enormous pressure to write in ADA for DOD work. DOE? No idea. Peter Ladkin
ladkin@kestrel.ARPA (Peter Ladkin) (02/21/86)
In article <5030@kestrel.ARPA>, ladkin@kestrel.ARPA (Peter Ladkin) writes: > Considering ADA to be flawed - not in one of your cases. I meant - at least one of the organisations quoted doesn't consider ADA to be flawed. > Having no intention of making it available, again false in two of > your quoted list. > From first hand knowledge. To be read similarly. Sorry for the confusion. Peter Ladkin
gsmith@brahms.BERKELEY.EDU (Gene Ward Smith) (02/21/86)
In article <127@diablo.ARPA> avg@diablo.UUCP (Allen VanGelder) writes: >Ada clearly has it right. Knuth agrees, but spells "rem" differently. >Ada examples: > 5/ 3 = 1 5 rem 3 = 2 5 mod 3 = 2 > (-5)/ 3 = -1 -5 rem 3 = -2 -5 mod 3 = 1 > 5/(-3) = -1 5 rem -3 = 2 5 mod -3 = -2 > (-5)/(-3) = 1 -5 rem -3 = -2 -5 mod -3 = -1 > It looks like I need to unsay most of the bad things I said about Ada. Sorry about that, Adaphiles, but at first I thought J. Eric Roskos was saying Ada had two mod-type functions, but later decided he was saying it had only one (since he said Knuth's was different). I hope foot-in-mouth disease isn't catching. >For b > 0, Z_b = {0,1,2,...,b-1} by standard definition. For b < 0 >I am unaware of any standard definition, but we might as well define >Z_b = {0,-1,-2,...,b+1}. Note that b+1 is the multiplicative identity. There is a standard remainder defintion for negative b, but it really doesn't matter; the Knuth/Ada definition is just fine. >I can't imagine implementing -5/3 = -2. If you really need this, I Just today I needed this. It took an extra (C language) function definition. I have *never in my life*, to the best of my recollection, wanted or needed -5/2 = -1. It's not as important as mod by any means, so I will just leave you with this thought: it's still wrong, but the situation is improving. Maybe the next "language to end all languages" after Ada will finally get it right. ucbvax!brahms!gsmith Gene Ward Smith/UCB Math Dept/Berkeley CA 94720 ucbvax!weyl!gsmith "Dumb problem. DUMB!!!"
franka@mmintl.UUCP (Frank Adams) (03/05/86)
In article <127@diablo.ARPA> avg@diablo.UUCP (Allen VanGelder) writes: >Ada clearly has it right. Knuth agrees, but spells "rem" differently. >Ada examples: > 5/ 3 = 1 5 rem 3 = 2 5 mod 3 = 2 > (-5)/ 3 = -1 -5 rem 3 = -2 -5 mod 3 = 1 > 5/(-3) = -1 5 rem -3 = 2 5 mod -3 = -2 > (-5)/(-3) = 1 -5 rem -3 = -2 -5 mod -3 = -1 > >(a mod b) is the answer to the question, > "What element in the field Z_b is congruent to a?" > >I can't imagine implementing -5/3 = -2. If you really need this, I >would assume you also need the Ada "mod" on the same numbers. So do > m = a mod b; > q = (a - m) / b; >with very little overhead. A step in the right direction, but it still doesn't divide and round. ALGOL does it this way, but it hasn't been heard from since. (By the way, one advantage of -5/3 = -2 is that it makes it easier to do a divide and round if one is not available already. One can write: (a + b / 2) / b instead of if (a > 0) then (a + b / 2) / b else (a - b / 2) / b or similar results from mucking around with some variant of the signum function.) Frank Adams ihnp4!philabs!pwa-b!mmintl!franka Multimate International 52 Oakland Ave North E. Hartford, CT 06108