weemba@brahms.BERKELEY.EDU (Matthew P. Wiener) (01/30/86)
In article <332@ism780c.UUCP> tim@ism780c.UUCP (Tim Smith) writes: >[Which is preferred: (-a)%b == - (a%b) or (-a)%b >= 0 always?] >Are there any good mathematical grounds for choosing one alternative over >the other here? Note that I am not asking from a hardware point of view >which is better. I want to know mathematically if one is better than >the other. I have NEVER seen an instance where the first one is preferable. Not only is it not preferable, it is just incorrect. Why such a routine has been allowed to be 50% inaccurate in every existing language all these years is beyond me. But since that is what you get, I have always had to program around it, sometimes thinking of clever ways to prevent negative numbers from being fed into the remaindering. Even in non-mathematical usages, the second is preferred. For example, if you have a circular list of length N, kept in an array, i=change(i)%N is the usual way most steps through the list are done, for some integer function change(i). At one research institute I have worked at, IMOD is put in the Fortran library, to be used instead of MOD, so as to get the correct remainder. MOD was left for portability from other people's software, not for usage. [I pity the fool who says "but the first is faster".] [Whether CS people should even be *allowed* to make such mathematical decisions is another question. In C on UNIX, for example, one has log(-x) == log(x), a rather dangerous identity, not based on anything comprehensible. Thus, the implementation of general exponentiation, a**b = pow(a,b) = exp( b*log(a) ) will silently return the wrong value if a is negative. (Try taking cube roots this way!)] ucbvax!brahms!weemba Matthew P Wiener/UCB Math Dept/Berkeley CA 94720
gsmith@brahms.BERKELEY.EDU (Gene Ward Smith) (01/30/86)
In article <11603@ucbvax.BERKELEY.EDU> weemba@brahms.UUCP (Matthew P. Wiener) writes: >In article <332@ism780c.UUCP> tim@ism780c.UUCP (Tim Smith) writes: >>[Which is preferred: (-a)%b == - (a%b) or (-a)%b >= 0 always?] >>Are there any good mathematical grounds for choosing one alternative over >>the other here? Note that I am not asking from a hardware point of view >>which is better. I want to know mathematically if one is better than >>the other. > >I have NEVER seen an instance where the first one is preferable. Not >only is it not preferable, it is just incorrect. Why such a routine >has been allowed to be 50% inaccurate in every existing language all >these years is beyond me. > >[Whether CS people should even be *allowed* to make such mathematical >decisions is another question. In C on UNIX, for example, one has >ucbvax!brahms!weemba Matthew P Wiener/UCB Math Dept/Berkeley CA 94720 Matthew has just about said it all, but since this has been my absolute *pet* gripe for some time now, I can't resist adding another $0.02 to the bill. When mathematicians define functions in a certain way, it is almost always for good reasons. I can think of only a few cases where doing things differently might be advisable (e.g., 1/Gammma(x) or 1/Gamma(x+1) instead of Gamma(x) never needs to worry about the poles so might be better on a computer, even though for theoretical perposes Gamma(x) is fine). Unless you really understand the situation, don't mess with the definitions of math functions and we will all be happier. Would CS people think |sin(x)| was as good as sin(x), or think that sqrt should be sqrt(|x|)? Then why mess around with quotient and remainder functions when you don't have a clue on God's green Earth what you are doing? Signed An Angry Number Theorist
weemba@brahms.BERKELEY.EDU (Matthew P. Wiener) (01/30/86)
>>[Whether CS people should even be *allowed* to make such mathematical >>decisions is another question. In C on UNIX, for example, one has > >bill. When mathematicians define functions in a certain way, it is almost >always for good reasons. I can think of only a few cases where doing >things differently might be advisable (e.g., 1/Gammma(x) or 1/Gamma(x+1) >instead of Gamma(x) never needs to worry about the poles so might be >better on a computer, even though for theoretical perposes Gamma(x) is >fine). Unless you really understand the situation, don't mess with the Speaking of the gamma function, why (in C on UNIX) is it CALLED gamma() when it RETURNS log(gamma())? Sheeesh. ucbvax!brahms!weemba Matthew P Wiener/UCB Math Dept/Berkeley CA 94720
wyatt@cfa.UUCP (Bill Wyatt) (01/31/86)
> [ .... ] In C on UNIX, for example, one has > log(-x) == log(x), a rather dangerous identity, not based on anything > comprehensible. Thus, the implementation of general exponentiation, > a**b = pow(a,b) = exp( b*log(a) ) will silently return the wrong value > if a is negative. (Try taking cube roots this way!)] > > ucbvax!brahms!weemba Matthew P Wiener/UCB Math Dept/Berkeley CA 94720 I did the above example (uVax II, Ultrix 1.1) and got a `floating exception'. AHA, I thought , DEC cleaned up this bogosityr! Then I decided to simply print log(-4.0), and it happily printed a garbage number! It would seem that the exception was only because the exp function was delivered a large number. -- Bill UUCP: {seismo|ihnp4|cmcl2}!harvard!talcott!cfa!wyatt Wyatt ARPA: wyatt%cfa.UUCP@harvard.HARVARD.EDU
td@alice.UucP (Tom Duff) (01/31/86)
Pardon my flamage, but what sort of nonsense is this: [in reference to divide instructions that give -(a/b)=(-a)/b] >I have NEVER seen an instance where the first one is preferable. Not >only is it not preferable, it is just incorrect. Wrong! That's the definition. It can't be incorrect. It might be different from what a number theorist wants, but by no stretch of the imagination can it be called incorrect. A mathematician should be able to to handle this elementary concept. >Why such a routine >has been allowed to be 50% inaccurate in every existing language all >these years is beyond me. Well, it's that way because that's the way it's defined in the ANSI Fortran standard, and Fortran is probably a Good Thing for a computer to support -- certainly more important than niggling know-nothing number-theoretic nonsense. Why does Fortran do it that way? Probably because the IBM 701 did it that way. Why did the IBM 701 do it that way? Well, at the time people thought that a divide instruction that satisfied certain identities was more important than mod function behavior. Certainly in most of the applications for which Fortran was designed (i.e. engineering numerical calculations) the behavior of the mod function is of minimal interest. In any case, why should you be worried that some operation you want to do isn't primitive. Most programming languages don't provide arithmetic on multivariate polynomials with arbitrary precision rational coefficients either (which I want more often than I want a number-theoretic mod function.) In any case, it's fairly easy to write: a=b%c if(a<0) a+=c I can't believe that you couldn't discover this code sequence yourself. (Note that it works whether the range of b%c is [0,c) or (-c,c) -- the C language definition allows either.) >[Whether CS people should even be *allowed* to make such mathematical >decisions is another question. In C on UNIX, for example, one has >log(-x) == log(x), a rather dangerous identity, not based on anything >comprehensible. Thus, the implementation of general exponentiation, >a**b = pow(a,b) = exp( b*log(a) ) will silently return the wrong value >if a is negative. (Try taking cube roots this way!)] This sort of nonsense makes me wonder whether the writer should be allowed to make *any* sort of decision at all. No plausible definition of the log function will let you use it to take cube roots of arbitrary reals in this manner. On a higher level of discourse, this writer (Matthew P Whiner) seems to think that mathematicians enjoy some sort of moral and intellectual superiority to engineers and computer scientists. Usually, this attitude is a symptom of envy, since mathematicians are so hard to employ, can't get decent salaries when they do find work, and have a much harder time raising grant money. The smart ones embrace computer science rather than denigrating it. The dull ones just say ``Computer Science? Pfui: that's not mathematics,'' thus demonstrating their lack of understanding of the nature of mathematics and of computer science. In summary: It is better to remain silent and be thought a fool than to speak up and remove all doubt.
thomas@utah-gr.UUCP (Spencer W. Thomas) (01/31/86)
There is of course, always another way to look at it. The '%' operator
is not defined to be MOD, it is defined such that
(a/b)*b + a%b = a
In other words, it is the REMAINDER upon dividing a by b. Now, if you
want a%b to always be positive, you must then have
(-a)/b != -(a/b)
which, I think you will agree, is much worse. If you really want MOD,
here it is:
mod(a,b)
{
return (( a % b ) + b) % b;
}
--
=Spencer ({ihnp4,decvax}!utah-cs!thomas, thomas@utah-cs.ARPA)steve@jplgodo.UUCP (Steve Schlaifer x3171 156/224) (01/31/86)
In article <11610@ucbvax.BERKELEY.EDU>, gsmith@brahms.BERKELEY.EDU (Gene Ward Smith) writes: > In article <11603@ucbvax.BERKELEY.EDU> weemba@brahms.UUCP (Matthew P. Wiener) writes: > >In article <332@ism780c.UUCP> tim@ism780c.UUCP (Tim Smith) writes: > >>[Which is preferred: (-a)%b == - (a%b) or (-a)%b >= 0 always?] > >>Are there any good mathematical grounds for choosing one alternative over > >>the other here? Note that I am not asking from a hardware point of view > >>which is better. I want to know mathematically if one is better than > >>the other. > > > >I have NEVER seen an instance where the first one is preferable. Not > >only is it not preferable, it is just incorrect. Why such a routine > >has been allowed to be 50% inaccurate in every existing language all > >these years is beyond me. > > > >[Whether CS people should even be *allowed* to make such mathematical > >decisions is another question. In C on UNIX, for example, one has > > >ucbvax!brahms!weemba Matthew P Wiener/UCB Math Dept/Berkeley CA 94720 > > Matthew has just about said it all, but since this has been my absolute > *pet* gripe for some time now, I can't resist adding another $0.02 to the > bill. When mathematicians define functions in a certain way, it is almost > always for good reasons. I can think of only a few cases where doing > ....... > Then why mess around with quotient and remainder > functions when you don't have a clue on God's green Earth what you are > doing? > > > Signed > > An Angry Number Theorist If you think of % as returning the *mathematical* remainder of a/b then it should return a value >=0. On the other hand, to be consistent with this view, the quotient operator (/) will also have to be modified to preserve the formulae b=qa+r (0<=r<a) q=b/a i.e. (-3)/2 must be -2 if (-3)%2 is 1. But this then means that (|a|)/b is not the same as |a/b| for a<0. Maybe *An Angry Number Theorist* wants this, but it seems to me to be a trap just waiting for the unwary to fall into. As for why the restriction of 0<=r<a was decided on, my only guess is that it then always produces a unique (q,r) for any given (a,b); this is a useful property when you are proving theorems or doing theoretical investigations. -- ...smeagol\ Steve Schlaifer ......wlbr->!jplgodo!steve Advance Projects Group, Jet Propulsion Labs ....group3/ 4800 Oak Grove Drive, M/S 156/204 Pasadena, California, 91109 +1 818 354 3171
weemba@brahms.BERKELEY.EDU (Matthew P. Wiener) (02/01/86)
In article <1666@utah-gr.UUCP> thomas@utah-gr.UUCP (Spencer W. Thomas) writes: >There is of course, always another way to look at it. The '%' operator >is not defined to be MOD, it is defined such that > (a/b)*b + a%b = a >In other words, it is the REMAINDER upon dividing a by b. Now, if you >want a%b to always be positive, you must then have > (-a)/b != -(a/b) >which, I think you will agree, is much worse. In previous articles, I and Gene Smith, both mathematicians, have stated our disapproval of defining % to be sometimes + and sometimes -. We did not get around to stating our opinions of the two identities involved, so here's mine. (a/b)*b + a%b == a This identity is clearly needed. It enables one to go back and forth between / and % in a consistent way, irregardless of whether % is MOD. Indeed, among mathematicians, the official definition of quotient and remainder for a over b (a,b integers with b>0) is to find the unique integer values of q and r such that a==b*q+r and 0<=r<b. You will see both that the identity holds and remainder is non-negative. (-a)/b == -(a/b) I see no reason for this. It may look nice formally, it corresponds to the school algorithms for how one goes about dividing with negative numbers by hand, but I see no reason for it. In fact, since to have both identities holding requires what I consider the mathematically obnoxious choice of %, I must oppose the identity. Notice that I mentioned that b>0 in the official mathematical definition. I really have no idea what one should do with b<0 in actual implementations. I have never seen it come up in or out of mathematics. Indeed, it perhaps seems preferable to generate some sort of arithmetic fault here. (Similarly there are rare cases where you want 3./0. to NOT cause a divide by zero fault, but you keep the fault because programmer error is the more likely explanation for 3./0..) But I am straying. (Of course, these comments about division only refer to integer division.) ----------------------------------------------------------------------------- Sorry if we seemed a little heavy handed last time. They've always seemed like defects that we users have to program around, and with no chance of ever changing, burned into all programming languages forever because--before I was even born!--someone chose the wrong convention. (Physicists sometimes dream of a world were the electron has a *positive* charge; if only we could go back in time and tell Ben Franklin to try the other convention; believe us, Ben, it makes a difference; etc.; sigh) Suddenly we get attached to the network and discover that maybe there is a way--why someone out there even ASKED us mathematicians what we thought! (Thanks!) We are both ex-Fortran programmers, and feel C and C++ are the wave of the future among scientific programmers. Now to convince the others.... (You powers that be might want to help!) ucbvax!brahms!weemba Matthew P Wiener/UCB Math Dept/Berkeley CA 94720
weemba@brahms.BERKELEY.EDU (Matthew P. Wiener) (02/02/86)
WARNING! The following article contains heavy flamage and sarcasm and no smiley faces. And it is not guaranteed to be interesting, accurate or informative. Any worse and it would have been rot13ed. Read at your own risk. Last chance to hit the 'n' key! In article <4917@alice.UUCP> td@alice.UucP (Tom Duff) writes: >Pardon my flamage, but what sort of nonsense is this: >[in reference to divide instructions that give -(a/b)=(-a)/b] >>I have NEVER seen an instance where the first one is preferable. Not >>only is it not preferable, it is just incorrect. >Wrong! Which sentence is wrong? It is an undeniable fact that *I* have never seen such instances, but you do include that as some "sort of nonsense". > That's the definition. It can't be incorrect. It might be different >from what a number theorist wants, but by no stretch of the imagination can >it be called incorrect. A mathematician should be able to to handle this >elementary concept. Of course it can be incorrect! 'correct' has the meanings of 'logically correct', in particular definitions must be tautologically correct, normally the proper usage within pure mathematics, and secondly of 'proper to do', as in "If I define f(a):=xyz, that is incorrect, because what users want is f(a):=xyzz". Which sense seems appropriate here? To quote from E W Dijkstra, "How Do We Tell Truths that Might Hurt", "... an exceptionally good mastery of one's native tongue is the most vital asset of a competent programmer". I must thank Tom Duff for illustrating that assertion so vividly. >>Why such a routine >>has been allowed to be 50% inaccurate in every existing language all >>these years is beyond me. >Well, it's that way because that's the way it's defined in the ANSI Fortran >standard, and Fortran is probably a Good Thing for a computer to support -- And of course it is important that C and other languages copy Fortran's mistakes. That way we won't have to strain our brains that much. I mean, why bother implementing what users want? Or am I confused, and Fortran did everything perfectly right off the bat, and every language since then has only confused people (like myself)? By the way, just out of curiosity mind you, this question popped into my head out of nowhere, but is anyone out there still using card readers? >certainly more important than niggling know-nothing number-theoretic nonsense. Oh wow, a Spiro Agnew fan! Or is William Safire your ghost-poster? >Why does Fortran do it that way? >Probably because the IBM 701 did it that way. Let's all take a deep bow for backwards compatibility! <Clap Clap> > Why did the IBM 701 >do it that way? Well, at the time people thought that a divide >instruction that satisfied certain identities was more important >than mod function behavior. Is that opinion or fact? I've sent the question off to the man who wrote the original Fortran compiler. > Certainly in most of the applications >for which Fortran was designed (i.e. engineering numerical calculations) >the behavior of the mod function is of minimal interest. Of course it is of minimal interest in most applications! So what is wrong with getting it right--excuse me, in case my digression earlier wasn't that clear--what is wrong with implementing the more common application that does occur? >In any case, why should you be worried that some operation you want to do >isn't primitive. Most programming languages don't provide arithmetic >on multivariate polynomials with arbitrary precision rational coefficients >either (which I want more often than I want a number-theoretic mod function.) And if they did, and all did it incorrectly--can you guess which meaning I'm using?--you'd be annoyed too. >In any case, it's fairly easy to write: > a=b%c > if(a<0) a+=c >I can't believe that you couldn't discover this code sequence yourself. >(Note that it works whether the range of b%c is [0,c) or (-c,c) -- the >C language definition allows either.) Your beliefs are accurate. What I can't believe is that I should have to do something so stupid myself each time. So close, and yet so far. >>[Whether CS people should even be *allowed* to make such mathematical >>decisions is another question. In C on UNIX, for example, one has >>log(-x) == log(x), a rather dangerous identity, not based on anything >>comprehensible. Thus, the implementation of general exponentiation, >>a**b = pow(a,b) = exp( b*log(a) ) will silently return the wrong value >>if a is negative. (Try taking cube roots this way!)] >This sort of nonsense makes me wonder whether the writer should be >allowed to make *any* sort of decision at all. No plausible definition >of the log function will let you use it to take cube roots of arbitrary >reals in this manner. I agree, both about the "sort of nonsense" advocated inducing wonder and the impossibility of defining log to take arbitrary *odd* roots. [To take cube roots plausibly requires defining log(-a):=log(a)+3*pi*i.] The example comes from a numerical analysis class I was teaching, where the students solved y'=y^third. I forgot that a lot of the students would not know that a**b cannot be used with a<0, and those who programmed in C got silently burned because of that "rather dangerous identity". And this is an example of my complaint. If one is doing a *mathematical* problem on the computer, one should not have to keep second guessing what the language is doing with the *mathematics*! We all can argue about the little things in languages that bug us--does ';' terminate or separate, for example--but certain little things, like what is a%b when a<0, don't seem to be decided without regard for their mathematical reasonableness. And then try to find a description in the manual of what was actually implemented! [The WORST offenders are random number generators. I have ended up writing my own because the one given is proprietary etc. UGH!] In the cube root of negative numbers example, there is no implementation that returns the correct--back to the logical sense--answer, so the proper thing to do is crash the program, and not return something for the sake of returning something. The CRAY-1's floating point multiply shaves many nanoseconds by a method that only gets 47 out of the 48 bit mantissa. That is clearly incorrect. In this case, I can only admire Seymour's boldness and imagination to take this step, and the lost bit seems worth it. Is there a similar reason to have (-a)/b == -(a/b) ? >On a higher level of discourse, this writer (Matthew P Whiner) seems ^^^^^^ ^^^^^^ Emerson once said "Consistency is the hobgoblin of little minds". So sue me for having a little mind. >to think that mathematicians enjoy some sort of moral and intellectual >superiority to engineers and computer scientists. Well, maybe a little. It depends on the engineer/computer scientist. > Usually, this >attitude is a symptom of envy, since mathematicians are so hard to >employ, can't get decent salaries when they do find work, and have >a much harder time raising grant money. The smart ones embrace >computer science rather than denigrating it. The dull ones just >say ``Computer Science? Pfui: that's not mathematics,'' thus demonstrating >their lack of understanding of the nature of mathematics and of >computer science. What a bunch of bullshit. >In summary: > It is better to remain silent and be thought a fool than >to speak up and remove all doubt. I agree! By the way, Tom Duff, have YOU ever seen an example where a%b<0 is preferred? ucbvax!brahms!weemba Matthew P Wiener/UCB Math Dept/Berkeley CA 94720
omondi@unc.UUCP (02/02/86)
> doing? > > > Signed > > An Angry Number Theorist *** REPLACE THIS LINE WITH YOUR MESSAGE ***
mouse@mcgill-vision.UUCP (der Mouse) (02/03/86)
[ Line eaters? Who ever hea
Don't you think this issue has been beaten to death already? How
about just agreeing that both sorts of behavior should be provided and
letting it go at that? We have different instructions which produce
this behavior when the divisor is a power of two (shifts and divides);
why can't we just have two sorts of divide? Some will want one and some
the other, as in all religious debates -- and it's surely not that hard
to satisfy both.
--
der Mouse
USA: {ihnp4,decvax,akgua,etc}!utcsri!mcgill-vision!mouse
philabs!micomvax!musocs!mcgill-vision!mouse
Europe: mcvax!decvax!utcsri!mcgill-vision!mouse
mcvax!seismo!cmcl2!philabs!micomvax!musocs!mcgill-vision!mouse
Hacker: One who accidentally destroys /
Wizard: One who recovers it afterwardweemba@brahms.BERKELEY.EDU (Matthew P. Wiener) (02/03/86)
In article <561@jplgodo.UUCP> steve@jplgodo.UUCP (Steve Schlaifer x3171 156/224) writes: >If you think of % as returning the *mathematical* remainder of a/b then >it should return a value >=0. On the other hand, to be consistent with this >view, the quotient operator (/) will also have to be modified to preserve >the formulae > > b=qa+r (0<=r<a) > q=b/a > >i.e. (-3)/2 must be -2 if (-3)%2 is 1. But this then means that (|a|)/b is not >the same as |a/b| for a<0. Maybe *An Angry Number Theorist* wants this, but it >seems to me to be a trap just waiting for the unwary to fall into. [sic: you go back and forth between a/b and b/a above :-(] But that's what we have been saying all along! Someone doing integer division, is not doing floating point division, and if he doesn't know that the rules are different, then yes, he will fall into trouble. There are several identities running around that are incompatible. (1) a == (a/b) * b + a%b (2) (-a)/b == -(a/b) (3) (a+b)/b == a/b + 1 (4) (a+b)%b == a%b Notice that (3) and (4) are compatible with what the number theorists want, but (2) isn't. Sure the naive user is fooled by (2) under the version we want, but then he's fooled by (3) and (4) in the usual version. (1) holds when the / and % are both what the number theorist wants or when neither are what the number theorist wants. >As for why the restriction of 0<=r<a was decided on, my only guess is that >it then always produces a unique (q,r) for any given (a,b); this is a useful >property when you are proving theorems or doing theoretical investigations. That is correct. It is also useful for programming a circular list. ------------------------------------------------------------------------------ Related question: what about floating to integer conversions? That is always done by truncating after the decimal point. That always seemed wrong to me, but it doesn't seem to bother me as much, and I can't remember a time when it got in my way. (unlike %) ucbvax!brahms!weemba Matthew P Wiener/UCB Math Dept/Berkeley CA 94720
rentsch@unc.UUCP (02/03/86)
ENOUGH ALREADY! LET'S GET THIS DISCUSSION OFF OF net.arch AND ONTO WHATEVER NEWSGROUP IT BELONGS! (probably it doesn't belong on net.lang.c, either. may i suggest net.who-cares?)
jer@peora.UUCP (J. Eric Roskos) (02/03/86)
> Pardon my flamage, but what sort of nonsense is this: > [in reference to divide instructions that give -(a/b)=(-a)/b] > >I have NEVER seen an instance where the first one is preferable. Not > Wrong! That's the definition. It can't be incorrect. It might be > different from what a number theorist wants, but by no stretch of the > imagination can it be called incorrect. A mathematician should be able to > to handle this elementary concept. But it may not be too usable to mathematicians if your definition is different from the generally accepted one... after all, mathematicians are one of the main groups of people these machines are built for... Anyway, I thought he was talking about "%", not "/"... I would think that since 3 * -2 = -6 then -6 / 3 = -2 and -6 / -2 = 3 Could someone who is a genuine number theorist please post the way the "modulo" function is supposed to work, and also what number theorists would prefer the results of integer divisions with nonzero remainders to be (for various permutations of signs), so that people who have some say in the way instruction sets get designed can make sure it's done right in the future? Please put "I am a number theorist" at the start of your posting (include some proofs too if you want!) ... this discussion has been going around and around for weeks. Better yet, put "Number theory" in the "subject" line ... Be sure to post it to net.arch, not just net.math. -- 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 xxxxx4xxx "There are other places that are also the world's end ... But this is the nearest ... here and in England." -TSE
ladkin@kestrel.ARPA (02/03/86)
In article <4917@alice.UUCP>, td@alice.UucP (Tom Duff) writes: > Pardon my flamage, but what sort of nonsense is this: > reals in this manner. > [......] > On a higher level of discourse, this writer (Matthew P Whiner) seems > to think that mathematicians enjoy some sort of moral and intellectual > superiority to engineers and computer scientists. Usually, this > attitude is a symptom of envy, since mathematicians are so hard to > employ, can't get decent salaries when they do find work, and have > a much harder time raising grant money. The smart ones embrace > computer science rather than denigrating it. The dull ones just > say ``Computer Science? Pfui: that's not mathematics,'' thus demonstrating > their lack of understanding of the nature of mathematics and of > computer science. > > In summary: > It is better to remain silent and be thought a fool than > to speak up and remove all doubt. I don't think anybody should pardon this sort of thing. Arrogance and snobbishness are best indulged in between consenting adults in private. Please let's clean up the discussion. This is an important and interesting issue, as shown by the inability of the participants to resolve it easily. Peter Ladkin
franka@mmintl.UUCP (Frank Adams) (02/04/86)
We seem to agree that there are three at least somewhat important identities. 1) (a/b)*b + a%b = a 2) (a+b)%b = a%b or (a+b)/b = a/b + 1 3) (-a)%b = -(a%b) or (-a)/b = -(a/b) As a mathematician and as a computer scientist, I cannot accept definitions of these functions for which (1) does not hold. Given (1), the two forms given for (2) and (3) are equivalent. Now, in fact, (3) in the division form is important. The area I know of where it is important is in financial applications. Suppose I own 200 shares of stock, which I purchased at a total cost of $2,098.75, including commission. I now sell 100 shares. I have to compute the cost basis for those 100 shares: $1,049.38. Now, suppose I had a short position with the same cost basis: -$2,098.75. If I buy back half of these, the rounding has to be done the same way: -$1,049.38. Of course, this application is not rounding toward zero; it is rounding to the *nearest* penny. So what we want for this application is to round to the nearest integer, with 1/2 rounded away from zero. This choice is very common in financial applications. (By the way, financial applications fairly often divide by negative numbers.) There are also a lot of number theoretic algorithms which run faster if the least absolute remainder is used; I once heard a professor of mathematics (Hans Zassenhaus, if memory serves) state that the least absolute remainder is what computer division *should* return. I believe that computers (CISC) and programming languages should provide at least three different division and remainder operations: round towards 0, round towards -infinity, and round to nearest (with 1/2 rounded away from 0). There is something to be said for round away from zero, and round to +infinity, as well. Frank Adams ihpn4!philabs!pwa-b!mmintl!franka Multimate International 52 Oakland Ave North E. Hartford, CT 06108
omondi@unc.UUCP (Amos Omondi) (02/04/86)
> In article <4917@alice.UUCP>, td@alice.UucP (Tom Duff) writes: > > Pardon my flamage, but what sort of nonsense is this: > > reals in this manner. > > [......] > > On a higher level of discourse, this writer (Matthew P Whiner) seems > > to think that mathematicians enjoy some sort of moral and intellectual > > superiority to engineers and computer scientists. Usually, this > > attitude is a symptom of envy, since mathematicians are so hard to > > employ, can't get decent salaries when they do find work, and have > > a much harder time raising grant money. The smart ones embrace > > computer science rather than denigrating it. The dull ones just > > say ``Computer Science? Pfui: that's not mathematics,'' thus demonstrating > > their lack of understanding of the nature of mathematics and of > > computer science. > > > > In summary: > > It is better to remain silent and be thought a fool than > > to speak up and remove all doubt. > > I don't think anybody should pardon this sort of thing. > Arrogance and snobbishness are best indulged in > between consenting adults in private. > Presumably this also applies, notwithstanding how angry the number theorists are, to articles implying that all CS types are idiots who don't have the foggiest idea of what they are doing.
laura@hoptoad.uucp (Laura Creighton) (02/04/86)
In article <11689@ucbvax.BERKELEY.EDU> weemba@brahms.UUCP (Matthew P. Wiener) writes: >.... There are several identities >running around that are incompatible. > > (1) a == (a/b) * b + a%b > (2) (-a)/b == -(a/b) > (3) (a+b)/b == a/b + 1 > (4) (a+b)%b == a%b > >Notice that (3) and (4) are compatible with what the number theorists want, >but (2) isn't. Sure the naive user is fooled by (2) under the version we >want, but then he's fooled by (3) and (4) in the usual version. (1) holds >when the / and % are both what the number theorist wants or when neither are >what the number theorist wants. While it is true that number theorists want 3 and 4, it is not the naive user who will be fooled by 2. It is the naive *mathematician*, which is just about everybody. To non-mathematicians, 2 is a law, with about the same force as the law of gravity, and not something that you can redefine. Sure they are wrong about the force of this law -- but blame the way mathematics is taught in hich schools and grade schools. In the meantime, only the mathematicians, as a class, will have the perspective to see this. Everybody else (again as a class) will look at (-a)/b != -(a/b) and say ***BUG!!!*** So, as a practical matter, the mathematicians will have to come up with a work-around, since only they are going to be able to understand what they want. In letting non-mathematicians design the languages they use, mathematicians may have seriously goofed, because the non-mathematicians may not understand what it is that the mathematicians want -- if they did they would be mathematicians. Of course, I am not sure that there is consensus among mathematicians as to what they want. If there is, maybe they should write their own language. [I'm glad I wrote that last line. It tells me where to post this fool thing, which has been in the back of my mind, bothering me, the whole time I was writing this. Before that, I was strongly tempted to post to net.philosophy...] -- Laura Creighton ihnp4!hoptoad!laura hoptoad!laura@lll-crg.arpa
radford@calgary.UUCP (Radford Neal) (02/05/86)
First, let me say that I'm firmly in the (-3)%2 == 1, (-3)/2 == (-2) camp.
This is normally what one wants.
There is one case, however, where the (-3)/2 == 3/(-2) == -(3/2) == -1
identity is usefull - writing software floating point routines. I offer this
as a suggestion as to why the initial "mistake" was made.
Now that we "all" have hardware floating point, can we change divide?
Actually, I'd be satisfied if people would at least *document* what their
divide operation does! (E.g. the MC68000 processor manual just says "the
division is done using signed arithmetic"...)
Radford Nealthomas@utah-gr.UUCP (Spencer W. Thomas) (02/05/86)
At least C calls it '%', and not 'MOD', as in Pascal. Unless someone
tells you that % means MOD, you have some small chance of realizing that
it might not do exactly what you want.
I would still rather have (-1)/1000000000000 = 0, not -1.
--
=Spencer ({ihnp4,decvax}!utah-cs!thomas, thomas@utah-cs.ARPA)gsmith@brahms.BERKELEY.EDU (Gene Ward Smith) (02/05/86)
In article <4917@alice.UUCP> td@alice.UucP (Tom Duff) writes: >standard, and Fortran is probably a Good Thing for a computer to support -- >certainly more important than niggling know-nothing number-theoretic nonsense. Personally, I think we should do everything the way Cobol does it, and to hell with niggling nonsense about the "right" way to do numerical computations. So what if floating point arithmetic gets a little screwed up, as long as you can do double entry bookkeeping. >Why does Fortran do it that way? >Probably because the IBM 701 did it that way. Why did the IBM 701 >do it that way? Well, at the time people thought that a divide >instruction that satisfied certain identities was more important >than mod function behavior. Certainly in most of the applications >for which Fortran was designed (i.e. engineering numerical calculations) >the behavior of the mod function is of minimal interest. [DUFF] And this attitude shows; what do you think we are complaining about? > >On a higher level of discourse, this writer (Matthew P Whiner) seems >to think that mathematicians enjoy some sort of moral and intellectual >superiority to engineers and computer scientists. Usually, this >attitude is a symptom of envy, since mathematicians are so hard to >employ, can't get decent salaries when they do find work, and have >a much harder time raising grant money. The smart ones embrace >computer science rather than denigrating it. The dull ones just >say ``Computer Science? Pfui: that's not mathematics,'' thus demonstrating >their lack of understanding of the nature of mathematics and of >computer science. What are you trying to do here -- prove yourself wrong by self-referential example? Do you really think those mathematicians (the vast majority, I assure you) who think there is some kind of difference between mathematics and Computer Science are wrong? If so, why are you attacking mathematicians but not Computer Scientists? Do you make as much money as your doctor? What about your lawyer? >In summary: > It is better to remain silent and be thought a fool than >to speak up and remove all doubt. Tell me the truth -- is this a gag or are you serious??? To everyone else but Tom Duff -- thank you for letting me blow off years of accumulated steam. To Tom Duff -- thank you for letting me feel that mathematicians *really are* a little bit better than Computer Scientists/ Engineers (in fact, I never thought this before, and I probably won't think it next week). ucbvax!brahms!gsmith Gene Ward Smith/UCB Math Dept/Berkeley CA 94720 ucbvax!weyl!gsmith "When Ubizmo talks, people listen."
hansen@mips.UUCP (Craig Hansen) (02/05/86)
I assume that everyone else is as sick and tired of seeing this dead horse beaten as I am, but I find a point still unstated. Several people have asked for mathematical reasons for choosing integer division with rounding to - infinity rather than zero. I submit the following: If you wish to compute an approximation to a/b to the NEAREST integer, when a/b is rounded to minus infinity, you can use (a+a+b)/(b+b). I can think of no expression except those that involve conditionals for which this can be done when a/b is rounded to zero. Craig Hansen MIPS Computer Systems ...decvax!decwrl!mips!hansen
gwyn@brl-smoke.ARPA (Doug Gwyn ) (02/06/86)
What I would like is for the language to provide a notation for obtaining BOTH the quotient and the remainder of an integer division in a single operation. Too often I need both and have to go through extra overhead to get them (many computers compute both parts at the same time). (I would also like to get both the sine and the cosine of an angle in a single operation with reduced overhead, but that seems much less feasible.) This % vs. Mod debate is rather silly. C's % operator is NOT repeat NOT intended to be a modulo operator, although people often use it that way for positive operands. All reasonable mathematicians agree on what the definition of a mod b is for positive b and negative a. That should not be confused with what the result of a % b should be under similar circumstances. C intentionally hedges a bit on the meaning of % in such a case (which makes that a generally inadvisable situation to allow to arise in one's C code).
ladkin@kestrel.ARPA (02/06/86)
(ladkin) > > Arrogance and snobbishness are best indulged in > > between consenting adults in private. (omondi) > Presumably this also applies, notwithstanding how angry > the number theorists are, to articles implying that all > CS types are idiots who don't have the foggiest idea of > what they are doing. Yes it does, witness the paragraph you edited out, and my previous postings. A plea: please include uucp pathnames so that we on arpa can avoid posting personal replies like this. Peter Ladkin
jst@abic.UUCP (Shack Toms) (02/06/86)
> By the way, Tom Duff, have YOU ever seen an example where a%b<0 is preferred?
I am squarely in the 0<=a%b<b camp. I don't believe I have ever
used a mod function on signed integers when it was not "corrected"
with that obnoxious "if (a<0) a+=b".
However: One might use a%b<0 iff a<0 in an algorithm which printed
the value of an integer in a given radix. The least significant
digit of a in radix b would then be |a%b|. :-)
Note: K&R allows the definition of a%b to take on either of two
values, when a<0 or b<0. This means that, even on the rare (in my
experience) algorithm which requires a%b<0 iff a<0, the programmer
will have to add extra code to compensate for implementations which
always return a non-negative modulus.
It is the *ambiguity* in the specification which is most disconcerting.
Perhaps K&R thought that the performance penalty of implementing a
consistent modulus (or divide) was not justified, since negative
integers are rarely encountered in "C" [this comment cannot be traced
to K&R.] However, this performance penalty can be avoided simply by
declaring unsigned integers as "unsigned int". The way the definition
is now, one cannot portably take advantage of either implementation
of divide. That is: even on machines which implement modulus
according to the whims of the particular net.flame(r) [:-)], the
overhead of either:
m = a%b;
if (m<0) m += b;
or:
m = a%b;
if (a<0 && m>0) m -= b;
is always incurred in portable code. (Unless your compiler is
more intelligent than any of the "C" compilers I have ever used.)
On the other hand: the lack of the property
-a/b == -(a/b)
Is easily accounted for portably (simply write the expression you
mean rather than the other one. :-))
Disclaimer: blah blah blah....
Shack Tomsearl@mips.UUCP (Earl Killian) (02/07/86)
Of the languages I'm familiar with, I believe integer division is best handled in Common Lisp. There are four functions of two arguments: trunc, floor, ceil, and round. Each divides the first argument by the second and then rounds the result to an integer using round to zero, round to -infinity, round to +infinity, and round to nearest respectively. The second return value is the remainder of that division. Thus: (trunc 7 3) => 2, 1 ; 2*3 + 1 = 7 (trunc -7 3) => -2, -1 ; -2*3 + -1 = -7 (floor 7 3) => 2, 1 ; 2*3 + 1 = 7 (floor -7 3) => -3, 2 ; -3*3 + 2 = -7 (ceil 7 3) => 3, -2 ; 3*3 + -2 = 7 (ceil -7 3) => -2, -1 ; -2*3 + -1 = -7 (round 7 3) => 2, 1 ; 2*3 + 1 = 7 (round -7 3) => -2, -1 ; -2*3 + -1 = -7 The programmer picks what is appropriate. I have found floor and ceil to be the most useful, and trunc somewhat less. I have never used round. Actually these are also functions of one argument: (floor 3.5) => 3 0.5, etc.
ark@alice.UucP (Andrew Koenig) (02/07/86)
To add some more fuel to the fire, consider extending a%b to floating-point operands. If we do this, we find that defining a%b to have the sign of a in all cases allows a%b to be represented exactly as a floating-point number, whereas giving a%b the sign of b does not. Consider, for instance, the case where b is huge and positive and a is tiny and negative.
weemba@brahms.BERKELEY.EDU (Matthew P. Wiener) (02/08/86)
In article <367@mcgill-vision.UUCP> mouse@mcgill-vision.UUCP (der Mouse) writes: > Don't you think this issue has been beaten to death already? yes > .... >why can't we just have two sorts of divide? How would you implement that? If you make one form get / and the other a function call, you haven't changed things very much! > Some will want one and some >the other... Is there someone out there who *wants* a/b to round towards 0 (for reasons that say that is the desired result)? I asked that before and have not seen any affirmatives. ucbvax!brahms!weemba Matthew P Wiener/UCB Math Dept/Berkeley CA 94720
cdshaw@watrose.UUCP (Chris Shaw) (02/09/86)
In article <4589@kestrel.ARPA> ladkin@kestrel.ARPA writes: >... deleted personal argument goes here ... >A plea: please include uucp pathnames so that we on arpa can >avoid posting personal replies like this. > >Peter Ladkin I think the obvious choice is to shut one's face instead of cluttering the technical newsgroups with this kind of trash. I'm up to my chest in all the mud that got slung around on this issue, and I'm getting rather sick of it. In the future, if one has something to say, be concise, and try not to repeat what others have said. Ad Hominems and Straw Men will no longer be accepted. Chris Shaw watmath!watrose!cdshaw or cdshaw@watmath University of Waterloo In doubt? Eat hot high-speed death -- the experts' choice in gastric vileness !
weemba@brahms.BERKELEY.EDU (Matthew P. Wiener) (02/09/86)
In article <1671@utah-gr.UUCP> thomas@utah-gr.UUCP (Spencer W. Thomas) writes: >At least C calls it '%', and not 'MOD', as in Pascal. Unless someone >tells you that % means MOD, you have some small chance of realizing that >it might not do exactly what you want. ?????? >I would still rather have (-1)/1000000000000 = 0, not -1. What about (-999999999999)/1000000000000 ? What about (+999999999999)/1000000000000 ? ucbvax!brahms!weemba Matthew P Wiener/UCB Math Dept/Berkeley CA 94720
hofbauer@utcsri.UUCP (John Hofbauer) (02/10/86)
> This % vs. Mod debate is rather silly. C's % operator is > NOT repeat NOT intended to be a modulo operator, although > people often use it that way for positive operands. All > reasonable mathematicians agree on what the definition of > a mod b > is for positive b and negative a. That should not be > confused with what the result of > a % b > should be under similar circumstances. C intentionally > hedges a bit on the meaning of % To paraphrase Alice In Wonderland loosely, an operator means whatever you want it to mean, nothing more, nothing less. The remainder of a machine integer division is defined as being whatever the engineer's found convenient to implement. Any resemblance to mathematics is purely coincidental.
weemba@brahms.BERKELEY.EDU (Matthew P. Wiener) (02/10/86)
In article <731@abic.UUCP> jst@abic.UUCP (Shack Toms) writes: >However: One might use a%b<0 iff a<0 in an algorithm which printed >the value of an integer in a given radix. The least significant >digit of a in radix b would then be |a%b|. :-) So would |a|%b, and it works under either convention. :-) ucbvax!brahms!weemba Matthew P Wiener/UCB Math Dept/Berkeley CA 94720
jsdy@hadron.UUCP (Joseph S. D. Yao) (02/10/86)
In article <685@brl-smoke.ARPA> gwyn@brl.ARPA writes: >What I would like is for the language to provide a notation >for obtaining BOTH the quotient and the remainder of an >integer division in a single operation. C doesn't provide a notation for an op with two returns, so this might be a little hard. (How I Did It:) On a PDP-11 with no FPP and V6 (that long ago), I wrote the long div/rem functions. Since the work involved was massive, I saved the operands, the quotient, and the remainder. If subsequent calls had the same operands, I just returned the already-computed values! If a div or rem is "cheap", this loses. However, if it is done in microcode the same way, this technique is recommended to the microcoders. >This % vs. Mod debate is rather silly. C's % operator is >NOT repeat NOT intended to be a modulo operator, although >people often use it that way for positive operands. Hooray. Modulo() != Remainder() except under certain circumstances, as this branch of net.flame has shown. I was at the point of posting this myself, the discussion was getting so disgusting (not to mention ad hominem -- or ad speciem). My degrees and first job titles all said "mathematics". Subsequent job titles have included phrases like "computer scientist" and "software engineer." This may qualify me to speak. (One degree also says "CS", and > 1 decade of experience lends credence to "engineer".) I consider each occupation to be superior to the others in what they do. Period. I don't expect the M or SE to immediately see a CS point of view, nor an SE or CS the M point of view, or any of the other possible permutations. SE's and programmers have made the remainder function what it is because the specs said so -- great! CS'ers, who don't use i m p l e m e n t e d languages unless they have to, are free to use mod() or rem() as they please. Mathematicians (pure) use anything they want, as long as it's in the realm of pure thought. Mathematicians (applied) have to use the tools that are available: so it is necessary for the SE's to provide their users d o c u m e n t a t i o n that clearly says, e.g., what rem is (it isn't mod, for instance). Then it is necessary for the users to r e a d said documentation, before complaining. Or take a class and l i s t e n . (No, I'm not saying none of my students ever did -- just the ones that complained most that they didn't understand. ;-}) All >reasonable mathematicians agree on what the definition of > a mod b >is for positive b and negative a. That should not be >confused with what the result of > a % b >should be under similar circumstances. C intentionally >hedges a bit on the meaning of % in such a case (which >makes that a generally inadvisable situation to allow to >arise in one's C code). -- Joe Yao hadron!jsdy@seismo.{CSS.GOV,ARPA,UUCP}
rb@ccivax.UUCP (rex ballard) (02/11/86)
As I recall, FORTH-83 has adopted the 'theorists' approach. so that A B SWAP OVER /MOD ROT * + gives the original value of A translated that gives A B SWAP ( Stack = B A ) OVER ( Stack = B A B ) /MOD ( Stack = A%B A/B B ) (A/B is floored) ROT ( Stack = A/B B A%B ) * ( Stack = (A/B)*B A%B ) + ( Stack = (A/B)*B+A%B ) (=A) This was a deliberate break from FORTH-79 which would have required the 'twiddle test'. Appearently, most applications either were using the unsigned versions, the positive case, or had rewritten the primitive. the example (taken from the draft standard of May 83) dividend divisor remainder quotient 10 7 3 1 -10 7 4 -2 10 -7 -4 -2 -10 -7 -3 1 Is this any better? I guess religion (because thats the way we always do it) isn't everything.
ka@hropus.UUCP (Kenneth Almquist) (02/11/86)
> Perhaps K&R thought that the performance penalty of implementing a > consistent modulus (or divide) was not justified, since negative > integers are rarely encountered in "C" [this comment cannot be traced > to K&R.] However, this performance penalty can be avoided simply by > declaring unsigned integers as "unsigned int". On the VAX, the unsigned remainder function is implemented as a subroutine call. The standard divide instruction cannot be used because the divide instruction does not work on unsigned integers. In Ada, division truncates towards zero, and there are separate remainder and modulo operators. The % operator in C is a remainder operator; we could have a new operator %% for modulo. (On the other hand, maybe not. We don't want C to get as large as Ada!) Kenneth Almquist ihnp4!houxm!hropus!ka (official name) ihnp4!opus!ka (shorter path)
gsmith@brahms.BERKELEY.EDU (Gene Ward Smith) (02/12/86)
In article <1133@mmintl.UUCP> franka@mmintl.UUCP (Frank Adams) writes: >We seem to agree that there are three at least somewhat important identities. > >1) (a/b)*b + a%b = a >2) (a+b)%b = a%b or (a+b)/b = a/b + 1 >3) (-a)%b = -(a%b) or (-a)/b = -(a/b) > >Now, in fact, (3) in the division form is important. The area I know of >where it is important is in financial applications. Suppose I own 200 >shares of stock, which I purchased at a total cost of $2,098.75, including >commission. I now sell 100 shares. I have to compute the cost basis for >those 100 shares: $1,049.38. Now, suppose I had a short position with the >same cost basis: -$2,098.75. If I buy back half of these, the rounding >has to be done the same way: -$1,049.38. > >Of course, this application is not rounding toward zero; it is rounding >to the *nearest* penny. So what we want for this application is to round >to the nearest integer, with 1/2 rounded away from zero. This choice is >very common in financial applications. (By the way, financial applications >fairly often divide by negative numbers.) > >There are also a lot of number theoretic algorithms which run faster if >the least absolute remainder is used; I once heard a professor of >mathematics (Hans Zassenhaus, if memory serves) state that the least >absolute remainder is what computer division *should* return. > The ususal definition in elementary number theory texts, etc. is that the remainder be positive. For many purposes, it does not matter what the range of the remainder function is *AS LONG AS IT IS CONSISTENT*. The way "%" has of flipping around to a negative range for negative numbers is the incredibly inconsistent and annoying feature I object to. As far as nearest integer vs. positive goes, some times one wants one, sometimes the other, and ususally either will do as long as things are kept consistent. >I believe that computers (CISC) and programming languages should provide >at least three different division and remainder operations: round towards >0, round towards -infinity, and round to nearest (with 1/2 rounded away >from 0). There is something to be said for round away from zero, and >round to +infinity, as well. I have no objection, but *always* there should be one non-screwed-up definition. ucbvax!brahms!gsmith Gene Ward Smith/UCB Math Dept/Berkeley CA 94720 ucbvax!weyl!gsmith "When Ubizmo talks, people listen."
jeff@gatech.CSNET (Jeff Lee) (02/12/86)
>[Whether CS people should even be *allowed* to make such mathematical >decisions is another question. I am afraid that I must rank this statement right up there with the statement that was made about a year ago that only computer scientists should be the people allowed to program. Being a computer scientist with an interest in math, I find in both statements some of the most ignorant and arrogant attitudes that I have seen just about anywhere (in a professional situation). I suppose that you also believe that only professional mechanics should work on your car, that professional drivers should drive it, that architects should be the only people allowed to design your house, or that professional cooks should be the only people allowed to cook your meals? I am afraid that I do all these things and will continue to do so. If you really believe that statement that you made, I would expect you to start giving your programming work to professional programmers who are trained in this sort of thing... -- Jeff Lee CSNet: Jeff @ GATech ARPA: Jeff%GATech.CSNet @ CSNet-Relay.ARPA uucp: ...!{akgua,allegra,hplabs,ihnp4,linus,seismo,ulysses}!gatech!jeff
jst@abic.UUCP (Shack Toms) (02/13/86)
> In article <731@abic.UUCP> jst@abic.UUCP (Shack Toms) writes: > >However: One might use a%b<0 iff a<0 in an algorithm which printed > >the value of an integer in a given radix. The least significant > >digit of a in radix b would then be |a%b|. :-) > > So would |a|%b, and it works under either convention. :-) Except that |a| is not available for the full range of a. In particular, on a 16 bit computer |-32768| is not expressible. The real point [of the :-)] is that it is just as easy to correct the result of a%b in the range [0..b) as it is to perform the absolute value function. That is: result = a%b; if (result < 0) result = -result; is no easier than result = a%b; if (a < 0) result = b - result; Shack Toms
jimc@ucla-cs.UUCP (02/14/86)
In article <561@jplgodo.UUCP> steve@jplgodo.UUCP (Steve Schlaifer x3171 156/224) writes: >If you think of % as returning the *mathematical* remainder of a/b then >it should return a value >=0. On the other hand, to be consistent with this >view, the quotient operator (/) will also have to be modified to preserve >the formulae > > b=qa+r (0<=r<a) > q=b/a > >i.e. (-3)/2 must be -2 if (-3)%2 is 1. But this then means that (|a|)/b is not >the same as |a/b| for a<0. Maybe *An Angry Number Theorist* wants this, but... > Right on! Invariably when I integer-divide negative numbers I have to do fancy coding to cause (-3)/2 to come out -2 rather than -1. I would very much like to see the quotient of *signed* integers come out this way auto- matically. However, most hardware doesn't cooperate, necessitating extra compiled code. I hope the compiler would have a separate, more efficient code macro for the unsigned case, so that users concerned with efficiency and knowing about their hardware could avoid useless overhead by declaring unsigned ints. This kind of efficient compilation would be helped if all int constants were automatically unsigned. In other words, the compiler would interpret -5 as (unary negate operator)(cast to signed)(unsigned int ={5}). James F. Carter (213) 206-1306 UCLA-SEASnet; 2567 Boelter Hall; 405 Hilgard Ave.; Los Angeles, CA 90024 UUCP:...!{ihnp4,ucbvax,{hao!cepu}}!ucla-cs!jimc ARPA:jimc@locus.UCLA.EDU
gwyn@brl-smoke.ARPA (Doug Gwyn ) (02/14/86)
>... Since >the work involved was massive, I saved the operands, the quotient, >and the remainder. If subsequent calls had the same operands, I >just returned the already-computed values! This is a nice example of a "good idea". It paid off because long division was frequently accompanied by long remainder with the same operands, and the extra bookkeeping overhead per call was more than compensated by the average computational savings. Thanks, Joe. The obvious generalization can be applied in a variety of codes. A conceptually related example is: /* RnNorm -- random normal deviate with specified mean & std. dev. last edit: 86/01/04 D A Gwyn SCCS ID: @(#)rnnorm.c 1.1 Method: Polar method; see Knuth 3.4.1C(1) */ #include <math.h> #include <random.h> /* defines RnFlt() (uniform range) */ #include <std.h> /* defines "bool", "true", "false" */ double RnNorm( mu, sigma ) /* return range (-inf,inf) */ double mu; /* desired mean */ double sigma; /* desired std. deviation */ { static bool saved = false; /* "have saved value" flag */ static double rndsave = 0.0; /* saved value iff `saved' */ double s, x, y; if ( saved ) { x = rndsave; /* already on hand */ saved = false; /* now used up */ } else { /* generate a pair of numbers */ do { x = RnFlt( -1.0, 1.0 ); y = RnFlt( -1.0, 1.0 ); s = x * x + y * y; } while ( s >= 1.0 /* 0.25 probability */ || s == 0.0 /* practically never */ ); rndsave = sqrt( -2.0 * log( s ) / s ); x *= rndsave; rndsave *= y; /* save for next call */ saved = true; } return mu + sigma * x; }
jst@abic.UUCP (Shack Toms) (02/15/86)
[Kenneth Almquist @ Bell Labs, Holmdel, NJ writes (single >)] > > Perhaps K&R thought that the performance penalty of implementing a > > consistent modulus (or divide) was not justified, since negative > > integers are rarely encountered in "C" [this comment cannot be traced > > to K&R.] However, this performance penalty can be avoided simply by > > declaring unsigned integers as "unsigned int". > > On the VAX, the unsigned remainder function is implemented as a > subroutine call. The standard divide instruction cannot be used > because the divide instruction does not work on unsigned integers. Thanks for getting me to check this out! On my VAX using VAXC V2.1, the unsigned division is done with very ugly inline code... Thats ok, but it is incorrect ugly inline code. Seems that it does not correctly perform x%y where x = 0x7fffffff, y = 0xfffffff2. It gets the answer 1, rather than 0x7fffffff. However, the following inline fragment should work ok. clrl r1 movl x,r0 ; load x into r0,r1 as quadword movl y,r2 ; y in r2, set condition codes bgeq 1$ ; y < 2**31, ediv is ok cmpl r2,r0 ; y >= 2**31, we know x < 2*y bgtru 2$ ; y > x ==> x%y == x subl2 r2,r0 ; y <= x < 2*y ==> x%y == x-y brb 2$ ; 1$: ediv r2,r0,r1,r0 ; y in range for ediv, x%y put in r0 2$: ; r0 now contains x%y For signed integers x%y, the following seems about optimal, [this is from the VAXC code (almost)] emul #0,#0,x,r0 ; place x in r0,r1 as signed quadword ediv y,r0,r1,r0 ; r0 now contains x%y Comparing the two fragments, the code for the unsigned divide will probably run about as fast as the code for the signed divide, so long as the value of y is less than 2**31. This is because the VAX lacks not only an unsigned divide, but also a signed longword to quadword conversion (except for the trick with emul). And the signed modulus instruction (ediv) requires a quadword dividend. The clear winner in all of this is probably x%y, where x is unsigned and y is a short (either signed or unsigned). The code is then: clrl r1 movl x,r0 ; Unsigned x in r0,r1 movzwl y,r2 ; Unsigned short y in r2 (cvtwl for short y) ediv r2,r0,r1,r0 ; r0 contains x%y But enough of implemention details... > In Ada, division truncates towards zero, and there are separate > remainder and modulo operators. The % operator in C is a remainder > operator; we could have a new operator %% for modulo. (On the other > hand, maybe not. We don't want C to get as large as Ada!) I certainly agree with that last remark. You say, however, that the % operator is a remainder operator. Sure, the definition is that a/b can round up or down [except when both a and b are positive], but a/b*b+a%b must equal a. The problem is that this selection of properties is shared by at least 8 possible funcions from Z X Z --> Z. Indeed, there may be many more than 8 functions. As I read my K&R there is nothing wrong with a compiler evaluating division of constants (constant folding) in a different manner from the run-time evaluation of the same values. Furthermore, the preprocessor may evaluate division in compile time expressions (say in #if statements) using a different algorithm. (These possibilities are probably greater with cross-compilers). Furthermore, if the denominator is a constant power of two, then the compiler might generate shifts and masks, and produce a result different from that of a division of the same values had they both been stored in variables. Similarly, for certain values of the numerator, the division can be optimized into a comparison with a result generated according to its own rule. The requirement seems to be only that, in each case, the a/b*b+a%b == a rule must hold. That is, whenever an optimization can be made for an expression involving "/", that the corresponding optimization also must be made for "%". Giving this operator a simple name ("remainder operator") belies its fundamental ambiguity. A very simple solution, which is upward compatible with the current language definition, is to define division to always round in a precise way, and then to keep % as the remainder function. That way, the language need not be cluttered with a %% operator. The problem is to choose that definition which has the most widespread application. Now to get back to the original subject [which way to round], in my opinion the most useful of these eight choices for division is made by adding the constraint that the sign of any non-zero remainder should be equal to the sign of the divisor. My experiences have led me to believe that this is the most convenient choice. These experiences were gained largely using languages which do integer division equivalently to: a/b = trunc(float(a)/float(b)) (i.e. the "wrong" way). *Whenever* I have sought the result of a%b with b>0, I have wanted the smallest non-negative remainder, regardless of the sign of a. The symmetric choice is to then have the sign of a%b determined by the sign of b. This choice may lead [as would any choice] to [marginally] increased overhead on machines which have asymmetric support for signed vs. unsigned integers, but it is no secret that C runs best on machines with symmetric architectures.
jst@abic.UUCP (Shack Toms) (02/18/86)
> [ Thomas Spencer writes...] > There is of course, always another way to look at it. The '%' operator > is not defined to be MOD, it is defined such that > (a/b)*b + a%b = a > In other words, it is the REMAINDER upon dividing a by b. Now, if you > want a%b to always be positive, you must then have > (-a)/b != -(a/b) > which, I think you will agree, is much worse.... This property [(-a)/b == -(a/b)] is *not* guaranteed by the definition of % in C. An implementation of C is free to return nonnegative remainders, so long as the implementation of / rounds toward -infinity. This property does not seem all that precious to me, though. Anyone who writes code which utilizes the entire range of int soon learns not to be too cavalier with negation, since the range of int is not always symmetric about 0. > ... If you really want MOD, > here it is: > mod(a,b) > { > return (( a % b ) + b) % b; > } And if you really want quotients to round toward 0 and negative remainders [although I believe this is desired less frequently] you had better write those too.
cottrell@NBS-VMS.ARPA (COTTRELL, JAMES) (02/19/86)
/* > I have no objection, but *always* there should be one non-screwed-up > definition. I looked in the C manual expecting to find the following caveat: " The % operator is whatever is left in the `remainder' register by the particular divide instruxion used on the host computer" It was not there. As a working definition, consider it said. I too prefer the positive remainder definition. However, as Walter Cronkite would say, "And that's the way it is". Programming around that fact can be done trivially & portably. Nuff Said, jim cottrell@nbs */ ------
weemba@brahms.BERKELEY.EDU (Matthew P. Wiener) (02/19/86)
In article <736@abic.UUCP> jst@abic.UUCP (Shack Toms) writes: >> In article <731@abic.UUCP> jst@abic.UUCP (Shack Toms) writes: >> >However: One might use a%b<0 iff a<0 in an algorithm which printed >> >the value of an integer in a given radix. The least significant >> >digit of a in radix b would then be |a%b|. :-) >> >> So would |a|%b, and it works under either convention. :-) > >Except that |a| is not available for the full range of a. In >particular, on a 16 bit computer |-32768| is not expressible. I don't know about you, but I'm too paranoid about the least negative number to begin with. In fact, I try not to get close, if possible. Frankly, if it's a question of a language getting integer division done correctly on -32767 to 32767 or getting it done incorrectly on -32768 to 32767, I think there is no debate about which is preferable. Or, to express my point in less prejudicial terms: in arguing A vs B in a language, the question of what happens with the least negative number is almost always irrelevant. >The real point [of the :-)] etc. Agreed etc. Personal to Shack Toms- I got mail asking me to keep this issue off of net.arch. As you reposted to net.arch, I wonder if you did? As it is, I'm sending this up to net.lang, since it is not really a C specific question. ucbvax!brahms!weemba Matthew P Wiener/UCB Math Dept/Berkeley CA 94720
pete@valid.UUCP (Pete Zakel) (02/28/86)
> Is there someone out there who *wants* a/b to round towards 0 (for reasons > that say that is the desired result)? I asked that before and have not seen > any affirmatives. > > ucbvax!brahms!weemba Matthew P Wiener/UCB Math Dept/Berkeley CA 94720 I do! Mainly because I want the absolute value of (-a)/b to equal the absolute value of a/b. -- -Pete Zakel (..!{hplabs,amd,pyramid,ihnp4}!pesnta!valid!pete)
cottrell@NBS-VMS.ARPA (COTTRELL, JAMES) (03/05/86)
/* > > Is there someone out there who *wants* a/b to round towards 0 (for reasons > > that say that is the desired result)? I asked that before and have not seen > > any affirmatives. > > > > ucbvax!brahms!weemba Matthew P Wiener/UCB Math Dept/Berkeley CA 94720 > > I do! Mainly because I want the absolute value of (-a)/b to equal the absolute > value of a/b. > -- > -Pete Zakel (..!{hplabs,amd,pyramid,ihnp4}!pesnta!valid!pete) Me too. Conceptually, `a/b' is `how many times does b go into a'? What is left over has the same sign as the dividend. It seems that most previously built computers truncate towards zero. Ironically, I also prefer that `a%b' be positive, so that the `%' operator is actually the `modulus' rather than the remainder. Thus we have the contradiction that `a != (a/b)*b + (a%b)' for all possible a & b. But, as previously noted, mostly we do `%' on positive integers. Of course, if b is a power of two, you can just `&' with `b - 1' to get the real modulus. jim cottrell@nbs */ ------