flee@shire.cs.psu.edu (Felix Lee) (02/19/90)
Kent Paul Dolan <xanthian@ads.com> wrote: >Yep. It is utterly amazing how many modulus inplementations exist >where (-1) mod m isn't m-1. There are three things that most people would like: quotient = -5 div 3 = -(5 div 3) = -1 remainder = -5 mod 3 = (-5 + 6) mod 3 = 1 3*quotient + remainder = -5 Unfortunately, they're mutually contradictory. You must choose one of them to violate. Someone will be unhappy with your decision. -- Felix Lee flee@shire.cs.psu.edu *!psuvax1!flee
xanthian@saturn.ADS.COM (Metafont Consultant Account) (02/19/90)
In article <E1wt*4@cs.psu.edu> flee@shire.cs.psu.edu (Felix Lee) writes: >Kent Paul Dolan <xanthian@ads.com> wrote: >>Yep. It is utterly amazing how many modulus inplementations exist >>where (-1) mod m isn't m-1. > >There are three things that most people would like: > quotient = -5 div 3 = -(5 div 3) = -1 > remainder = -5 mod 3 = (-5 + 6) mod 3 = 1 > 3*quotient + remainder = -5 > >Unfortunately, they're mutually contradictory. You must choose one of >them to violate. Someone will be unhappy with your decision. Absolutely! One may either choose to truncate integer divisions' quotients towards minus infinity, a very unnatural feeling operation, to dissociate the modulus function from the remainder of integer division, or to violate the grade school concept of reconstructing the dividend simply from the divisor, the quotient, and the remainder. I see the idea of a modulus function that doesn't change if the axis is shifted left or right by the mod base, rather than one that suffers an ugly reflection at the origin, as inherently beautiful, in the math sense. It is also inherently more useful, in the graphics programming sense. Among your three items, the one that does not arouse any particular religious fervor at thoughts of its loss is the second; I see no particular reason to identify the mod function with the remainder of integer division; they are very comfortable as independent concepts, and, I think, were identified with one another on computers by the historical accident that the remainder fell out simply from the most common implementation of shift and subtract logic for division, which leaves the remainder in one half of the dividend double register while the quotient is built in the other half, and the by arithmetical coincidence that they are identical when all the operands are positive. -- xanthian@ads.com xanthian@well.sf.ca.us (Kent Paul Dolan) Again, my opinions, not the account furnishers'.
aipdc@castle.ed.ac.uk (Paul D. Crowley) (02/20/90)
In article <E1wt*4@cs.psu.edu> flee@shire.cs.psu.edu (Felix Lee) writes: >There are three things that most people would like: > quotient = -5 div 3 = -(5 div 3) = -1 > remainder = -5 mod 3 = (-5 + 6) mod 3 = 1 > 3*quotient + remainder = -5 > >Unfortunately, they're mutually contradictory. You must choose one of >them to violate. Someone will be unhappy with your decision. I'd _hate_ a computer that obeyed the first of these. To me, -5 div 3 is -2. -5 div 3 = int(-5/3) = int(-1.666) = -2 Then again, I think month and day numbers should start at 0. -- \/ o\ "I say we grease him right away. No offense." - Aliens. /\__/ Paul D Crowley aipdc@uk.ac.ed.castle
desnoyer@apple.com (Peter Desnoyers) (02/20/90)
In article <10946@saturn.ADS.COM> xanthian@saturn.ADS.COM (Metafont Consultant Account) writes: > I see the idea of a modulus function that doesn't change if the axis > is shifted left or right by the mod base, rather than one that suffers > an ugly reflection at the origin, as inherently beautiful, in the math > sense. It is also inherently more useful, in the graphics programming > sense. It is more than just pretty. The integers mod M has M elements, usually represented as 0..M-1. A modulo operator that results in {integers mod M} having 2M-1 elements is either incorrectly named or incorrectly implemented. Peter Desnoyers Apple ATG desnoyer@apple.com
xanthian@saturn.ADS.COM (Metafont Consultant Account) (02/20/90)
In article <6790@internal.Apple.COM> desnoyer@apple.com (Peter Desnoyers) writes: >In article <10946@saturn.ADS.COM> xanthian@saturn.ADS.COM (Metafont >Consultant Account) writes: >> I see the idea of a modulus function that doesn't change if the axis >> is shifted left or right by the mod base, rather than one that suffers >> an ugly reflection at the origin, as inherently beautiful, in the math >> sense. It is also inherently more useful, in the graphics programming >> sense. > >It is more than just pretty. The integers mod M has M elements, usually >represented as 0..M-1. A modulo operator that results in {integers mod M} >having 2M-1 elements is either incorrectly named or incorrectly implemented. [I knew I couldn't get away without drawing a picture; my words have never been that clear...] Peter, It isn't the case, for the implementions I have seen that I considered flawed, that the x mod 4 mapping looks like: 3 3 2 2 1 1 0 0 0 0 0 -1 -1 -2 -2 -3 -3 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 but instead it looks like: 3 3 3 3 2 2 2 2 1 1 1 1 0 0 0 0 0 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 when I need it to look like: 3 3 3 3 2 2 2 2 1 1 1 1 0 0 0 0 0 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 which latter is invarient under translations of the axis by multiples of 4, the modulus base, a very desirable property for mapping a rectangle onto a torus. -- xanthian@ads.com xanthian@well.sf.ca.us (Kent Paul Dolan) Again, my opinions, not the account furnishers'.
chl@cs.man.ac.uk (Charles Lindsey) (02/20/90)
xanthian@saturn.ADS.COM (Metafont Consultant Account) writes: >In article <E1wt*4@cs.psu.edu> flee@shire.cs.psu.edu (Felix Lee) writes: >>There are three things that most people would like: >> quotient = -5 div 3 = -(5 div 3) = -1 >> remainder = -5 mod 3 = (-5 + 6) mod 3 = 1 >> 3*quotient + remainder = -5 >Absolutely! One may either choose to truncate integer divisions' >quotients towards minus infinity, a very unnatural feeling operation, On the contrary, one must start by realising that it is the usual definition of integer division in programming languages that is WRONG, and is the real root of the problem. Also, aipdc@castle.ed.ac.uk (Paul D. Crowley) writes: >I'd _hate_ a computer that obeyed the first of these. To me, -5 div 3 is >-2. -5 div 3 = int(-5/3) = int(-1.666) = -2 So I am not alone in my view. Here is a nice example taken from an article by Lambert Meertens in ALGOL Bulletin #39. I have transcribed it into ADA, TYPE intarray IS ARRAY(integer RANGE <>) OF integer; PROCEDURE mid(a: intarray) RETURN integer IS -- the "middle" value of the array a BEGIN RETURN a( (a'first + a'last)/2 ) END; PROCEDURE at(a: intarray, newbound: integer) RETURN intarray IS -- a copy of a, s.t. a'first = newbound DECLARE newa: ARRAY(newbound .. a'last-a'first+newbound) OF integer := a; BEGIN RETURN newa; END; somearray: intarray(1..4) := (1,2,3,4); -- so mid(somearray) gives '2' FOR i IN REVERSE -4..+4 LOOP put(mid(at(somearray, i))); END LOOP; -- prints "2 2 2 2 2 2 3 3 3" How did we get into this mess? Once upon a time (c. 1950) some machines (mostly in Europe) did integer division "right" and some (mostly in America) did it "wrong". The difference was essentially between machines built by mathematicians and machines built by engineers (note that, if you carefully follow a textbook on Algebra, you will see how mathematicians treat it). Not surprisingly, the "wrong" answer got built into FORTRAN. The last chance to get it right was in ALGOL 60, when the Europeans were only interested in REAL division. The Americans wanted a separate operator for INTEGER division, so the Europeans asked the Americans to provide a definition for it. I tried in 1968 to get it right in ALGOL 68, but all I achieved was to get the MOD correct (and not the same as remainder). I tried to persuade ADA to get it right, but all I achieved was to get a REM operator in addition to MOD. I tried to get the PASCAL standardizers to get it right, but although they admitted the merit of my case, they got cold feet because, in the meantime, all hardware was now being built the way languages were now defining it. So here is my plea to our descendants who may someday colonize a planet in Alpha Centauri. When you get there, and set up new standards to be applied in that corner of the galaxy, please remember that the people on Terra got integer division WRONG, and do not let the mistake propagate any further.
djones@megatest.UUCP (Dave Jones) (02/21/90)
In article <E1wt*4@cs.psu.edu> flee@shire.cs.psu.edu (Felix Lee) writes: > There are three things that most people would like: > quotient = -5 div 3 = -(5 div 3) = -1 > remainder = -5 mod 3 = (-5 + 6) mod 3 = 1 > 3*quotient + remainder = -5 > >Unfortunately, they're mutually contradictory. You must choose one of >them to violate. Someone will be unhappy with your decision. > I differ. The first of these, -5 div 3 == -1 is wrong. -5 div 3 is -2. Fix that, and everything is cool. Draw both versions of the 'div-3' graph, and you'll see why this makes sense. The -5 div 3 == -1 graph has an ughliness in it around zero that translates into an extra test in algorithms.
flee@shire.cs.psu.edu (Felix Lee) (02/21/90)
Dave Jones <djones@megatest.UUCP> wrote:
>I differ. The first of these, -5 div 3 == -1 is wrong.
The contrary view is that abs(a/b) != abs(-a/b) is strange. It
depends on what you're doing. I have no problems with either stance.
--
Felix Lee flee@shire.cs.psu.edu *!psuvax1!fleedjones@megatest.UUCP (Dave Jones) (02/22/90)
From article <Er$cfg@cs.psu.edu>, by flee@shire.cs.psu.edu (Felix Lee): > Dave Jones <djones@megatest.UUCP> wrote: >>I differ. The first of these, -5 div 3 == -1 is wrong. > > The contrary view is that abs(a/b) != abs(-a/b) is strange. It > depends on what you're doing. I have no problems with either stance. You've hit the nail on the head. The contrary 'view' is only that: a view. Many beautiful and consistent mathematical concepts seem 'strange' when understood only incompletely. If you didn't sell it back to the bookstore for tuition, get your old group-theory textbook out of the garage and read the first couple of chapters. Then tell me what 'abs' has to do with the price of tea in China. Several others have told me that it 'depends on what you're doing', but so far nobody has come up with an example where the contrary view is a win.
mph@lion.inmos.co.uk (Mike Harrison) (02/22/90)
In article <10940@saturn.ADS.COM> xanthian@saturn.ADS.COM (Metafont Consultant Account) writes: >Yep. It is utterly amazing how many modulus inplementations exist >where (-1) mod m isn't m-1. In "Ada Language and Methodology", by David Watt, Brian Wichmann and William Findlay, (pub. Prentice-Hall International). [quoted without permission - sorry Brian!] The following definitions are given for integer divide, rem and mod operations: "The 'division operators' /, rem and mod are fairly straightforward when no negative operands are involved. ... The operator / always yields a result truncated, if necessary, towards zero. In general: (-I)/J = -(I/J) = I/(-J) The operators rem and mod always yield results smaller in magnitude than their right operands. They are interchangeable unless their operands have opposite signs. The difference is that rem always takes the sign from its left operand, whereas mod always takes its sign from its right operand. They are defined by: I rem J = I - (I/J) * J I mod J = I - J * n for some integer n such that abs(I mod J) < abs J and such that I mod J has the same sign as J ..." Applying this to your example: (-1) mod m, and letting m = (say) 3, gives: (-1) mod 4 = (-1) - 4 * n, which for n = -1 yields = (-1) - 4 * (-1) = (-1) - (-4) = (-1 + 4) = 3 = m - 1 which appears to meet your case. Mike, Michael P. Harrison - Software Group - Inmos Ltd. UK. ----------------------------------------------------------- UK : mph@inmos.co.uk with STANDARD_DISCLAIMERS; US : mph@inmos.com use STANDARD_DISCLAIMERS;
firth@sei.cmu.edu (Robert Firth) (02/22/90)
In article <12099@goofy.megatest.UUCP> djones@megatest.UUCP (Dave Jones) writes: [the 'contrary' view is that integer division should truncate towards zero] >Several others have told me that it 'depends on what you're doing', but so >far nobody has come up with an example where the contrary view is a win. That surprises me, since there is a standard example. You have a picture drawn on a Cartesian plane, symmetrical about the origin. You need to scale this picture by some factor - for example, you want to reduce its size by 50% linear. The obvious coordinate transformation is (x',y') = (x/2,y/2). If division truncates towards zero, fine; otherwise, the scaled picture is no longer symmetrical (and typically the viewer can perceive the asymmetry).
flee@shire.cs.psu.edu (Felix Lee) (02/22/90)
On the issue of -a div b = -(a div b) [1] versus a div b = floor(a/b) [2] I do prefer [2] over [1]. The reason I'm mostly tolerant of either case is because I remember writing expressions like abs(a) div b * sgn(a) to simulate [1], but I can't remember the context; it could probably have been better done differently anyway. -- Felix Lee flee@shire.cs.psu.edu *!psuvax1!flee
bs@linus.UUCP (Robert D. Silverman) (02/22/90)
In article <12099@goofy.megatest.UUCP> djones@megatest.UUCP (Dave Jones) writes:
:From article <Er$cfg@cs.psu.edu>, by flee@shire.cs.psu.edu (Felix Lee):
:> Dave Jones <djones@megatest.UUCP> wrote:
:>>I differ. The first of these, -5 div 3 == -1 is wrong.
:>
:> The contrary view is that abs(a/b) != abs(-a/b) is strange. It
:> depends on what you're doing. I have no problems with either stance.
:
Sigh. Don't people learn about functions in school anymore?
The mapping 5 div 3 -- > 1 is a function. It is the floor function
of the quotient. Why on earth SHOULD one expect that for some function f
abs(f(a,b)) = abs(f(-a,b))?????
It would be the same as expecting f(a,b) = -f(-a,b). This simply is not
true of all functions.
It is not strange. It is simply people who know very little mathematics
shooting their mouth off.
--
Bob Silverman
#include <std.disclaimer>
Internet: bs@linus.mitre.org; UUCP: {decvax,philabs}!linus!bs
Mitre Corporation, Bedford, MA 01730postpischil@alien.enet.dec.com (Always mount a scratch monkey.) (02/22/90)
In article <6197@bd.sei.cmu.edu>, firth@sei.cmu.edu (Robert Firth) writes... > The obvious coordinate transformation is (x',y') = (x/2,y/2). If > division truncates towards zero, fine; otherwise, the scaled picture > is no longer symmetrical (and typically the viewer can perceive > the asymmetry). I'm not sure why you are doing geometry with integers, but it's a real shame that the drawing, which consisted of two identical components, one centered about the origin and one off to the side a bit, no longer consists of two identical components. The difference between the two divisions is that one preserves reflectional symmetry and one preserves translational symmetry. Can you make an argument that one symmetry is more aesthetic than another? Neither form of division has a greater claim to purity or grace. Each should be used when appropriate. Both should be available in a general programming environment. -- edp (Eric Postpischil) "Always mount a scratch monkey." postpischil@alien.enet.dec.com
firth@sei.cmu.edu (Robert Firth) (02/23/90)
In article <8574@shlump.nac.dec.com> postpischil@alien.enet.dec.com (Always mount a scratch monkey.) writes: >The difference between the two divisions is that one preserves reflectional >symmetry and one preserves translational symmetry. Can you make an argument >that one symmetry is more aesthetic than another? I agree completely. That's why, in my opinion, you can't call one semantics 'right' and the other 'wrong'.
peter@ficc.uu.net (Peter da Silva) (02/23/90)
I've got a secret for you. Engineers like a continuous div/rem as well. The
folks who got it wrong were the physiscists, who never deal with integers
nohow, and crystallography weenies, ditto.
--
_--_|\ Peter da Silva. +1 713 274 5180. <peter@ficc.uu.net>.
/ \
\_.--._/ Xenix Support -- it's not just a job, it's an adventure!
v "Have you hugged your wolf today?" `-_-'djones@megatest.UUCP (Dave Jones) (02/23/90)
From article <981@m1.cs.man.ac.uk>, by chl@cs.man.ac.uk (Charles Lindsey): ... > > I tried to get the PASCAL standardizers to get it right, but although they > admitted the merit of my case, they got cold feet because, in the meantime, > all hardware was now being built the way languages were now defining it. > I too haggled with the Pascal standardizers, but I was under the impression that we WON. I just now went back to an old draft copy, and to _Standard_Pascal_ by Doug Cooper, and I discover that dammit, they only did MOD right, not DIV. @#$%^&!!! MOD is stipulated to be correct, but -- get this! -- DIV is stipulated to be wrong! You can't even do it right if you want to. Not unless you want to (shudder) violate the standard. Oooooo. They say, abs(i) - abs(j) < abs((i div j)*j) <= abs(i) There's them damnable abses again. What the **** has abs got to do with anything? Abses in definitions translate into tests for > 0 at runtime. Who needs the agravation? And then they confess, 'NOTE: Only for i >=0 and j > 0 does the relation (i div j) * h + i mod j = i hold.' *** Just now I did a little experimenting. On Sun-3, release 4.3. In both C and Pascal, division is correct, but mod is wrong. In other words, they have it exactly backwards from the ANSI Pascal Standard. Not right mathematically. Not right according to the standard. You got to wonder, how come?
flee@shire.cs.psu.edu (Felix Lee) (02/23/90)
Bob Silverman <bs@linus.mitre.org> wrote: >The mapping 5 div 3 -- > 1 is a function. It is the floor function >of the quotient. Why on earth SHOULD one expect that for some function f >abs(f(a,b)) = abs(f(-a,b))????? >It would be the same as expecting f(a,b) = -f(-a,b). This simply is not >true of all functions. I find this statement a little strange. Consider: The mapping 2 plus 3 -> 5 is a function. Why on earth SHOULD one expect that for some function f, f(a,b) = f(b,a)?? I'm afraid my statement about "div" was a little unclear. The issue is whether integer division is the floor of the quotient or not. -- Felix Lee flee@shire.cs.psu.edu *!psuvax1!flee
djones@megatest.UUCP (Dave Jones) (02/23/90)
From article <6197@bd.sei.cmu.edu>, by firth@sei.cmu.edu (Robert Firth): > In article <12099@goofy.megatest.UUCP> djones@megatest.UUCP (Dave Jones) writes: > > [the 'contrary' view is that integer division should truncate towards zero] > >>Several others have told me that it 'depends on what you're doing', but so >>far nobody has come up with an example where the contrary view is a win. > > That surprises me, since there is a standard example. Several people posted candidates, but each was shot down in turn. > You have a > picture drawn on a Cartesian plane, symmetrical about the origin. > You need to scale this picture by some factor - for example, you > want to reduce its size by 50% linear. > > The obvious coordinate transformation is (x',y') = (x/2,y/2). If > division truncates towards zero, fine; otherwise, the scaled picture > is no longer symmetrical (and typically the viewer can perceive > the asymmetry). I presume that since we are using integer division, the image is some kind of a bitmap, right? This has the ring of truth to it, although it seems somewhat contrived. (How often do you have a *symetrical* digitized picture laying about that you want to scale by 1/2?) It has the ring of truth, because the problem with the 'contrary' view is precicely that it's graph is symetrical about the y-axix, which makes translating it sideways impossible. And here we have a picture which is symetrical about the y-axis. If there is a case where the 'contrary view' prevails, it will be something like this. But I'm still not convinced. A picture undergoing this transformatinon will be 'pinched' along both the x and y-axes, whether it is symetrical or not. This may or may not be obvious, depending on the picture. But I would think that the 'creases' down the middle would often be noticeable, and would be a direct consequence of the nastiness around zero. (It may not matter, but is this really a valid way to scale down a bitmap image? Seems bogus to me, because any two-by-two rectangle that has even one dot in it will get transformed into a dot.)
bs@linus.UUCP (Robert D. Silverman) (02/23/90)
In article <E5$4$m@cs.psu.edu> flee@shire.cs.psu.edu (Felix Lee) writes: >Bob Silverman <bs@linus.mitre.org> wrote: >>The mapping 5 div 3 -- > 1 is a function. It is the floor function >>of the quotient. Why on earth SHOULD one expect that for some function f >>abs(f(a,b)) = abs(f(-a,b))????? >>It would be the same as expecting f(a,b) = -f(-a,b). This simply is not >>true of all functions. > >I find this statement a little strange. Consider: > The mapping 2 plus 3 -> 5 is a function. Why on earth SHOULD one > expect that for some function f, f(a,b) = f(b,a)?? Huh? This statement has absolutely nothing to do with what I said. Oh, for blanks sake. When are you CS weenies going to learn some math? I said for *some* function f. Not for *all* functions f, and this clown then picks out an example of a linear function for which f(a,b) = f(b,a), which has absolutely nothing to do with the issue at hand. It works for this particular function, but won't work for all. Will everyone PLEASE go look up the difference between a ring and a field? The integers are not a field and division is not well defined for every pair of integers. Choosing a,b \in Z --> a/b = floor[a/b] is the best, mathematically consistent way to handle integer division. This means -5/3 = -2. This is absolutely necessary. The integers form a Euclidean domain. We therefore MUST have 3*(-5/3) + (-5 mod 3) = -5. -- Bob Silverman #include <std.disclaimer> Internet: bs@linus.mitre.org; UUCP: {decvax,philabs}!linus!bs Mitre Corporation, Bedford, MA 01730
jgk@osc.COM (Joe Keane) (02/23/90)
The main problem is that you're trying to assign an operator to one of many possible different functions. I have my favorites, but someone will always want a different one from what you pick. Let's say we just want to convert a floating point number to an integer. There are a number of rounding possibilities, up, down, toward zero, away from zero, and to nearest. And if you're rounding to nearest, what do you do if you're halfway in between? Again you can go up, down, toward zero, away from zero, or my favorite, pick the even one. Just when you think you've got it down, some weird case shows up; for example, should 1 mod -2 be 1 or -1? I won't even get into 0 vs. -0 or infinities and not-a-numbers. Good thing IEEE and ANSI define the way these things should work. Trouble is, they don't always agree with each other. Even in the BASIC on my HP-71 there are four functions to convert a floating point number to an integer, and three functions to take remainders in different ways. I just looked in the Unix manual section RINT(3M) and there are seven functions provided to convert a floating point number to an integer. If you think this is all kid's stuff, try getting the branch cuts right in your complex inverse hyperbolic functions. Fun stuff.
cet1@cl.cam.ac.uk (C.E. Thompson) (02/23/90)
In article <12115@goofy.megatest.UUCP> djones@megatest.UUCP (Dave Jones) writes: >From article <981@m1.cs.man.ac.uk>, by chl@cs.man.ac.uk (Charles Lindsey): >... >> >> I tried to get the PASCAL standardizers to get it right, but although they >> admitted the merit of my case, they got cold feet because, in the meantime, >> all hardware was now being built the way languages were now defining it. >> > >I too haggled with the Pascal standardizers, but I was under the impression >that we WON. I just now went back to an old draft copy, and to >_Standard_Pascal_ by Doug Cooper, and I discover that dammit, they >only did MOD right, not DIV. > >@#$%^&!!! > >MOD is stipulated to be correct, but -- get this! -- DIV is stipulated >to be wrong! You can't even do it right if you want to. Not unless you >want to (shudder) violate the standard. Oooooo. They say, > > abs(i) - abs(j) < abs((i div j)*j) <= abs(i) > >There's them damnable abses again. What the **** has abs got to do with >anything? Abses in definitions translate into tests for > 0 at runtime. >Who needs the agravation? > >And then they confess, 'NOTE: Only for i >=0 and j > 0 does the relation >(i div j) * j + i mod j = i hold.' (Slight correction to quotation made there) Why the big suprise? I thought that this <%rudeword> in Pascal was NOTORIOUS. And you have had eight years to find out about it :-) If I have it right, the critical change happened between the 3rd and 5th working drafts (i.e. between Oct 1978 and Nov 1979). In the 3rd, i div j was defined for i>=0, j>0 to be what everyone would expect; to be an error if j=0, and to be 'implementation defined' in other cases; however i mod j was defined to be i - j*(i div j) (by implication, for all i,j). By the 5th these definitions, which at least allow the 'right' implementation, had been replaced by the mess that made it into the 1982 ISO standard. > > *** > >Just now I did a little experimenting. On Sun-3, release 4.3. In both C >and Pascal, division is correct, but mod is wrong. > >In other words, they have it exactly backwards from the ANSI Pascal >Standard. Not right mathematically. Not right according to the standard. >You got to wonder, how come? The *ANSI* standard... the fact that the ANSI standard is not the same as the ISO standard is another <%rudeword>. Luckily, it doesn't affect the div/mod discussion. Chris Thompson JANET: cet1@uk.ac.cam.phx Internet: cet1%phx.cam.ac.uk@nsfnet-relay.ac.uk
callahan@mordor.endor.cs.psu.edu (Paul B. Callahan) (02/24/90)
In article <98717@linus.UUCP> bs@linus.UUCP (Robert D. Silverman) writes: > >Oh, for blanks sake. When are you CS weenies going to learn some math? . . . >Choosing a,b \in Z --> a/b = floor[a/b] is the best, >mathematically consistent way to handle integer division. [this gives the correct definition: a mod b = a-b*floor[a/b]] Here's at least one CS weenie that agrees with you. On at least one occasion I've gone crazy trying to track down errors related to the incorrect implementation of the % (so called modulus) operator in C. I have this funny notion in my head that "a mod b" ought to be in the range 0 to b-1. I remember once thinking after a core dump "hmmm... maybe '%' is returning a negative value... naaah, they couldn't have been that dumb; it must be my fault," and wasting another half hour trying to track down a non-existent bug. When I first learned that floor[x] was the largest integer less than or equal to x (a long time ago, in high school) it did strike me as strange, since my intuitive notion of turning a real into an integer involved throwing away all the digits to the right of the decimal point. After seeing enough mathematics, I was ultimately convinced that my intuition was at fault. That is, the idea of digit truncation is an _artifact_ of the way we _represent_ numbers, and is not elegantly defined in terms of the numbers themselves (as many have pointed out, you have to throw in these nasty absolute values to make it work). On the other hand, as a computer weenie, I like to have direct access to the operations the machine is actually performing. If we assume that floating point arithmetic is done using a sign-magnitude representation then it is reasonable to conclude that when the machine coerces a float to an integer, it does so by throwing away the digits to the right of the decimal point. This is somewhat easier to implement, though it gives an incorrect value for floor. Assuming the machine is giving out this value for free, I would rather have the *option* of using it, than be *forced* to use a version of floor or mod which is correct but requires a software test. When I say I would like to have the option, this is not to say that I would be inclined to exercise the option often. Normally, I would be quite happy to pay a time penalty if it meant I could remember exactly what the function is supposed to return. A nice and easy way to get around this problem is to define your own "defensive" mod procedure, which assumes that mod only works for positive numbers. The obvious way to do this involves an extra software test. If you're careful, it can be made completely portable. Incidentally, the way I got around this problem in practice was simply to add a big multiple of b to a when computing "a mod b." That is, a mod b = kb+a mod b So, if we choose k large enough to insure kb+a is always positive, then we get the correct value for mod. As long as b is constant, we can precompute kb. Admittedly, this is a kludge, but it is probably faster than sticking in an extra "if." Paul Callahan callahan@crabcake.cs.jhu.edu callahan@psuvax1.cs.psu.edu
karl@haddock.ima.isc.com (Karl Heuer) (02/24/90)
In article <0:X1-+Fxds13@ficc.uu.net> peter@ficc.uu.net (Peter da Silva) writes: >I've got a secret for you. Engineers like a continuous div/rem as well. The >folks who got it wrong were the physiscists, who never deal with integers >nohow, and crystallography weenies, ditto. As you may know, C allows the / % operator-pair to be implemented in either of two$ ways: the reflection-invariant definition that rounds toward zero, or the translation-invariant one that rounds toward negative infinity. It seems that there were some voices that didn't like that indeterminacy, and the compromise position was to add the div() function whose result-pair would be predictable. For some reason--possibly to interface with other "broken" languages--the X3J11 Committee chose to make div() round toward zero. I think they should have also provided a mathdiv() that rounds toward minus infinity; since they didn't, I keep such a function in my own library. Karl W. Z. Heuer (karl@ima.ima.isc.com or harvard!ima!karl), The Walking Lint ________ $ Strictly speaking, I suppose the implementation-defined rule could be something silly like "round toward negative infinity if the denominator is a power of two, else round toward zero", but since the choice must be documented, I doubt that any serious vendor will try that.
karl@haddock.ima.isc.com (Karl Heuer) (02/24/90)
In article <E*er-q@cs.psu.edu> callahan@mordor.endor.cs.psu.edu (Paul B. Callahan) writes: >After seeing enough mathematics, I was ultimately convinced that my intuition >was at fault. A similarly confusing point is that the negative of a negative number is positive. Ah, the memories of being a TA... >If we assume that floating point arithmetic is done using a sign-magnitude >representation [then truncate is probably easier than floor to implement]. But, given that most implementations use two's complement for integers, and even for floating-point exponents, why *is* sign-magnitude the standard for floating point significands? Karl W. Z. Heuer (karl@ima.ima.isc.com or harvard!ima!karl), The Walking Lint
dik@cwi.nl (Dik T. Winter) (02/25/90)
In article <16014@haddock.ima.isc.com> karl@haddock.ima.isc.com (Karl Heuer) writes: > In article <E*er-q@cs.psu.edu> callahan@mordor.endor.cs.psu.edu (Paul B. Callahan) writes: > >If we assume that floating point arithmetic is done using a sign-magnitude > >representation [then truncate is probably easier than floor to implement]. > > But, given that most implementations use two's complement for integers, and > even for floating-point exponents, why *is* sign-magnitude the standard for > floating point significands? > There is a good reason to use two's complement for integers: on an add ignore carry, this reason is much less compelling when doing floating-point arithmetic, you can not simply ignore carry. Note also that the exponent is not strictly two's complement, but has the sign bit inverted. The reason is that compare logic is simplified. Further, IEEE specifies four rounding modes, so using a two's complement mantissa because of simple truncation is no good reason. It is even stronger: when doing a round to nearest IEEE specifies that if the exact result is halfway two representable numbers, that number has to be chosen that has a low order zero bit (*). With a two's complement mantissa a similar requirement might be posed, but it would look more complex, and would be more complex in the logic. -- (*) See [I think; this is from memory] IEEE Computer, Vol. 14, Issue 1. This describes draft 8.0 of the IEEE standard and has a number of accompanying articles. The current standard is based on draft 10.0. There are some differences, but they are not shocking. I do not have a reference for that standard. -- dik t. winter, cwi, amsterdam, nederland dik@cwi.nl
flee@shire.cs.psu.edu (Felix Lee) (02/25/90)
Robert D. Silverman <bs@linus.UUCP> wrote:
>Huh? This statement has absolutely nothing to do with what I said.
Grr, semantic difficulties. I think I agree with your position, but
not with your phrasing.
Anyway, more silliness: ADA has both "rem" and "mod", and its integer
division rounds towards zero. (e.g., (-A)/B = -(A/B) = A/(-B))
--
Felix Lee flee@shire.cs.psu.edu *!psuvax1!fleemoss@ibis.cs.umass.edu (Eliot Moss) (02/26/90)
(Please take this as appropriately tongue-in-cheek, though there is a little bit of a message, too! :-) Ok, you theoretical weenies, the *real* reason why -5 DIV 2 comes out as -1 is that some of the first computers (including some of the first ones on which FORTRAN was implemented) were sign-magnitude machines ... so they implemented the MOD, DIV, etc. functions on the absolute values (magnitudes) and then propagated the signs according to (slightly arbitrary) rules. The FORTRAN standards were established in this distant era, have propagated to the present day, and continue to lead machine designers to implement the "FORTRAN" (sign/magnitude) version of these operations in hardware, even when language designers (such as myself) and algorithm designers probably prefer the purer "mathematical" form. The sign/magnitude form probably *is* a little easier to implement, but if it's not what people want, it doesn't matter. Of course, what people want depends on which people you ask .... Eliot -- J. Eliot B. Moss, Assistant Professor Department of Computer and Information Science Lederle Graduate Research Center University of Massachusetts Amherst, MA 01003 (413) 545-4206; Moss@cs.umass.edu
ccplumb@lion.waterloo.edu (Colin Plumb) (03/01/90)
In article <16014@haddock.ima.isc.com> karl@haddock.ima.isc.com (Karl Heuer) writes: >But, given that most implementations use two's complement for integers, and >even for floating-point exponents, why *is* sign-magnitude the standard for >floating point significands? Because the multiply/add ratio is much higher for floating point code, and signed-magnitude is better for multiply at the expense of add. -- -Colin
sjs@spectral.ctt.bellcore.com (Stan Switzer) (03/01/90)
In article <Er$cfg@cs.psu.edu> flee@shire.cs.psu.edu (Felix Lee) writes: > Dave Jones <djones@megatest.UUCP> wrote: > >I differ. The first of these, -5 div 3 == -1 is wrong. > > The contrary view is that abs(a/b) != abs(-a/b) is strange. It > depends on what you're doing. I have no problems with either stance. Put up or shut up. I have often found that the anomalous behavior of "modulus" at zero has caused me extra work to make it do the "right" thing: -5 div 3 == -2 -5 mod 3 == 1 This has occurred in graphics applications, in communications handlers (computing sliding windows using a wrap-around counter), and others. Please, somebody, show me a single example where the other behavior is actually USEFUL! We are not concerned with whether your grade-school education [ -a/b == -(a/b) ] applies to computers, but with what actually is useful in integer computation in actual algorithms. Stan Switzer sjs@bellcore.com