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
msb@lsuc.UUCP (Mark Brader) (01/31/86)
[Sorry about repeating 20-odd lines, but I needed the equation numbers] Tim Smith (tim@ism780c.UUCP) writes in net.math: > A recent discussion on net.arch raised the problem of defining integer > division for negative numbers. Most computers seem to say that -3/2 is > -1, and -3%2 is -1. Many people thought this was fine, but some of us > think that -3/2 should be -2, and -3%2 should be 1. Both sides agree > that integer division on computers must be defined to satisfy > > (1) (a/b)*b + a%b = a. > > Everyone agreed that for positive a and b, a/b should round toward zero. > The people who want -3/2 to be -1 argue that the following should hold: > > (2) (-a)/b = -(a/b). > > Those of us who want -3/2 to be -2 want the following to hold: > > (3) a%b for positve b has a range of [0,b-1], not [-b+1,b-1], and > (4) (a+b)/b = a/b + 1. > > 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... > > ... when I was a math major my major interest was number theory, where > (3) and (4) are more useful than (2). I'm going to answer this from a software person's point of view (and therefore I'm cross-posting back to net.arch, which I don't read). When I do an "integer division" operation, (2) is important to me. I want the operation of dividing and then truncating at the decimal point. I hardly ever want the remainder as well as the quotient, and *when I do*, the dividend is always *positive*. When I do a % operation, I may be doing one of two things. I may want the remainder that goes with the division I just did -- in which case, as I say, the dividend is, in my experience of cases of interest, always positive. Or I may want to do the mathematical operation of taking the modulus, which is expressed by (3); and in that case, the "dividend" may be negative or positive. This puts me squarely in the *third* camp. I want (2) *and* (3), and I don't give a dam~ about (1) for negative dividends. So I want -3/2, or rather (-3)/2, to be -1, and (-3)%2 to be +1. I must make one hardware-type comment: I think one argument, perhaps unconscious, in favor of (1) is that computers (the ones I know, anyway) compute quotient and remainder simultaneously. To this I say, yes, but why should they do that anyway? Few languages have DIVIDE X BY D GIVING Q REMAINDER R., and most often the second computed value is unused anyway. I see no reason that this tradition should give extra weight to (1). Mark Brader
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 afterward
weemba@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.
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 Neal
thomas@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 Toms
aglew@ccvaxa.UUCP (02/06/86)
I just thought that it might be worthwhile pointing out that what people are arguing about is not an architectural issue but a linguistic issue. If you are annoyed that you have to write something stupid like a = b % c; if( a < 0 ) a += c; because of the way your math library does % (call it modulo, call it remainder - I don't care) then you can always define it as a function, say, a = positive_mod(b,c). Don't like that? Then what you want is a language that lets you define your own infix operators. Try Ada. The only architectural question here is - what should the actual hardware support, if it has a MOD instruction? I don't think that there are any hardware issues here - I don't know of any circuits that do a good job of implementing an arbitrary MOD - and, unfortunately, under neither scheme could we get away with only one instruction for both signed and unsigned arithmetic. Have I missed anything? And, please, let us talk about architecture, not interior decorating.
earl@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.
ken@turtlevax.UUCP (Ken Turkowski) (02/10/86)
In article <685@brl-smoke.ARPA> gwyn@brl.ARPA writes: >(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.) You'll be glad to know that the 68881 returns BOTH the sine and cosine with a 15% timing penalty over just sine. -- Ken Turkowski @ CIMLINC, Menlo Park, CA UUCP: {amd,decwrl,hplabs,seismo,spar}!turtlevax!ken ARPA: turtlevax!ken@DECWRL.DEC.COM
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}
tim@ism780c.UUCP (Tim Smith) (02/10/86)
In article <5100003@ccvaxa> aglew@ccvaxa.UUCP writes: > >The only architectural question here is - what should the >actual hardware support, if it has a MOD instruction? The architectural issue is how should division round. The behaviour of the MOD function is just a side effect of how division rounds. Thus, the architectural issue is which of the following is best: 1. round toward zero 2. round toward -infinity 3. round toward +infinity 4. round to closest integer ( have I left any out? ). 1 and 2 are the ones most people consider reasonable. With 2 we have arithmetic shift right and division by two are the same ( on a "normal" machine ), and a - (a/b)*b is the mod function. -- Tim Smith sdcrdcf!ism780c!tim || ima!ism780!tim || ihnp4!cithep!tim
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.
bmw@aesat.UUCP (Bruce Walker) (02/11/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 Yes, *I* want a/b to round toward 0, and for a good (although selfish) reason. (I also want divide to produce *both* result *and* remainder which answers a question posed by someone else on just that point.) When I write the firmware for the disk controller boards I design, I want that code to run as fast as possible (so do you, if your machine uses my board!). When a logical block address is handed to me, I do an integer divide by the number of sectors per track which produces both a quotient and remainder. The quotient will represent the track I should seek, and the remainder represents the sector I should read. No extra work is done, and all the micros I would normally use for this kind of purpose do what I expect. The above algorithm is simplified of course, one would normally have to consider bad-block management etc., but the principle remains intact. So, if as a result of this discussion, every uP manufacturer ups and "fixes" his microcode, don't come crying to me that all your disk reads take 20 more microseconds than they used to. Bruce Walker {allegra,ihnp4,linus,decvax}!utzoo!aesat!bmw "I'd feel a lot worse if I wasn't so heavily sedated." -- Spinal Tap
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
paulr@decwrl.UUCP (02/13/86)
This message is empty.
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
herndon@umn-cs.UUCP (02/14/86)
If all of you would like a little light on the subject (for practical applications), there was an article (or rather a few of them) in SIGPLAN Notices about a year or so ago. Robert Herndon ...!ihnp4!umn-cs!herndon
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
tim@ism780c.UUCP (Tim Smith) (02/14/86)
In article <557@aesat.UUCP> bmw@aesat.UUCP (Bruce Walker) writes: > >Yes, *I* want a/b to round toward 0, and for a good (although selfish) >reason. (I also want divide to produce *both* result *and* remainder >which answers a question posed by someone else on just that point.) > >When I write the firmware for the disk controller boards I design, I >want that code to run as fast as possible (so do you, if your machine >uses my board!). When a logical block address is handed to me, I do an >integer divide by the number of sectors per track which produces both a >quotient and remainder. The quotient will represent the track I should >seek, and the remainder represents the sector I should read. No extra >work is done, and all the micros I would normally use for this kind of >purpose do what I expect. > If your logical block numbers are >= 0, and your disks have a positive number of sectors per track, then round toward zero and round toward negative infinity are the same. If you were given a relative block number to seek to, say N blocks from the start of the current track, then N might be negative. In this case you would also want to round to negative infinity. For example, if we have 16 sectors per track, and want the logical sector -13 from the start of the current track, we want -13/16 = -1, and -13%16 = 3, so we go back one track and read sector 3. With round toward zero, we would get -13/16 = 0, -13%16 = -13, thus we try to read sector -13 of the current track. -- Tim Smith sdcrdcf!ism780c!tim || ima!ism780!tim || ihnp4!cithep!tim
taylor@glasgow.UUCP (02/17/86)
During my undergraduate days, one of the Great Men who taught us suggested, seriously I think, that rounding should be up OR down AT RANDOM, with a 50/50 chance. This would remove systematic errors introduced by rounding in iteractive algorithms. ( which way do you round 0.5 is the hardest question; 0.5000001 and 0.4999999 are much easier.) -Jem. #include <disclaimer.h>
jimc@ucla-cs.UUCP (02/18/86)
In article <557@aesat.UUCP> bmw@aesat.UUCP (Bruce Walker) writes: >| Is there someone out there who *wants* a/b to round towards 0 (for reasons >| ucbvax!brahms!weemba Matthew P Wiener/UCB Math Dept/Berkeley CA 94720 > >Yes, *I* want a/b to round toward 0, and for a good (although selfish) >reason. (I also want divide to produce *both* result *and* remainder >which answers a question posed by someone else on just that point.) > >...When a logical block address is handed to me, I do an >integer divide by the number of sectors per track ... "Round" is a misnomer. I think the problem is, if the logical block number is negative, should the answer be made more or less positive? In other words, in (-16)/7 do you want the answer to be -2 or -3? I don't think I have ever had a situation where it mattered -- but remaindering is closely related, and it *does* matter there. Do you want (-16)%7 to be -2 or +5? In your disc example I think you would rather be on sector +5, track -3 rather than sector -2 track -2. Similarly for circular caches, hash tables, etc.etc. One point, though: most divisions and remainderings are of known-to-be positive quantities, and we want to avoid adding useless overhead to check unsigned quantities for being negative. It would be best if the hardware would let the remainder have the sign of the divisor, whatever the dividend is. (Ask for the moon and they might give it to you.) 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
rentsch@unc.UUCP (Tim Rentsch) (02/20/86)
In article <17200003@umn-cs.UUCP> herndon@umn-cs.UUCP writes: > >If all of you would like a little light on the subject >(for practical applications), there was an article (or >rather a few of them) in SIGPLAN Notices about a year >or so ago. > > Robert Herndon > ...!ihnp4!umn-cs!herndon Which underscores the point that this is a language issue, NOT an architecture issue. Please, no more integer division articles on net.arch newsgroup. Other posters have moved to net.lang newsgroup; go thou and do likewise. grumble, Tim Rentsch
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)