Odd numbers
Dave Giunti
RS>From: R.Smi...@ee.surrey.ac.uk (Russell Smithers)
RS>Date: 6 Aug 91 09:31:54 GMT
RS>Organization: University of Surrey, Guildford, England GU2 5XH.
RS>Message-ID: <1991Aug6.0...@EE.Surrey.Ac.UK>
RS>Newsgroups: comp.lang.c
RS>
RS>Ok heres a few things that I came up with last night.
RS>
RS>1. Whats the best way of finding out if x is odd or even?
RS>2. What different ways are there of doing so?
RS>3. using the expression (x % 2) == 0 being true evaluates to an Even number!
RS> Using this expression 0 is an Even number?
RS>4. Is 0 an even number?
Yes 0 should be defined as even.
The fastest and likely most portable test is simply:
if ( x & 1)
printf("It is odd);
else printf("Since there is no 1 in the ones place it's even!");
Happy Computing
Dave
* EZ 1.33 *
--
Dave Giunti - via RBBS-NET node 8:914/201
INTERNET: Dave....@p0.f217.n914.z8.RBBS-NET.ORG
Stan Brown
> Yes 0 should be defined as even.
> The fastest and likely most portable test is simply:
>
> if ( x & 1)
> printf("It is odd);
> else printf("Since there is no 1 in the ones place it's even!");
This is quite UNportable. For instance, if x < 0 and the machine happens
to be a ones complement machine, (x & 1) will likely give the wrong
answer.
--
Stan Brown, Oak Road Systems, Cleveland, Ohio, USA +1 216 371 0043
email: br...@ncoast.org -or- ap...@cleveland.freenet.edu
"I'll admit I've seen better days, but I'm still not to be had for the price
of a cocktail, like a salted peanut." --All About Eve
Ed de Moel
>In article <750.28...@wyrm.rbbs-net.ORG> Dave....@p0.f217.n914.z8.RBBS-NET.ORG (Dave Giunti) writes:
>> Yes 0 should be defined as even.
>> The fastest and likely most portable test is simply:
>>
>> if ( x & 1)
>> printf("It is odd);
>> else printf("Since there is no 1 in the ones place it's even!");
>
>This is quite UNportable. For instance, if x < 0 and the machine happens
>to be a ones complement machine, (x & 1) will likely give the wrong
>answer.
with the programming techniques I've seen.
The definition of 'being even' is 'leaving no remainder when
divided by two'. The C-way of finding out about remainders is
through the % operator.
Hence, by definition, even(x) is equal to !(x%2).
Or, odd(x) being !even(x), by definition is equal to (x%2).
Programs tend to be regarded as 'better' and 'easier to maintain'
when the code is closer to the definition of what is supposed to be happening.
Bit-manipulations are tricks that sometimes give the same results,
but they are tricks, and should be avoided if portability is important.
Ed.
Peter Richards
|> with the programming techniques I've seen.
|>
|> The definition of 'being even' is 'leaving no remainder when
|> divided by two'. The C-way of finding out about remainders is
|> through the % operator.
|>
|> Hence, by definition, even(x) is equal to !(x%2).
|> Or, odd(x) being !even(x), by definition is equal to (x%2).
|>
|> Programs tend to be regarded as 'better' and 'easier to maintain'
|> when the code is closer to the definition of what is supposed to be happening.
|>
|> Bit-manipulations are tricks that sometimes give the same results,
|> but they are tricks, and should be avoided if portability is important.
|>
|> Ed.
This is true I guess, but I think I remember reading somewhere that the
*actual* remainder that is returned (for negative dividends) is
machine-dependent. If this is true, you still need to watch out with other moduli and negative numbers. For example, what is (-10) % 3 ? If one depends
on an analogy with moduli in mathematics it should be 2, but (maybe?)
depending on your implementation you could get -2 or something.
If I'm totally hallucinating about this implementation-dependence of negative
args to the % operator, let me know please
Pete Richards
pi...@kashmir.esd.sgi.com
Ed de Moel
>
>If I'm totally hallucinating about this implementation-dependence of negative
>args to the % operator, let me know please
>
operation and the 'remainder of a division'.
When both operands (or parameters) are positive, the result is the same.
The remainder of -7 / 3 is seen by most people as -1. The function
'modulus' reduces the set of numbers to a subset that repeats cyclically:
To keep with the example of 3:
0 1 2 0 1 2 0 1 2 0 1 2 0 1 2
-6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8
(This definition is the one that my algebra teacher gave me.
I am aware that some compilers or run-time systems generate
different results. I believe that those systems are mathematically
incorrect).
In the case of 'odd' and 'even', however, the difference between
modulus and remainder should play no role, since 'even' was
defined as 'when the modulus is zero'.
Ed.
Kevin D. Quitt
>
>If I'm totally hallucinating about this implementation-dependence of negative
>args to the % operator, let me know please
In K&R, % is called the "modulus operator", whereby the results
should always be positive. On the other hand, in both sections 2.5 and
A7.6, it clearly states that % yields the remainder after the division.
Hey Karl, you out there?
--
_
Kevin D. Quitt srhqla!venus!kdq kdq%ve...@sr.com
3D systems, inc. 26081 Avenue Hall Valencia, CA 91355
VOICE (805) 295-5600 x430 FAX (805) 257-1200
96.37% of all statistics are made up.
Chris Torek
>The remainder of -7 / 3 is seen by most people as -1 [but -7 mod 3 = 2].
>... (This definition is the one that my algebra teacher gave me.
>I am aware that some compilers or run-time systems generate
>different results. I believe that those systems are mathematically
>incorrect).
This statement is far too strong. C's % operator is not `modulus' but
rather `remainder'---despite common nomenclature---and in many cases you
*do* want -7%3 to give -1. (Note that -1 is congruent to 2 mod 3.)
When -7 / 3 is -2, the remainder is -1, but when -7 / 3 is -3, the
remainder is 2. Some machines give one answer, some give the other;
some give both (depending on a mode, or on which instructions you use);
C requires only that, given nonzero b, ((a/b)*b + (a%b)) equal a.
Thus, the C implementor can choose whichever the machine does best.
>In the case of 'odd' and 'even', however, the difference between
>modulus and remainder should play no role, since 'even' was
>defined as 'when the modulus is zero'.
Indeed: and if odd is taken as `not even', rather than `congruent to
1 mod 2', the fact that machine arithmetic is loosely defined is less
important.
I noted all of this some time ago, and do not understand why the issue
has resurfaced.
--
In-Real-Life: Chris Torek, Lawrence Berkeley Lab CSE/EE (+1 415 486 5427)
Berkeley, CA Domain: to...@ee.lbl.gov
new area code as of September 2, 1991: +1 510 486 5427
Paul Potts
>In article <342...@MVB.SAIC.COM> Dem...@Fwva.Saic.Com (Ed de Moel) writes:
>>The remainder of -7 / 3 is seen by most people as -1 [but -7 mod 3 = 2].
>>... (This definition is the one that my algebra teacher gave me.
>>I am aware that some compilers or run-time systems generate
>>different results. I believe that those systems are mathematically
>>incorrect).
>
>This statement is far too strong.
I agree. In a programming language class I once took, one of our assignments
was to find out how MOD worked with negative numbers, in as many different
languages as possible. We used Forth, Pascal, Modula-2, a couple of
implementations of C, HyperTalk, etc. There was no consistency at all.
It seems to be one of those things that ought to best be called
"implementation-dependent."
Paul Potts
po...@itl.itd.umich.edu
Ed de Moel
>In article <17...@dog.ee.lbl.gov> to...@elf.ee.lbl.gov (Chris Torek) writes:
>>In article <342...@MVB.SAIC.COM> Dem...@Fwva.Saic.Com (Ed de Moel) writes:
>>>The remainder of -7 / 3 is seen by most people as -1 [but -7 mod 3 = 2].
>>>... (This definition is the one that my algebra teacher gave me.
>>>I am aware that some compilers or run-time systems generate
>>>different results. I believe that those systems are mathematically
>>>incorrect).
>>
>>This statement is far too strong.
>
>I agree.
operation on numbers. Some computer languages implement that operation,
but produce a result that is not conform the mathematical definition.
I don't see what's so 'strong' about my statement: wrong is wrong,
that is a simple fact.
Blair P. Houghton
>It seems to be one of those things that ought to best be called
>"implementation-dependent."
The fact is that modulus and remainder are two different
things, and each should be defined in a language so that
together they give a programmer access to both definitions.
The mathematical definition of modulus is along the lines
of (I left my Knuth at home, so pardon me if I cock this up...)
x mod y = z if and only if z is a nonnegative
integer and there is a nonnegative integer q
such that q*y + z = x.
Remainder is defined like
If x and y are real numbers and y is not zero,
then the remainder z of the quotient x/y is a
real number and
z = x - y * floor(x/y) , x/y > 0;
z = x - y * ceil(x/y) , x/y < 0;
z = 0 , x/y = 0;
If y is zero then the value of z is undefined.
Where floor() is "greatest integer less than or equal to",
and ceil() is "least integer greater than or equal to".
The case where x, y, and z are integers is a direct result.
(ANSI X3.159-1989 provides remainder in `fmod()', but
leaves the integer remainder `%' open, refusing to specify
the sign when either operand is negative; and it completely
ignores modulus operators. It adds a hack called `modf()',
referred to disingenuously in the index as the "modulus
function", which merely splits a double into integer and
fractional parts, retaining the argument's sign in both).
--Blair
"Where's the APL character set
when you _really_ need it?"
Chris Torek
>... I believe that those systems are mathematically incorrect ...
In article <17...@dog.ee.lbl.gov> I wrote:
>>>This statement is far too strong.
In article <348...@MVB.SAIC.COM> Dem...@Fwva.Saic.Com (Ed de Moel) replies:
>My statement is that there is a mathematical definition of a certain
>operation on numbers. Some computer languages implement that operation,
>but produce a result that is not conform the mathematical definition.
>
>I don't see what's so 'strong' about my statement: wrong is wrong,
>that is a simple fact.
But the computer languages do not even *claim* to `implement that
operation': even K&R-1 notes that the `%' operator, which is often
called modulus, is actually a remainder operator and is only
*associated with* modulus and congruence---not *defined as*.
As the old saying goes, calling a tail a leg does not make it one.
In another sense, the phrase `mathematically incorrect' is largely
meaningless. For instance, 9 + 9 = 18, but 9 + 9 = 12, and 9 + 9 = 8.
All three of those are true: the first for natural numbers and
supersets, in base 10; the second, for the same in base 16; the third,
for a ring defined over the set of integers [0..9].
Mathematics is not about reality. There is something fundamentally
mysterious about the fact that mathematics can be used to *describe*
reality (with varying success). This makes it all very interesting,
but in mathematics, you choose your axioms and go from there, and if it
happens to apply to some field---including computing---that is more an
`intentional accident' rather than some sort of divine law.
You might as well say that, because planetary motion does not quite
obey Newtonian physics, it is `physically wrong'. There is a flaw in
the match, to be sure, but the `wrongness' is in the application of
of an `unreal' mathematics or physics to a `real' phenomenon.
You may claim that this is sheer sophistry (and some of it is :-) ),
but holding computer languages to a narrow subset of mathematics is
not a particularly profitable tack.
Ed de Moel
>In article <1991Aug29....@terminator.cc.umich.edu> po...@us.cc.umich.edu (Paul Potts) writes:
>>It seems to be one of those things that ought to best be called
>>"implementation-dependent."
>
>The fact is that modulus and remainder are two different
>things, and each should be defined in a language so that
>together they give a programmer access to both definitions.
>
sine, cosine, or modulus, needs to be found in math-books, not
in programming documentation.
I have received some flames for thinking this way, because I'm
calling implementations 'wrong' when they produce a result that
would be 'unexpected' according to math. It seems that nobody
finds fault with me when I say this about a sine function that
returns 1.5 in some cases, but I have a hard time obtaining any
sympathy when the modulus function/operator is involved.
Am I being obnoxious, or am I missing the point, or are other people
missing the point?
Ed.
Paul Potts
>bhou...@hopi.intel.com (Blair P. Houghton) writes:
>My opinion is that the definition of mathematical functions like
>sine, cosine, or modulus, needs to be found in math-books, not
>in programming documentation.
>I have received some flames for thinking this way, because I'm
>calling implementations 'wrong' when they produce a result that
>would be 'unexpected' according to math.
I agree that you are technically correct: a function which calls itself
"modulus" should return a mathematica mod() and should just work correctly.
On the other hand, computers have always taken liberties with mathematical
concepts, on the grounds that things like internal number representations
must represent a compromise between accuracy and speed, and I guess I've
just about gotten used to that kind of tradeoff. It just means that things
have to be very well documented. I am not opposed to using a quick "mod"
function which generates correct results only for integers >= 0, but it
should be very clear before I use it that these are the constraints.
C in particular is full of these tradeoffs - consider "strcpy." It works
beautifully and compiles to a very few instructions, but if you pass it
a string without a terminating zero, it can wreak havoc.
I too would be quite upset with a "sin" function that returned incorrect
results - that's why things like Apple's SANE libraries were created.
Mod on the other hand is generally used with integers. Maybe there should
be a better mod function available with the math libraries that works on a
full set of values. In my compiler, THINK C, there is a floating-point mod.
Then the distinction becomes which function to use. It is like the difference
between multiplying using a left shift << and using the regular multiplicative
operand. One is quick-and-dirty and works only with powers of two, one isn't.
-Paul Potts-
po...@itl.itd.umich.edu
Lance Bresee
>In article <348...@MVB.SAIC.COM> Dem...@Fwva.Saic.Com (Ed de Moel) writes:
>>bhou...@hopi.intel.com (Blair P. Houghton) writes:
>
>>My opinion is that the definition of mathematical functions like
>>sine, cosine, or modulus, needs to be found in math-books, not
>>in programming documentation.
>>I have received some flames for thinking this way, because I'm
>>calling implementations 'wrong' when they produce a result that
>>would be 'unexpected' according to math.
>
>I agree that you are technically correct: a function which calls itself
>"modulus" should return a mathematica mod() and should just work correctly.
Just out of curiosity,
has anyone considered that,
-6 % 5 = -1 in c,
and -6 modulo 5 is 4,
but -1 = (modulo 5) 4.
ie % returns mathematically correct
values, but just does not return the
isomorphic copy of the result within
the group Z(n) for modulo n?
Joe W Wright
"The binary % operator yields the remainder from the division of
the first expression by the second". "On all machines covered by
this manual, the remainder has the same sign as the dividend".
"It is always true that (a/b)*b + a%b is equal to a (if b is not
0)". "The operands must not be 'float'".
a b a/b a%b (a/b)*b + a%b == a
7 3 2 1 2 * 3 + 1 == 7
7 -3 -2 1 -2 * -3 + 1 == 7
-7 3 -2 -1 -2 * 3 + -1 == -7
-7 -3 2 -1 2 * -3 + -1 == -7
If you don't get these results, your library's broke (I know mine
was). Note there is no reference to 'modulus' in the definition.
Joe Wright al...@cup.portal.com
Andrew Koenig
> Just out of curiosity,
> has anyone considered that,
> -6 % 5 = -1 in c,
Actually, -6 % 5 is either -1 or 4 in C.
--
--Andrew Koenig
a...@europa.att.com
Chris Torek
>My opinion is that the definition of mathematical functions like
>sine, cosine, or modulus, needs to be found in math-books, not
>in programming documentation.
I doubt anyone will argue with this (at least, not very successfully :-) ).
>I have received some flames for thinking this way, because I'm
>calling implementations 'wrong' when they produce a result that
>would be 'unexpected' according to math.
Such an implementation is wrong *only if it claims to do something
and fails*.
>It seems that nobody finds fault with me when I say this about a
>sine function that returns 1.5 in some cases ...
Such a function is (by definition) not a `sine function' ... but such a
function may well still be useful---perhaps it produces results which
differ from sin(x) by no more than 2 ulps% except when x exceeds 1E+305
---and may appear in some language. It cannot be faulted for producing
1.5 *unless it claims otherwise*.$
-----
% A `ulp' is a `unit in last place', i.e., for floating point, the tail
end bits of the fraction. It is common, though not necessarily
desirable, for math libraries to give accurate ranges for a limited
domain only. Those who truly understand floating point can explain
it better than I, but it has to do with doing fast argument reduction
so that intermediate expressions do not need excessive precision.
$ Spelling the function `sin' and *not* noting that it fails for large
values of x may constitute an implicit claim that sin(x) approximates
the sine of x for all values of x. Note that sin(x) cannot *equal*
the sine of x for all values of x: for instance, while x=1.0 is
representable in any binary floating point, sin 1 is not; indeed, sin
1 is irrational (I think---I am very rusty at this and am relying on
an informal eyeballing of the Taylor expansion of sin 1, which
appears to require an arbitrarily large number of prime factors in
order to reduce the error to an arbitrarily small epsilon).
-----
>Am I being obnoxious, or am I missing the point, or are other people
>missing the point?
I think people are busy arguing past each other.
Anyway, in C, `a % b' is *not* defined as `a mod b', but rather as `a
remainder b'. Because of that, it is not wrong for a % b to be
negative. If you need a mod b, in C, you must define it yourself. The
situation is rather worse in Pascal, where `a remainder b' is quite
literally spelled `a mod b'. This falls afoul of my second footnote
above, and you are on a stronger footing to call this `wrong'---not
because the a mod b does not compute the correct remainder, but rather
because this remainder function has a highly misleading name. This is
why C's `a % b' should not be pronounced `a mod b'.
house ron
>In article <1991Aug30.1...@terminator.cc.umich.edu> po...@us.cc.umich.edu (Paul Potts) writes:
>>In article <348...@MVB.SAIC.COM> Dem...@Fwva.Saic.Com (Ed de Moel) writes:
>>>bhou...@hopi.intel.com (Blair P. Houghton) writes:
>>
>>>My opinion is that the definition of mathematical functions like
>>>sine, cosine, or modulus, needs to be found in math-books, not
>>>in programming documentation.
>>>I have received some flames for thinking this way, because I'm
>>>calling implementations 'wrong' when they produce a result that
>>>would be 'unexpected' according to math.
>>
>>I agree that you are technically correct: a function which calls itself
>>"modulus" should return a mathematica mod() and should just work correctly.
So it's lucky the ANSI C standard calls it 'remainder' and not 'modulus',
isn't it? Or is that _another_ mistake - it _should_ be modulus, and it
_should_ work like modulus!
Lincoln wus right - you can't please all the people all the time - even
when you're doing nothing wrong.
--
Regards,
Ron House. (s64...@zeus.usq.edu.au)
(By post: Info Tech, U.C.S.Q. Toowoomba. Australia. 4350)
Ed de Moel
>In article <1991Aug30.1...@terminator.cc.umich.edu> po...@us.cc.umich.edu (Paul Potts) writes:
>>In article <348...@MVB.SAIC.COM> Dem...@Fwva.Saic.Com (Ed de Moel) writes:
>>>bhou...@hopi.intel.com (Blair P. Houghton) writes:
>>
>Just out of curiosity,
>has anyone considered that,
>
>-6 % 5 = -1 in c,
>and -6 modulo 5 is 4,
>but -1 = (modulo 5) 4.
>
>ie % returns mathematically correct
>values, but just does not return the
>isomorphic copy of the result within
>the group Z(n) for modulo n?
if it returns 2pi when called for the value 1.0?
Of course, it is not wrong. But I would think that the value 0.0
would be a lot more appropriate...
Ed.
Kevin D. Quitt
>The following "quotes" from K&R 1, p.188. somewhat out of order..
>
>"The binary % operator yields the remainder from the division of
>the first expression by the second". "On all machines covered by
>this manual, the remainder has the same sign as the dividend".
>"It is always true that (a/b)*b + a%b is equal to a (if b is not
>0)". "The operands must not be 'float'".
>If you don't get these results, your library's broke (I know mine
>was). Note there is no reference to 'modulus' in the definition.
The confusion derives from the fact that it is called the modulous
operator, not the remainder operator (At least it is in K&R2 P41 " The
binary arithmetic operators are +, -, *, /, and the modulus operator %."
I don't have the ANSI spec). In fact, in K&R2, there isn't even an
index entry for remainder, only modulus.
Does the ANSI spec drop the "modulus" name? I sure hope so.
Bob Goudreau
>
> The confusion derives from the fact that it is called the modulous
> operator, not the remainder operator (At least it is in K&R2 P41 " The
> binary arithmetic operators are +, -, *, /, and the modulus operator %."
> I don't have the ANSI spec). In fact, in K&R2, there isn't even an
> index entry for remainder, only modulus.
>
> Does the ANSI spec drop the "modulus" name? I sure hope so.
Yup. The index has an entry for "remainder operator, %, 3.3.5", and
that section is pretty clear on the matter: "... the result of the
% operator is the remainder." The only index entry for "modulus" is
in reference to the modf() function of the math library.
----------------------------------------------------------------------
Bob Goudreau +1 919 248 6231
Data General Corporation goud...@dg-rtp.dg.com
62 Alexander Drive ...!mcnc!rti!xyzzy!goudreau
Research Triangle Park, NC 27709, USA
Tony Mountifield
>
> So it's lucky the ANSI C standard calls it 'remainder' and not 'modulus',
> isn't it? Or is that _another_ mistake - it _should_ be modulus, and it
> _should_ work like modulus!
Is 'modulus' even the correct term for what people mean?
When I was at school, the modulus of A was written |A|, and meant the
absolute value (a<0 ? -a : a).
The term for positive remainder was 'modulo', i.e. A modulo 3 meant:
if A = (-3,-2,-1,0,1,2,3,4,5), then A modulo 3 = (0,1,2,0,1,2,0,1,2).
Anyone else agree?
Tony.
--
Tony Mountifield. | Microware Systems (UK) Ltd.
MAIL: to...@mwuk.uucp | Leylands Farm, Nobs Crook,
INET: tony%mwuk...@ukc.ac.uk | Colden Common, WINCHESTER, SO21 1TH.
UUCP: ...!mcsun!ukc!mwuk!tony | Tel: 0703 601990 Fax: 0703 601991
**** OS-9, OS-9000 Real Time Systems **** MS-DOS - just say "No!" ****
Chris Torek
>Is 'modulus' even the correct term for what people mean?
>When I was at school, the modulus of A was written |A|, and meant the
>absolute value (a<0 ? -a : a).
Ah, but you probably put your luggage in the car's boot and remove
pencilled errors with a rubber. :-) (A friend of mine recalls being
rather nonplussed at the latter. Americans generally call these
`erasers'; `rubbers' refer to over-shoe rain-gear and, in slang,
to condoms.)
Seriously, yes, the positive remainder function which we abbreviate as
`mod' is usually expanded as `A modulo 3 equals ...'.
--
In-Real-Life: Chris Torek, Lawrence Berkeley Lab CSE/EE (+1 510 486 5427)
Berkeley, CA Domain: to...@ee.lbl.gov
Doug Moore
I understand the points that both sides have made in this argument. I
personally believe that the world would be a better place if the C
standard said that, for ints a and b,
a/b == floor((float) a, (float) b)
and, as a consequence of the rule
a%b == a - (a/b)*b,
that a%b was always a value between 0 and b-1, inclusive. I have had
to write more complex code from time to time because the world does
not have this property. A simple example is in a circular array
implementation of deques, in which I can write
back++, back %= size;
to extend the back of the deque, but cannot safely write
front--, front %= size;
to pull forward the front of the deque.
In response to someone who argued that any other behavior is
mathematically wrong, I have heard three arguments:
1. It's best the way it is because it's in the standard and changing
the standard is bad.
I reject such arguments.
2. It's best the way it is because the compiler writer should have
the ability to implement the operation whichever way is fastest.
Okay. Is there hardware upon which doing it my preferred way takes
longer than doing it some other way? If so, is it because the
hardware designer made an arbitrary, mathematically ill-considered
decision, or because the preferred way is inherently more complex? If
the former, how can future hardware designers be induced to make
better decisions?
3. There is no best way, because sometimes you want one result and
sometimes the other, so it's best to avoid hampering the compiler
writer.
Okay. Can you present an example in which you want a remainder
operator that behaves some way other than the way I prefer?
I know this is a tired thread, but I've never seen these issues
addressed. If you have answers to offer to these questions, I'd
appreciate them.
I suggest that this issue deserves to be addressed on the FAQ for this
group.
Doug Moore (do...@rice.edu)
Doug Moore
In article <17...@dog.ee.lbl.gov>, to...@elf.ee.lbl.gov (Chris Torek) writes:
|> In article <1991Sep8.0...@rice.edu> do...@rice.edu (Doug Moore) writes:
|> >... I can write
|> > back++, back %= size;
|> >to extend the back of the deque, but cannot safely write
|> > front--, front %= size;
|> >to pull forward the front of the deque.
|>
|> in unsigned arithmetic.
This is false; for example, if unsigneds are six bits, size is 7,
and front is unsigned 0, the effect of
front--, front %= size;
is to change front to 63, then to 0, rather than 6, the intended
result.
|> >If so, is it because the hardware designer made an arbitrary,
|> >mathematically ill-considered decision, or because the preferred
|> >way is inherently more complex?
|>
|> Aside from the slanted wording, I do not know. (Thus, I put this
|> answer in merely to point out that the wording carries a negative
|> connotation.)
Of course the wording is slanted. I have an opinion. I believe that
the current definition can be a source of traps, pitfalls, and
excessively verbose code in some practical applications. If someone
can demonstrate that the definition I advocate would also be a source
of traps, pitfalls, and complex code in practical applications, then
I'll retreat from my belief that my way (and Knuth's way -- I didn't
invent this definition myself) is *the right way*.
I would welcome such a demonstration.
Doug Moore (do...@rice.edu)
Chris Torek
>personally believe that the world would be a better place if the C
>standard said that, for ints a and b,
>
(Actually, this would be bad in some systems, as (int)(float)a is often
not equal to a, as float holds fewer integer bits than int. However...)
C does give you this sort of effect, but only for `unsigned' values.
>... I can write
> back++, back %= size;
>to extend the back of the deque, but cannot safely write
> front--, front %= size;
>to pull forward the front of the deque.
But you can---as long as you make `front' unsigned, or calculate front%size
in unsigned arithmetic.
>... Is there hardware upon which doing it my preferred way takes
>longer than doing it some other way?
Yes; on these machines, doing unsigned remainder is often slower than
doing signed remainder. [It can be faster: if `size' is a power of
two, then (x mod size) is equal to (x & (size - 1)), in two's
complement or unsigned binary arithmetic. This is not the case for
(x remainder size) when the remainder is negative.]
>If so, is it because the hardware designer made an arbitrary,
>mathematically ill-considered decision, or because the preferred
>way is inherently more complex?
Aside from the slanted wording, I do not know. (Thus, I put this
answer in merely to point out that the wording carries a negative
connotation.)
>I suggest that this issue deserves to be addressed on the FAQ for this
>group.
Maybe not: it has not been a frequent topic (merely a noisy one).
Blair P. Houghton
hasn't, so here's some macros that do honest modulus and
honest remainder. Note that they use the `%' operator to
get the job done. I did that out of sheer bloody-mindedness,
and because someone's hardware may do `%' in an
instruction, and fleshing it out using divisions and
subtractions might be slower.
The big idea is to bulletproof your programs. According
to the ANSI standard, the effect of a negative number
in either operand of `%' is implementation-specific,
which means that you can't use it in "strictly conforming"
programs. These macros arrange that `%' only ever
gets nonnegative operands.
Note that the macros are dangerous: they use their
arguments more than once. Wrap them in functions
if you need to protect against side-effects, but
remember that you lose the identity of the types
when you do that.
Bug reports are always welcome.
--Blair
"Would you buy a used
cdr from this man?"
----------------->8 Decapitate'n'Debug 8<----------------
#!/bin/sh
# shar: Shell Archiver (v1.22)
#
# Run the following text with /bin/sh to create:
# remmod.h
#
sed 's/^X//' << 'SHAR_EOF' > remmod.h &&
X#include <errno.h>
X#include <math.h>
X#include <limits.h>
X
X/* sets EDOM and returns INT_MIN if x or y is out of domain of function */
X/* totally unsafe: x and y are each evaluated 0 to 3 times */
X#define rem(x,y) \
X ( ((y) == 0) \
X ? ( errno = EDOM, INT_MIN ) /* result */ \
X : ( ((x) == 0) \
X ? 0 /* result */ \
X : ( ((x) > 0) \
X ? (( (y) > 0) \
X ? ((x)%(y)) /* result */ \
X : ((x)%(-(y))) /* result */ \
X ) \
X : ( ((y) > 0) \
X ? (-((-(x))%(y))) /* result */ \
X : (-((-x)%(-(y)))) /* result */ \
X ) \
X ) \
X ) \
X ) /* end */
X
X/* sets EDOM and returns -1 if x or y is out of domain of function */
X/* totally unsafe: x and y are each evaluated 0 to 3 times */
X#define mod(x,y) \
X ( ((x) == 0) \
X ? 0 /* result */ \
X : ( ((y) == 0) \
X ? ( errno = EDOM, (-1) ) /* result */ \
X : ( ((x) > 0) \
X ? ( ((y) > 0) \
X ? ((x)%(y)) /* result */ \
X : ((x)%(-(y))) /* result */ \
X ) \
X : ( ((y) > 0) \
X ? ((y) - ((-(x))%(y))) /* result */ \
X : ((-(y)) - ((-x)%(-(y)))) /* result */ \
X ) \
X ) \
X ) \
X ) /* end */
SHAR_EOF
chmod 0644 remmod.h || echo "restore of remmod.h fails"
exit 0
Chris Torek
>>in unsigned arithmetic.
In article <1991Sep9.0...@rice.edu> do...@rice.edu (Doug Moore) writes:
>This is false; for example, if unsigneds are six bits, size is 7,
>and front is unsigned 0, the effect of
>
>front--, front %= size;
>
>is to change front to 63, then to 0, rather than 6, the intended
>result.
Oops, quite right; it works only if `size' divides 2-to-the-bits-
per-unsigned evenly.
Oh well: `if (--front < 0) front = size - 1;' anyone?
Henry Spencer
>standard said that, for ints a and b...
Why? The result would simply be that most C implementations would have a
clause in the manual saying "oh by the way, to strictly conform to the
standard's rules for division, use the -slowdivide flag". In this area,
as in others, an efficiency-oriented language like C really has no choice
but to recognize that machines differ; in many cases, C users do not care
about the differences but don't want the speed penalty incurred by hiding
them.
>... how can future hardware designers be induced to make
>better decisions?
For starters, get the Fortran standard changed; at present, it *demands*
the wrong behavior. Many manufacturers see that most users don't care
about this issue, and prefer to implement division only one way.
--
Programming graphics in X is like | Henry Spencer @ U of Toronto Zoology
finding sqrt(pi) using Roman numerals. | he...@zoo.toronto.edu utzoo!henry
Andrew Koenig
> I personally believe that the world would be a better place if the C
> standard said that, for ints a and b,
> a/b == floor((float) a, (float) b)
> and, as a consequence of the rule
> a%b == a - (a/b)*b,
> that a%b was always a value between 0 and b-1, inclusive.
I know what you're driving at, but in fact that's not what you said
for two reasons:
1. There is no particular reason to assume that
(float) a == a, and indeed it will often be false
on most machines I know. Try it, for example, with
a == 1234567891.
2. If b < 0, you want a%b to have a value between 0 and b+1.
In any event, there are three properties that one might reasonably
find desirable about integer division and the relationship between
division and remainder:
1. a%b == a - (a/b) * b
2. a%b is between 0 and b, including 0 but not b
3. (-a)/b == -(a/b)
These properties cannot all be true at once. What C does is guarantee
(1) and then permit the implementer to choose between (2) and (3)
depending on which is most convenient on the machine in question.
> In response to someone who argued that any other behavior is
> mathematically wrong, I have heard three arguments:
> 1. It's best the way it is because it's in the standard and changing
> the standard is bad.
> I reject such arguments.
Would you also reject the argument that changing the standard
is impossible? The C standard is complete; to change things
requires waiting for the next standard (or doing it in the C++
standard -- but no one has made a request to do so!)
> 2. It's best the way it is because the compiler writer should have
> the ability to implement the operation whichever way is fastest.
> Okay. Is there hardware upon which doing it my preferred way takes
> longer than doing it some other way?
Yes -- on every computer I've ever used, the built-in divide instruction
preserves rule (3) above, not rule (2).
> 3. There is no best way, because sometimes you want one result and
> sometimes the other, so it's best to avoid hampering the compiler
> writer.
That's not really the issue. It's more like `sometimes you don't care
which result you get and it's too expensive to arrange to get
the answer you want when you do care, so it's best to avoid imposing
overhead on all users for the benefit of a few.'
> Okay. Can you present an example in which you want a remainder
> operator that behaves some way other than the way I prefer?
No, but I do think a lot of people would be surprised if 7/4 were 1
and (-7)/4 were -2.
--
--Andrew Koenig
a...@europa.att.com
Richard A. O'Keefe
> 3. There is no best way, because sometimes you want one result and
> sometimes the other, so it's best to avoid hampering the compiler
> writer.
> Okay. Can you present an example in which you want a remainder
> operator that behaves some way other than the way I prefer?
> I know this is a tired thread, but I've never seen these issues
> addressed. If you have answers to offer to these questions, I'd
> appreciate them.
Lisp has all four division operators:
(floor x y) = floor(x/y)
(ceiling x y) = ceil(x/y)
(truncate x y)
(round x y)
*ALL FOUR* are useful. This has been beaten to death in several newsgroups.
I have posted examples where I want all four of these operators. If it is
_really_ necessary I will do so again, but honestly, all it takes is a little
imagination.
Yes, some machines _do_ make one easier than the others.
Don't forget, many machines were designed with Fortran in mind,
and it does specify what its MOD function does...
Pascal, by the way, does _not_ specify the effect of X mod Y for
negative Y.
Note that the book "Concrete Mathematics" proposes that x mod 0 == x.
--
It really is a nice theory. The only defect I think it has is probably
common to all philosophical theories. It's wrong. -- Saul Kripke.
I'm o...@goanna.cs.rmit.oz.au; all donations accepted.
Don Lewis
>>>But you can---as long as you make `front' unsigned, or calculate front%size
>>>in unsigned arithmetic.
>
>In article <1991Sep9.0...@rice.edu> do...@rice.edu (Doug Moore) writes:
>>This is false; for example, if unsigneds are six bits, size is 7,
>>and front is unsigned 0, the effect of
>>
>>front--, front %= size;
>>
>>is to change front to 63, then to 0, rather than 6, the intended
>>result.
>
>Oops, quite right; it works only if `size' divides 2-to-the-bits-
>per-unsigned evenly.
>
>Oh well: `if (--front < 0) front = size - 1;' anyone?
front += size-1, front %= size;
or
front = (front + size - 1) % size;
--
Don "Truck" Lewis Phone: +1 916 265-3211 Silicon Systems
Internet: (under contruction) FAX: +1 916 265-2931 138 New Mohawk Road
UUCP: {uunet,tektronix!gvgpsa.gvg.tek.com}!ssigv!lewis Nevada City, CA 95959
Dan Bernstein
> Note that the book "Concrete Mathematics" proposes that x mod 0 == x.
That's hardly a proposal. It's the only sane definition. y had better
divide x - (x mod y), so if y is 0, x - (x mod y) has to be 0. Look up
``null ideal'' in any modern algebra text.
On the other hand, I think it's particularly silly to implement mod 0,
since it's slow no matter what hardware you use. When's the last time
you wrote a program which would have been simpler if x % 0 were defined?
---Dan
Adrian McCarthy
>are useful. This has been beaten to death in several newsgroups.
Correct. So let % be the most natural operation for the machine you're on
when you need that blinding speed and you don't have to worry about the
negative operand cases. But both the mod and rem operations should also
be explicitly available (possibly as standard library functions). That
should make everybody happy, but I'm sure it won't.
Aid. (adr...@gonzo.mti.com)
Michael Morrell
> No, but I do think a lot of people would be surprised if 7/4 were 1
> and (-7)/4 were -2.
----------
I hope they're not mathematicians, then. I think of / with integer arguments
as behaving like the floor function (i.e., returning the largest integer <=
the argument, which, in the case of -7/4, is definitely -2). I realize that
the C standard does not guarantee whether -7/4 is -1 or -2, but I it should
have (I vote for mathematical correctness over some implementation discomfort
any time).
Michael
Blair P. Houghton
>Bug reports are always welcome.
> cdr from this man?"
Low time_t. New types. Driven by a little old
lady from CalTech...
Karl Heuer (The Walking Lint, in case you forget) found,
of course, a debilitating bug. My mod() macro would
return 2 in mod(-4,2).
Bletch.
If you've saved them, erase them...I'll get back to it, soon...
--Blair
"I will write a COMPLETE test suite...
I will write a COMPLETE test suite...
I will write a COMPLETE test suite...
I will write a COMPLETE test suite...
I will write a COMPLETE test suite...
I will write a COMPLETE test suite..."
der Mouse
> [ wants a%b in [0..b) and the corresponding / operator. ]
> In response to someone who argued that any other behavior is
> mathematically wrong, I have heard three arguments:
> 1. It's best the way it is because it's in the standard and changing
> the standard is bad.
This would be a reasonable argument, except that its hypothesis is not
true: the standard requires neither the -(a/b)==(-a)/b property nor the
a%b in [0..b) property.
> 2. It's best the way it is because the compiler writer should have
> the ability to implement the operation whichever way is fastest.
This is essentially the current situation. (Note that for a very large
class of applications, the behavior of % when used with a negative
operand is completely irrelevant.) Since existing implementations
vary, and the committee was in the business of standardizing existing
practice rather than inventing new (they failed in this in a few
places, but not many), they more or less had to standardize as they did.
> Okay. Is there hardware upon which doing it my preferred way takes
> longer than doing it some other way?
I'm sure there is.
> If so, is it because the hardware designer made an arbitrary,
> mathematically ill-considered decision,
Let's omit the semantic bludgeon "mathematically ill-considered", since
% is not *supposed* to be "mathematical modulus", and if you consider
the -(a/b)==(-a)/b property more important, then the behavior you so
dislike is mandated by the a==(a/b)*b+a%b property.
> or because the preferred way is inherently more complex?
That's a good question. I don't know enough about hardware ALU design
to say. But I do know that the SPARC, to pick a concrete example of a
more-or-less modern CPU, does integer / and % in software. Why don't
you try writing code for / and % in terms of +, -, <<, and >>, first
doing it one way, then the other?
> If the former, how can future hardware designers be induced to make
> better decisions?
After removing the "mathematically ill-considered", "better" makes no
sense here; it must be replaced with "different" or "other" or some
such. The answer, of course, is to demonstrate that the class of
applications that would prefer your semantics is larger than the class
that would prefer the other way.
> 3. There is no best way, because sometimes you want one result and
> sometimes the other, so it's best to avoid hampering the compiler
> writer.
> Okay. Can you present an example in which you want a remainder
> operator that behaves some way other than the way I prefer?
Not offhand. What I feel sure I could find are (a) applications that
expect a==(a/b)*b+a%b for positive a and b, and (b) applications that
expect -(a/b)==(-a)/b. It would be logically consistent to provide /
that preserves -(a/b)=(-a)/b and % that provides a%b-in-[0..b), and
give up on a==(a/b)*b+a%b (except when a and b are positive). I don't
know how useful such a language would be.
You started off with
> In response to someone who argued that any other behavior is
> mathematically wrong, I have heard three arguments:
There is another one. It is simply to point out that computer
arithmetic is not, never has, and probably never will be mathematical
arithmetic (though bignum systems try to come close), so saying that
one way or another is "mathematically wrong" verges on meaningless.
der Mouse
old: mcgill-vision!mouse
new: mo...@larry.mcrcim.mcgill.edu
Dave Jones
...
> ... The situation is rather worse in Pascal, where `a remainder b' is quite
> literally spelled `a mod b'.
I argued loudly at the time the Pascal standard was written that "mod"
should mean modulo. If I remember correctly, *I won*! But alas I forgot
to argue about how "div" should work, so it's screwed up anyway.
Dave Jones
> The following "quotes" from K&R 1, p.188. somewhat out of order..
>
> "The binary % operator yields the remainder from the division of
> the first expression by the second". "On all machines covered by
> this manual, the remainder has the same sign as the dividend".
> "It is always true that (a/b)*b + a%b is equal to a (if b is not
> 0)". "The operands must not be 'float'".
>
> a b a/b a%b (a/b)*b + a%b == a
>
> 7 3 2 1 2 * 3 + 1 == 7
> 7 -3 -2 1 -2 * -3 + 1 == 7
> -7 3 -2 -1 -2 * 3 + -1 == -7
> -7 -3 2 -1 2 * -3 + -1 == -7
>
> If you don't get these results, your library's broke (I know mine
> was).
I'm a fraid knot.
Notice that (Classic) K&R hedges with "on all machines covered by this
book".
The second edition, which represents the new ANSI standard, hedges even
more, saying that except when both the divisor and the dividend are
positive, the sign of the remainder is unspecified, except that the
absolute value of the remainder is to be less than the absolute value of
the divisor.
From time to time the discussion comes up as to which scheme is best in
practice. The arguments get heated. It's almost like language wars in a
way, although there is a contingency that says it depends on the application
which is best. Come to think of it, that happens in the language wars too.
Eventually one side always wins though.
(Putting on my best MacLaughlin-Report impersonation...)
The answer IS, "Positive remainders are best! Next topic."
Them mathematics-types got it right when they invented the "modulus"
function. The other scheme creates a discontinuity at zero which invariably
translates in practice to a runtime test for the sign of the dividend.
Besides, "negative remainder" is an oxymoron.
Dave Jones
) In any event, there are three properties that one might reasonably
) find desirable about integer division and the relationship between
) division and remainder:
)
) 1. a%b == a - (a/b) * b
)
) 2. a%b is between 0 and b, including 0 but not b
)
) 3. (-a)/b == -(a/b)
Of what possible value to a programmer is property 3?? Be specific.
Neatness counts. Show your work.
Dave Jones
> In article <s64421.683815004@zeus> s64...@zeus.usq.EDU.AU (house ron) writes:
>>
>> So it's lucky the ANSI C standard calls it 'remainder' and not 'modulus',
>> isn't it? Or is that _another_ mistake - it _should_ be modulus, and it
>> _should_ work like modulus!
>
> Is 'modulus' even the correct term for what people mean?
>
Sort of. For a congruence relation, the modulus is like our divisor in this
real-number case. The expression "a == b modulo M" means that a and b are
congruent with respect to the modulus M.
"Modulus" also means the number by which the logarithm of one base must be
multiplied in order to obtain the logarithm in another base. (If you dig
into it deep enough, it turns out that the two ideas are related
algebraically.)
> When I was at school, the modulus of A was written |A|, and meant the
> absolute value (a<0 ? -a : a).
Yeah, it is used way too. I don't know how to reconcile this meaning
with the other two. When I was into this stuff though, the popular
generalization for absolute value was always called the "norm" of a point.
We used to fill notebooks with what at the time seemed like profound and
fascinating fun-facts about "normed linear spaces" and "complex-inner-product-
spaces", and "Hilbert-spaces" and God knows what other kinds of spaces.
Some of my friends have managed to make a living, marry and divorce women,
by houses and cars, and even raise dogs and kids, through all the intervening
years, simply by putting such stuff into journals, and occasionally teaching
other people how to do the same -- a fact which today I find it very
bizarre indeed.
>
> The term for positive remainder was 'modulo', i.e. A modulo 3 meant:
> if A = (-3,-2,-1,0,1,2,3,4,5), then A modulo 3 = (0,1,2,0,1,2,0,1,2).
>
> Anyone else agree?
Yep. Precisely.
Dave Jones
)
) I understand the points that both sides have made in this argument. I
) personally believe that the world would be a better place if the C
) standard said that, for ints a and b,
)
) a/b == floor((float) a, (float) b)
)
) [... and] that a%b was always a value between 0 and b-1, inclusive.
Yep. You are absolutely right. That's the best way to do it.
) ...
) In response to someone who argued that any other behavior is
) mathematically wrong, I have heard three arguments:
)
) 1. It's best the way it is because it's in the standard and changing
) the standard is bad.
)
) I reject such arguments.
Then may you fly in a 737 whose thrust-reverser control chip has recently
been re-compiled.
) ...
)
) 3. There is no best way, because sometimes you want one result and
) sometimes the other, so it's best to avoid hampering the compiler
) writer.
)
) Okay. Can you present an example in which you want a remainder
) operator that behaves some way other than the way I prefer?
Nope. I've seen this argument played out several times, and no one has
come up with such an example yet.
Doug Moore
I apologize in advance for the mass of quoted and requoted text here.
However, the article to which I respond made several interesting
comments that I want to rebut.
mo...@thunder.mcrcim.mcgill.edu (der Mouse) writes:
> do...@rice.edu (Doug Moore) writes:
> > [ <dougm> wants a%b in [0..b) and the corresponding / operator. ]
> > In response to someone who argued that any other behavior is
> > mathematically wrong, I have heard three arguments:
> > 1. It's best the way it is because it's in the standard and changing
> > the standard is bad.
> This would be a reasonable argument, except that its hypothesis is not
> true: the standard requires neither the -(a/b)==(-a)/b property nor the
> a%b in [0..b) property.
You have misstated my hypothesis. "The way it is" means just that;
underspecified behavior for % with negative arguments.
> > Okay. Is there hardware upon which doing it my preferred way takes
> > longer than doing it some other way?
> I'm sure there is.
> > If so, is it because the hardware designer made an arbitrary,
> > mathematically ill-considered decision,
> Let's omit the semantic bludgeon "mathematically ill-considered", since
> % is not *supposed* to be "mathematical modulus", and if you consider
> the -(a/b)==(-a)/b property more important, then the behavior you so
> dislike is mandated by the a==(a/b)*b+a%b property.
There are two valid interpretations of what % is *supposed* to be:
1. A value that is easy for the machine to calculate, and maybe
somebody wants it, so we'll give them a way to get it. I imagine this
to be the idea that motivated the operator in C.
2. A value that programmers would find most useful. I want this.
I wish that the machine calculated the second quantity, so that there
would be no conflict. Only by stating that opinion persuasively can I
hope ever to have it happen. Maybe a future CPU designer is reading
this. Maybe I can help establish a consensus that one definition is
at least slightly preferred to another.
I have asked anyone to identify a case in which he considers the
-(a/b)==(-a)/b property more important, but I have seen no such
examples presented.
It's interesting that a couple of people have taken me to task for
forcefully stating my opinion, accusing me of using a "semantic
bludgeon" or stating something in an "overly slanted" way. It seems
that on the net, one is obligated to preface any opinion with
IMVHOWIDNRVTHMAWIWBGFYTC (in my very humble opinion which I do not
really value that highly myself and which I would be grateful for you
to consider). Call me a net-boor, then.
> > or because the preferred way is inherently more complex?
> That's a good question.
Thanks.
> Why don't you try writing code for / and % in terms of +, -, <<, and
> >>, first doing it one way, then the other?
Okay. To the extent possible, I'll simulate a typical machine.
void divmod(long n, short d, long *qptr, short *rptr)
{
int neg_n = n < 0, neg_d = d < 0;
long q;
int nShifts = 0;
/* make operands nonnegative */
if (neg_n) n = -n;
if (neg_d) d = -d;
/* shift to make n/d a proper fraction */
while (d <= n)
++nShifts, d <<= 1;
#ifdef BAD
q = 0;
#else /* GOOD */
if (neg_n != neg_d) q = -1, n = d - n;
else q = 0;
#endif
/* reduce n to a value < denominator */
while (nShifts-- > 0)
{
d >>= 1;
q <<= 1;
{
long diff = n - d;
if (diff >= 0) ++q, n = diff;
}
}
/* correct for differing signs */
#ifdef BAD
if (neg_n != neg_d) q = -q;
if (neg_n) n = -n;
#else /* GOOD */
if (neg_d) n = -n;
#endif
*qptr = q;
*rptr = n;
}
In the case when the quotient is positive, the two versions operate
identically, except that one test is made in a different place in one
program than in the other.
> > If the former, how can future hardware designers be induced to make
> > better decisions?
> After removing the "mathematically ill-considered", "better" makes no
> sense here; it must be replaced with "different" or "other" or some
> such. The answer, of course, is to demonstrate that the class of
> applications that would prefer your semantics is larger than the class
> that would prefer the other way.
So far, the score is
Applications that want my semantics: 1
Applications that want other semantics: 0
Applications that don't care: 10000
These are estimates only. I can boost the first score. Can anyone
boost the second?
> > 3. There is no best way, because sometimes you want one result and
> > sometimes the other, so it's best to avoid hampering the compiler
> > writer.
> > Okay. Can you present an example in which you want a remainder
> > operator that behaves some way other than the way I prefer?
> Not offhand. What I feel sure I could find are (a) applications that
> expect a==(a/b)*b+a%b for positive a and b, and (b) applications that
> expect -(a/b)==(-a)/b. It would be logically consistent to provide /
> that preserves -(a/b)=(-a)/b and % that provides a%b-in-[0..b), and
> give up on a==(a/b)*b+a%b (except when a and b are positive). I don't
> know how useful such a language would be.
I'm still looking for those class (b) applications.
> You started off with
>
> > In response to someone who argued that any other behavior is
> > mathematically wrong, I have heard three arguments:
>
> There is another one. It is simply to point out that computer
> arithmetic is not, never has, and probably never will be mathematical
> arithmetic (though bignum systems try to come close), so saying that
> one way or another is "mathematically wrong" verges on meaningless.
You have attributed to me an argument which is not mine. I seek a
less error prone and more useful definition, not a mathematically pure
one. Everytime I have to write "(n + size - 1)% size" instead of
"(n-1) % size", I'm paying the cost of one addition, so it's a speed
issue too.
Doug Moore, windmill jouster
(do...@rice.edu)
Tim Peters
> [... wants a%b == a-floor(a/b)*b, wonders why a-truncate(a/b)*b is
> more common ...
> ]
Believe it boils down to this:
1) "The most natural" way to design integer division *hardware* is to
have it truncate rather than compute the floor. "The most natural"
way to do integer division in hardware was historically the way you'd
do binary integer division by hand:
a) Convert to a signed magnitude representation (so that the
operands are positive) and remember the sign bits for later.
b) Do the obvious (or the not-so-obvious variations) one-
quotient-bit-at-a-time loop to develop the quotient.
c) Stop when you reach the end of the word.
d) Attach the proper sign bit and, if negative, convert back to
the machine's normal representation for negative integers.
This is inherently truncating. The "natural way" to do the floor
instead requires additional logic (== circuitry, implies more space &
more time) between #c and #d to test both the sign and the remainder,
and to conditionally bump the quotient by 1 "depending".
In the C code you wrote later in the msg, you did the fiddling for
floor earlier on, but it makes no essential difference: you still
needed an "extra" addition (subtraction; same thing) to get the
floor, and in *hardware* that has a real cost (although one that's
become less & less worth worrying about ...).
2) Since most machines that did integer division in hardware did only
the truncating version directly, the natural flavor of "mod" was the
cheapest one to compute, i.e. the one that used the division the
hardware supplied (& note that, for whatever reasons, many many
architectures that do support integer division don't deliver the
remainder directly, thus leaving any flavor of mod for software to
compute).
3) Etc (insert the usual essay about historical forces and our varied
adaptations and reactions to same <0.9 grin>).
All by way of fleshing out:
>1. A value that is easy for the machine to calculate, and maybe
>somebody wants it, so we'll give them a way to get it. I imagine this
>to be the idea that motivated the operator in C.
And the same idea that motivated Fortran to mandate truncating integer
division & the natural mod that follows from that. I too would prefer
to have a choice, and much prefer the floor-based flavor of mod. You're
by no means alone in that, Doug. Fortran 90 introduced a second
intrinsic "mod-like" function so that Fortran 90 users will have the
choice. Perhaps the next version of C should do the same.
and-if-we-all-keeping-whining-about-it-maybe-it-will<grin>-ly y'rs - tim
Tim Peters Kendall Square Research Corp
t...@ksr.com, ksr!t...@uunet.uu.net
Joe W Wright
about all this. She said "I don't know modulus, but.."
dividend / divisor = quotient + (remainder / divisor)
and pointed out that with simple algebra you could assign letters
to these things and manipulate them in all sorts of ways. She
then proceeded to write some equations for me.
If a / b == q + (r / b)
then a == (b * q) + r
and b == (a - r) / q
and q == (a - r) / b
and r == a - (b * q)
Seriously now people, our wishes are not important. We are
talking about 'real' numbers here. The rules for their
manipulations do outdate and will outlive us all. Pay attention.
Rewrite [(a/b)*b + a%b == a] and you will see [a == (b * q) + r]
and the rest of the above equations. Clearly then, if a is -7
and b is 2, a/b == -3 and a%b == -1. There's just no way around
it. And the 'white book' says so too. If [a - (b * q)] is not
what you want, don't do [a%b]. Try something else.
Now regardless of machine type and hardware arithmetic method, it
is up to the C compiler's backend to trick the hairy beasts into
giving us all the same right answers, given the same good
questions. If it doesn't, its author isn't finished yet. Don't
argue with this. It's what C standards are all about.
I was going to make some sort of disclaimer about humble opinions
but I don't see any here.
"Go ahead, make my day." Harry Callahan SFPD
Joe Wright al...@cup.Portal.COM "If you want it wRight"
Alpha Systems Corp., 711 Chatsworth Pl., San Jose, CA 95128
(408) 297-5594 (voice) "If you want it wRight now!"
"The New World is sixty-four bits wide, and flat!"
Michael Sierchio
(a/b)*b is probably not a. Oh, it might be. But operations are not
associative in Finite (or Discrete) math as they are in real math. And
given that, and the standard's explicit statement that implementation
details that are not delineated are left to the implementor's discretion.
Period. Sorry.
--
Michael Sierchio TRW Financial Systems
1947 Center Street
ku...@tfs.com Berkeley, CA 94704-1105
510.704.3380
house ron
>I asked my 13-year-old daughter (8th grade) what she thought
>about all this. She said "I don't know modulus, but.."
[Delightful story omitted.]
>Rewrite [(a/b)*b + a%b == a] and you will see [a == (b * q) + r]
>and the rest of the above equations. Clearly then, if a is -7
>and b is 2, a/b == -3 and a%b == -1. There's just no way around
>it. And the 'white book' says so too. If [a - (b * q)] is not
>what you want, don't do [a%b]. Try something else.
How about a/b == -4 and a%b == 1? You are assuming truncation
towards 0.
>Now regardless of machine type and hardware arithmetic method, it
>is up to the C compiler's backend to trick the hairy beasts into
>giving us all the same right answers, given the same good
>questions. If it doesn't, its author isn't finished yet. Don't
>argue with this. It's what C standards are all about.
Just one minor detail - The C standard is _deliberately_ vague about
the case where a or b is negative. The reason is (to me) obvious -
about 10000000 programs do positive remaindering for each 1 which
does negative, and it is more important to make that 10000000 as
fast as possible by letting the compiler writer use the fastest
possible instruction for %. If you want to do something special,
write yourself a special function.
>I was going to make some sort of disclaimer about humble opinions
>but I don't see any here.
No, only right and wrong ones. :-)
--
Regards,
Ron House. (s64...@zeus.usq.edu.au)
(By post: Info Tech, U.C.S.Q. Toowoomba. Australia. 4350)
Andrew Koenig
> Rewrite [(a/b)*b + a%b == a] and you will see [a == (b * q) + r]
> and the rest of the above equations. Clearly then, if a is -7
> and b is 2, a/b == -3 and a%b == -1. There's just no way around
> it. And the 'white book' says so too. If [a - (b * q)] is not
> what you want, don't do [a%b]. Try something else.
If you look a little more closely, you will see that the 'white book'
(and the ANSI/ISO C standard) allows either a/b == -3 and a%b == -1
or a/b == -4 and a%b = 1.
--
--Andrew Koenig
a...@europa.att.com
Joe W Wright
'position', I am going to agree with Doug Moore about the %
operator.
1. First, a%b should return a remainder in the range 0..|b|-1,
not for esoteric 'correctness' but for maximum usefulness.
2. Further, a/b should be rounded toward 0, again to be more
useful in providing the 'expected' result. This will give us the
properties -(a/b) == (-a)/b == a/(-b) == -((-a)/(-b)). If we
need a signed remainder for some reason (like Doug, I can't think
of one) we can apply the sign of a to the result of a%b.
q = a/b; toward 0 (-7 / 2 == -3)
m = a%b; 0..|b|-1 (1)
r = (a < 0) ? -m : m; (-1)
This will give us the [a / b == q + (r / b)] relation again.
I don't know if this is actually 'defined' in other languages
better than it is in C but I did try this with Turbo Pascal and
also with Ada.
In both, a div b rounds the quotient toward 0. In Pascal the mod
operator returns the remainder with the sign of the quotient. In
Ada a mod b has the sign of a. Ada also has a rem operator which
returns the remainder with the sign of b.
There doesn't seem to be much of a concensus here. Just for the
record, I have changed my own C math library to conform to (1.)
and (2.) above.
Joe Wright al...@cup.Portal.COM "If you want it wRight"
Alpha Systems Corp., 711 Chatsworth Pl., San Jose, CA 95128
(408) 297-5594 (voice) "If you want it wRight now!"
"The real world is eight bits wide, until further notice."
Arthur Rubin
>There are two valid interpretations of what % is *supposed* to be:
>1. A value that is easy for the machine to calculate, and maybe
>somebody wants it, so we'll give them a way to get it. I imagine this
>to be the idea that motivated the operator in C.
>2. A value that programmers would find most useful. I want this.
>I wish that the machine calculated the second quantity, so that there
>would be no conflict. Only by stating that opinion persuasively can I
>hope ever to have it happen. Maybe a future CPU designer is reading
>this. Maybe I can help establish a consensus that one definition is
>at least slightly preferred to another.
>I have asked anyone to identify a case in which he considers the
>-(a/b)==(-a)/b property more important, but I have seen no such
>examples presented.
I'm not sure this has the correct syntax for itoa, but bear with me.
I'm also using MicroSoft C's specifications for strcat and strrev; I'm
not sure they're ANSI.
char * itoa(int i, char * s)
{
char * sign = (i<0) ? "-" : "";
char * tmp = s;
do {
*tmp++ = '0' + abs(i % 10);
i /= 10;
} while (i);
*tmp = 0;
return (strrev(strcat(s,sign)));
}
--
216...@mcimail.com 7070...@compuserve.com art...@pnet01.cts.com (personal)
a_r...@dsg4.dse.beckman.com (work)
My opinions are my own, and do not represent those of my employer.
Andrew Koenig
> 1. First, a%b should return a remainder in the range 0..|b|-1,
> not for esoteric 'correctness' but for maximum usefulness.
> 2. Further, a/b should be rounded toward 0, again to be more
> useful in providing the 'expected' result. This will give us the
> properties -(a/b) == (-a)/b == a/(-b) == -((-a)/(-b)). If we
> need a signed remainder for some reason (like Doug, I can't think
> of one) we can apply the sign of a to the result of a%b.
> q = a/b; toward 0 (-7 / 2 == -3)
> m = a%b; 0..|b|-1 (1)
> r = (a < 0) ? -m : m; (-1)
> This will give us the [a / b == q + (r / b)] relation again.
You can't do this in a standard-conforming C implementation,
because the standard requires that if q = a/b and r = a%b,
then a == q * b + r. You cannot preserve this property and
simultaneously keep your two properties above.
In particullar, following the standard and simultaneously maintaining
your property (2) is possible only if a%b has the same sign as a.
Your property (1) insists that a%b be non-negative, which means
that you'll violate the standard whenever a is negative.
--
--Andrew Koenig
a...@europa.att.com
Dave Jones
) Just to finish up my part of this thread and to state my latest
) 'position', I am going to agree with Doug Moore about the %
) operator.
)
) 1. First, a%b should return a remainder in the range 0..|b|-1,
) not for esoteric 'correctness' but for maximum usefulness.
)
) 2. Further, a/b should be rounded toward 0, again to be more
) useful in providing the 'expected' result.
Why? If I had never heard of FORTRAN, and being a card-carrying mathematician,
I would expect that a/b be consistently rounded *down*, not toward zero.
) This will give us the
) properties -(a/b) == (-a)/b == a/(-b) == -((-a)/(-b)).
What earthly good are those properties to the simple country programmer?
Dave Jones
> I asked my 13-year-old daughter (8th grade) what she thought
> about all this. She said "I don't know modulus, but.."
>
> dividend / divisor = quotient + (remainder / divisor)
Your daughter is absolutely correct. Ask her what she thinks of the
following:
1. Imagine you are in a club with two members, and it is decided that
you will divide up the money in the treasury, to the nearest dollar.
There are seven dollars in the account. So you divide $7 by 2 obtaining
$3. Each member takes that amount, and there is a $1 remainder.
2. Now imagine instead that the club owes $7, and it is decided that
each member will contribute an integral number of dollars to retire the
debt. You divide minus $7 by 2, obtaining a negative $4. Each member pays
$4 and there is again a $1 remainder.
The moral to the story is that a "negative remainder" is an oxymoron.