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-7642