djones@megatest.UUCP (Dave Jones) (11/05/88)
As is Mr. Switzer, I too am absolutely certain that I know how / and % should be defined for negative dividends. Peculiar that we should not agree! :-) We agree on the MOD issue, but not on DIV. Or maybe not. First he says that IBM "did it right": > The PC/RT implements / to truncate to smaller values and i%n to always > return a value (0..n-1) for positive "n" But then he says, > Please, do not argue that integer -1/2 should be -1... But that is, or course, truncation toward a smaller value. (-1 is smaller than -0.5) Perhaps he will want to clarify. I have given the matter quite a bit of thought, ever since 1979, only months after having obtained an M.S. in math, when I was appalled to discover that the Pascal implementation at my new place of employment calculated -1 MOD 2 to be a negative number! Sheesh. I have since become resigned to the fact that, as the saying goes, "S**t happens." I am well aware of the fact that writing portable code means recognizing that most C compilers don't do it the way I would like it. But I still have strong opinions on the subject, as to what the most practical definitions of DIV and MOD are. It is no coincidence that they happen to be the theoretical definitions as well. I really find it quite astonishing that there is no consesus on this. It just looks so obvious. There is one way that is beautifully consistent. All the other ways have hair. In case you have not figured it out, my vote is along these lines: -1 % 2 == 1 -1 / 2 == -1 It is not a coincidence that these are the same numbers that you get from -1 & 1 == 1 -1 >> 1 == -1 provided that the >> operator does sign extension properly on signed integers. The operations of shifting and masking are intimately related to the arithmetic operations of counting. It has long been a source of delight and insight for me to take notice of the striking correspondences between, for example, addition of numbers and disjoint union of sets -- between masking bits and orthogonal projections in inner-product spaces -- between the algebra of continued fractions and the algebra of solving regular expressions -- to name just a few examples. I propose that if j > 0 then i/j be truncated downward -- by that I do not mean "toward zero" -- and that i%j is a number in the range 0..(j-1). We will return to the matter of i % (-j) and i/(-j) in a couple of exercises later on. (I'll give my answers in a spoiler at the very bottom.) Okay, now to reality. By what criteria would we choose these conventions? What are the practical considerations? In practice, what one wants is to be able to do calculations that do not require checking the signs of numbers. Also nice is to use shifts and and negation to optimize code when divisors and multipliers are positive multiples of two. This can be done by compilers or by knowledgable/devious programmers (depends on your point of view), provided that the conventions allow it unambiguously. You can even extend this to non- powers of two, by using shifts and adds for multiplication. But if your definition of DIV or MOD refers to the function ABS, as does the ANSII Pascal standard, it is pretty likely that checking the sign (or equivalently, calling ABS) will be required. The ABS function has a nasty non-linearity at zero. It is equivalent to say that "changing the sign of the dividend changes sign of the quotient, but not the magnitude," becuase there is an implicit "ABS" in the word "magnitude". Look at the graph of the the functions for DIV2 and MOD3, as I propose them, and you will see that they breeze through zero without taking any notice of it, whatsoever. DIV2 2 X----X . . . . . . . . 1 X----X . . . . . . . . |....|....|....|....X----X....|....|....|....| -4 -3 -2 -1 0 1 2 3 4 5 . . . . . . X----X -1 . . . . . . . . X----X -2 Notice that the X's form a neat stairstep with a slope of 1/2. Everywhere you look at it, it looks exactly the same. There is nothing peculiar happening about zero. The competing graph has one "step" that is three units in length: -1, 0, 1. All the other steps are two units long, just as one would expect of an integral graph with slope 1/2. MOD3 X 2 X X / . / / / . / / / . / / X 1 X X / . / / / . / / / ./ / X X X -4..-3..-2..-1..0...1...2...3...4...5 . . A nice, regular "ramp function". Again, there is nothing special about zero. The function looks the same everywhere. The competing graph "flips over" at zero. So if we use these definitions, we never have to check the sign of a dividend. Notice also that i == (i/j)*j + i%j holds for all i, positive and negative alike, when j>0. Same reason. Nothing out of the ordinary happens at zero. So how about those nutty negative divisors, eh? Let's call the property i == (i/j)*j + i%j the "Chinese Remainder" property, after the "Chinese Remainder Theorem" of number theory. EXERCISE 1. Propose a definitive graph demonstrating the truncation properties of the function DIV_minus_2. What alternatives did you consider? Why did you choose the one you did? How does it extend the principal of truncation? EXERCISE 2. Can the definition of MOD be extended to include negative divisors? If so, propose a definitive graph for MOD_minus_3. Does it, along with your definition from exercise, 1 have the Chinese Remainder property? Spoilers follow. Answer 1. To obtain a DIV_minus_n graph, flip the DIVn graph about the X-axis, so that the stairsteps slope down going left-to-right, rather than up. Sybolicly, define i/(-j) as -(i/j). Thus truncation of dividends is downward for positive divisors, and upward for negative divisors. They tend to "slip down the stairstep" quite consistently. Answer 2. Define i%(-j) as i%j. The Chinese Remainder property is preserved by these definitions.
ok@quintus.uucp (Richard A. O'Keefe) (11/08/88)
In article <972@goofy.megatest.UUCP> djones@megatest.UUCP (Dave Jones) writes:
This is an issue which has been thrashed out many times over the years.
Back issues of SigPlan Notices are a good place to look.
As Every Schoolboy Knows, there are at least three sensible definitions of
integer division/remainder, all of which agree which divisor and dividend
are positive. Common Lisp provides all three, and a fourth, also sensible.
Note that the Pascal standard does not define integer division and
remainder for non-positive divisors.sjs@jcricket.ctt.bellcore.com (Stan Switzer) (11/08/88)
In article <972@goofy.megatest.UUCP> djones@megatest.UUCP (Dave Jones) writes: > As is Mr. Switzer, I too am absolutely certain that I know > how / and % should be defined for negative dividends. Peculiar > that we should not agree! :-) We agree on the MOD issue, but > not on DIV. Or maybe not. First he says that IBM "did it right": > > Please, do not argue that integer -1/2 should be -1... > But that is, or course, truncation toward a smaller value. > (-1 is smaller than -0.5) > Perhaps he will want to clarify. OOPS! I goofed. I meant 0 not -1. I agree completely with your followup. One day while I was hacking Postscript it occurred to me to see if Adobe was clever enough to do it right. After all, grapgics is one of the areas where it really matters how / and % work. I am sad to say that Postscript does it wrong too. And here it is impossible to blame the hardware, as the cost of making it work right would be insignificant compared to the interpreter overhead. Stan Switzer sjs@ctt.bellcore.com
mcdonald@uxe.cso.uiuc.edu (11/09/88)
> -1 >> 1 giving -1
Odd. Lets see here. In binary 4 bits 1 == 0001b
0 == 0000b
-1 == 1110b
with zero filling shift -1 >> 1 == 0111b == 7
with sign filling shift -1 >> 1 == 1111b == -0
neither of which are == -1. Perhaps you are unfamiliar with this
relatively common method. On some machines -1 >> 1 == -1, but not
all machines - and not necessarily in ANSI C.
:-) :-) :-)djones@megatest.UUCP (Dave Jones) (11/09/88)
From article <643@quintus.UUCP>, by ok@quintus.uucp (Richard A. O'Keefe): > This is an issue which has been thrashed out many times over the years. No doubt. > Back issues of SigPlan Notices are a good place to look. Sigplan Notices is one of the most prolific sources of nonsense in all Computerdom. > > As Every Schoolboy Knows, there are at least three sensible definitions of > integer division/remainder, all of which agree which divisor and dividend > are positive. Being an [ex] schoolboy (and an [ex] associate prof of computer sci, who taught quite a few of the schoolboy's), I know about the competing definitions. But this exschoolboy finds all but one of them to be seriously flawed. Maybe I'll start a political movement to enforce my opinions. I'll call it a "Standards Committee". Yeah. I can see it now: "Just say NO to negative remainders and rounding toward zero."
djones@megatest.UUCP (Dave Jones) (11/09/88)
I've figured it out! This whole deficit thing is due to a misdefinition
of DIV and MOD.
Dig it.
Let's say there's a club with ten members. So the chairman comes in
and sez, "Okay, we owe 19 skillion dollars. Let's divide up the
debt, and pay it off."
Let's see now...
-1 skil.
---------
10) -19 skil.
We each owe one skillion dollars. And the _good_ news is that
*we*have*a*remainder!ok@quintus.uucp (Richard A. O'Keefe) (11/09/88)
In article <982@goofy.megatest.UUCP> djones@megatest.UUCP (Dave Jones) writes: >From article <643@quintus.UUCP>, by ok@quintus.uucp (Richard A. O'Keefe): >> Back issues of SigPlan Notices are a good place to look. >Sigplan Notices is one of the most prolific sources of nonsense in >all Computerdom. It doesn't *begin* to compare with comp.lang.c and other newsgroups (:-). There has been a *lot* of good stuff in Sigplan notices. Even some of the bad advice repays careful study to see _why_ it's bad. (I have learned a lot by saying "this is trash" and having someone ask me "why?") >> As Every Schoolboy Knows, there are at least three sensible definitions of >> integer division/remainder, all of which agree which divisor and dividend >> are positive. > >Being an [ex] schoolboy (and an [ex] associate prof of computer sci, who >taught quite a few of the schoolboy's (sic)), I know about the competing definitions. >But this exschoolboy finds all but one of them to be seriously flawed. I thought that when I capitalised "as every schoolboy knows" it could manage without a smiley. It's a well-known catchphrase, after all. BE MORE SPECIFIC. Say *why* you find all the other definitions "seriously flawed". (I can see how a definition can be useless, or awkward, or hard to understand, or difficult to implement in a programming language. But "flawed"?) By the way, whatever sensible definition of remainder one adopts, MOST_NEGATIVE_INTEGER % (-1) ought to be 0 (*anything* % (-1) should be 0). I can imagine implementations (e.g. on an IBM System/370) where the result might be an interrupt, and I know of one machine where the obvious translation would yield rubbish.
turner@sdti.UUCP (Prescott K. Turner) (11/10/88)
In article <643@quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) writes: >As Every Schoolboy Knows, there are at least three sensible definitions of >integer division/remainder, all of which agree which divisor and dividend >are positive. To call all three definitions "sensible" is inviting a war. To me the arguments Dave Jones presented make sense and the counterarguments do not. Actually, I do accept as a counterargument that most programming languages require the definition in which the quotient is truncated towards 0. But it's a shame that they went down that path. >Note that the Pascal standard does not define integer division and >remainder for non-positive divisors. The Pascal standard defines integer division for all divisors except 0. Standard Pascal's "mod" operator does not give the remainder from "div", even for positive divisors. The committee decided that while "div" had to be like all of the other languages, "mod" should be sensible. -- Prescott K. Turner, Jr. Software Development Technologies, Inc. 375 Dutton Rd., Sudbury, MA 01776 USA (508) 443-5779 UUCP:...genrad!mrst!sdti!turner
djones@megatest.UUCP (Dave Jones) (11/10/88)
From article <225800089@uxe.cso.uiuc.edu>, by mcdonald@uxe.cso.uiuc.edu: [ Description of one's complement arithmetic omited. } > Perhaps you are unfamiliar with this > relatively common method. On some machines -1 >> 1 == -1, but not > all machines - and not necessarily in ANSI C. > > > :-) :-) :-) Nah. I'm familiar with it. I just thought maybe if I closed my eyes, it would go away, along with all those communist-inspired negative remainders. Here. Have a smiley on me: :-) Dave J.
ok@quintus.uucp (Richard A. O'Keefe) (11/11/88)
In article <328@sdti.UUCP> turner@sdti.UUCP (0006-Prescott K. Turner, Jr.) writes: >In article <643@quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) writes: >>there are at least three sensible definitions of integer division/remainder, >>all of which agree which divisor and dividend are positive. >To call all three definitions "sensible" is inviting a war. Not at all: to agree that what someone else wants to do is sensible is usually a rather irenic thing to do. >To me the arguments Dave Jones presented make sense and the >counterarguments do not. I claim that each of the "floor", "trunc", and "ceil" definitions is sensible and useful. I have realistic (got to conceal those proprietary details) examples showing that each of them has uses. Please don't think that I ever suggested that any of the definitions other than your favourite should be used _instead_. I repeat that I have uses for all three. (And if there are other sensible definitions around, I can probably find uses for them too.) Dave Jones' arguments, and arguments I have received by E-mail from someone else, boil down to "_I_ haven't had the wit to see a use for it, so it's _baaaad_." >Actually, I do accept as a counterargument that most programming languages >require the definition in which the quotient is truncated towards 0. re >But it's a shame that they went down that path. Well, programming language designers mostly copy other languages. And way back there we find Fortran. And Fortran's designers either ruled the way they did because they were convinced that it was the most useful definition for Fortran's then envisaged applications, or because it suited the hardware well, and in the latter case the designers of the 704 or whatever presumably had what _they_ thought were good reasons for their choice. "Most programming languages require definition X" is some sort of argument for making definition X available, but it is _not_ a good argument for having X be the _only_ definition available. I don't give a Continental which particular definition a language designer choses to dignify with infix notation of its own, as long as when I have a use for one of the others it is available at least as efficiently as any- thing I could have coded myself. It is worth noting that on a lot of present-day UNIX boxes (68010s, 68020s, VAXen, many but not all RISCs) that integer division is so slow anyway that providing the hardware version (whatever that is) as "/" and "%" and supporting the other three definitions with a few conditional branches and other in-line code would be a perfectly reasonable thing to do.
dik@cwi.nl (Dik T. Winter) (11/12/88)
In article <664@quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) writes: > Well, programming language designers mostly copy other languages. And way > back there we find Fortran. And Fortran's designers either ruled the way > they did because they were convinced that it was the most useful definition > for Fortran's then envisaged applications, or because it suited the > hardware well, and in the latter case the designers of the 704 or whatever > presumably had what _they_ thought were good reasons for their choice. > I do not think that earlier versions of Fortran gave a precise specification of the semantics of DIV (earlier versions of Fortran were not precise enough anyway). And yes, truncating to zero matched machines best in those times, with 9's complement or sign-magnitude. -- dik t. winter, cwi, amsterdam, nederland INTERNET : dik@cwi.nl BITNET/EARN: dik@mcvax
djones@megatest.UUCP (Dave Jones) (11/12/88)
From article <664@quintus.UUCP>, by ok@quintus.uucp (Richard A. O'Keefe): > Dave Jones' arguments, and arguments I have received by E-mail from > someone else, boil down to > "_I_ haven't had the wit to see a use for it, so it's _baaaad_." > [ Author's note: The following has undergone four rounds of toning down. ] I suggest that the reader compare the two postings side by side and determine for themselves which speaks to mathematical utility and which makes unsubstantuated value claims. I also hope that in the future, Mr. O'Keefe will refrain from impugning the "wit" of fellow participants. Best regards, Dave J.
ok@quintus.uucp (Richard A. O'Keefe) (11/13/88)
In article <1003@goofy.megatest.UUCP> djones@megatest.UUCP (Dave Jones) writes: >From article <664@quintus.UUCP>, by ok@quintus.uucp (Richard A. O'Keefe): >> Dave Jones' arguments, and arguments I have received by E-mail from >> someone else, boil down to >> "_I_ haven't had the wit to see a use for it, so it's _baaaad_." >I suggest that the reader compare the two postings side by side >and determine for themselves which speaks to mathematical utility >and which makes unsubstantuated value claims. > >I also hope that in the future, Mr. O'Keefe will refrain from >impugning the "wit" of fellow participants. I did take the trouble to write several pages of mathematical-style justification, but decided that it would be a waste of bandwidth to post it. I will here show four examples: Given a block of memory N bytes long, and M objects to distribute it among, how much can each object have? Answer = floor(N/M) [definition 1] How much memory will not be allocated to any object? Answer = N-floor(N/M)*M = N "floor-mod" M Given that I need N bytes of memory, but that I have to ask for pages M bytes long, how many pages should I ask for? Answer = ceil(N/M) [definition 2] How much excess memory did I have to ask for? Answer = ceil(N/M)*M-N = -(N "ceil-mod" M) I have an axis ranging from 0 to N (sign unknown) which I want to divide into M "full" buckets with perhaps one "partial" bucket left over. What should the width of each full bucket be? Answer = trunc(N/M) = N div M [definition 3] How wide will the partial bucket be? Answer = N-trunc(N/M)*M = N mod M Which integer most accurately approximates N/M? Answer = round(N/M) [definition 4] What is the error in this approximation? Answer = N-round(M/M)*M = N "round-mod" M. I did not impugn anyone's wit at all, I was attacking the form of their arguments. No amount of showing that a particular definition is useful will show that other definitions are _not_ useful. Nor is it legitimate to claim that certain mathematical properties useful for _some_ application are essential for _all_ uses of division. All that the "speaking to mathematical utility" amounted to may fairly be paraphrased as "I find this definition useful and don't see how to use another, so another definition is bad". For example, one person claimed that an essential property of remainder was that X (mod N) classify all integers X into N equivalence classes. That is a very useful property indeed, and definition 3 lacks it. But there are applications (like the one shown) where that property is _not_ needed, and demanding that _the_ remainder operation have it really doesn't help. Honestly, friends, each of the four versions of integer division (and its corresponding remainder) shown above has its uses. I find myself wanting _each_ of them (though I have to admit that I want [4] less often than the others, but what of that? another programmer may have other needs). A compiler could generate more efficient code for them (whatever the hardware support for division) than I could. I don't care which of them gets the privilege of having its own infix notation and update operator, I just wish they were all available _somehow_. [It might be a good idea to reserve the infix notation for when it doesn't matter whether you're using floor or trunc, then the compiler could pick whichever was more efficient.]