C signed integer division rule history?
Stuart Levy
quotient/remainder were defined in C. It's been this
way since the '70s, so it surely won't change now.
I'd just like to know if anyone understands why it was
done this way.
The annoyance is in the case a/b or a%b,
where a<0 and b>0. In every single case I can
ever remember programming, I've wanted a%b (b>0, any a) to
yield a non-negative value in range 0 .. b-1. But no,
C makes the sign of the remainder match the sign
of the numerator, not the denominator. Because of
this choice, I need an extra test: not
r = a % b;
but something like
r = (a<0) ? (a%b) + b : (a%b);
or sometimes, when I know the possible range of a,
r = (a+b) % b;
It appears that many (most?) hardware divide
instructions, from the PDP-11 onward, make the
same choice. Maybe that's why. But if so,
why would all those hardware designers have chosen it?
On the other hand, has anyone here ever actually
*wanted* the sign-of-remainder = sign-of-numerator behavior?
Thanks.
Stuart Levy, sl...@ncsa.uiuc.edu
Bruce G. Stewart
I guess in the ten years between 1989 and 1999, somebody decided that
the symmetry of -a/b == -(a/b) was better than the regularity of (a+b)/b
== (a/b)+1, hence -1/2 == 0 rather than -1/2 == -1. C89 left the choice
to the implementation, but C99 dictates the first alternative.
I presume this was a choice to codify the behaviour of a lot of
hardware, rather than a thumbing of the nose at mathematians.
% is the remainder operation, defined (rather reasonably, imho) by the
identity (a/b)*b + a%b == a. Thus, the behavior of % is condemned to be
that which you observe.
Kaz Kylheku
>I'm puzzled (and annoyed) by the way that integer
>quotient/remainder were defined in C. It's been this
>way since the '70s, so it surely won't change now.
>I'd just like to know if anyone understands why it was
>done this way.
>
>The annoyance is in the case a/b or a%b,
>where a<0 and b>0. In every single case I can
>ever remember programming, I've wanted a%b (b>0, any a) to
>yield a non-negative value in range 0 .. b-1. But no,
If you want positive residues, there are a few tricks you can pull,
such as adding enough multiples of the modulus to get a positive left
operand to %.
If you are working with congruences, you can avoid negative intermediate
results completely (and even use unsigned types). Avoid subtraction. If
you need to subtract x, instead add (m+1-x) where m is the modulus. Then
you can normalize by reducing modulo m.
For example, suppose I have a circular array of size m, and given element
n, I want to compute the adjacent lower one. Now n could be zero, in
which case the adjacent lower one is m-1. No matter, what, an expression
which yields the correct index is (n + m - 1) % m.
>C makes the sign of the remainder match the sign
>of the numerator, not the denominator. Because of
>this choice, I need an extra test: not
>
> r = a % b;
>
>but something like
> r = (a<0) ? (a%b) + b : (a%b);
>or sometimes, when I know the possible range of a,
> r = (a+b) % b;
>
>It appears that many (most?) hardware divide
>instructions, from the PDP-11 onward, make the
>same choice. Maybe that's why. But if so,
>why would all those hardware designers have chosen it?
>
>On the other hand, has anyone here ever actually
>*wanted* the sign-of-remainder = sign-of-numerator behavior?
The semantics of % are tied to the semantics of /. In C89, the
implementor has a choice (which must be documented) whether the result
of an inexact division, when it is negative, is closer to zero or to
negative infinity. If it is closer to zero, then it means that the
remainder from the % operator is negative to match.
In C99, the implementation choice is removed: the result must be
closer to zero---and so the div() and ldiv() functions are now
superflous.
So you see, it's not a case of preferring a negative residue in
the remainder operator, but rather a case of preferring the rounding
toward zero in the division operator, which provides a nice
symmetry, so that
a/b == -(-a/b) == -(a/-b) == (-a/-b)
morgan mair fheal
sl...@niri.ncsa.uiuc.edu (Stuart Levy) wrote:
>I'm puzzled (and annoyed) by the way that integer
>quotient/remainder were defined in C. It's been this
>way since the '70s, so it surely won't change now.
>I'd just like to know if anyone understands why it was
>done this way.
this was the fortran rule
and c is fortran in pascal clothing
i assume its the fortran rule because its how the ibm machine did it
and this is from the pre system 360 era
Bill Godfrey
> but something like
> r = (a<0) ? (a%b) + b : (a%b);
Incidently, is this expression strictly confomringly correct to work
for circular arrays?
Bill, has a big file of macros.
Lawrence Kirby
k...@ashi.footprints.net "Kaz Kylheku" writes:
...
>The semantics of % are tied to the semantics of /. In C89, the
>implementor has a choice (which must be documented) whether the result
>of an inexact division, when it is negative, is closer to zero or to
>negative infinity. If it is closer to zero, then it means that the
>remainder from the % operator is negative to match.
In C89 the choice exists if either operand is negative. So, for example
either
-5/-2 == 2 -5%-2 == -1
or
-5/-2 == 3 -5%-2 == 1
is allowed.
--
-----------------------------------------
Lawrence Kirby | fr...@genesis.demon.co.uk
Wilts, England | 7073...@compuserve.com
-----------------------------------------
Stuart Levy
[...]
>If you are working with congruences, you can avoid negative intermediate
>results completely (and even use unsigned types). Avoid subtraction. If
>you need to subtract x, instead add (m+1-x) where m is the modulus. Then
>you can normalize by reducing modulo m.
Yes -- that's what I meant by
r = (a+b) % b
though this only works if you can be sure that a >= -b
(which you sometimes can, sure enough). But it seems as though
the need to use such a trick, in such a common case, is a sign of
a bad design choice. That's what I was hoping to get opinions on.
[...]
>The semantics of % are tied to the semantics of /.
Yes...
>In C89, the
>implementor has a choice (which must be documented) whether the result
>of an inexact division, when it is negative, is closer to zero or to
>negative infinity. If it is closer to zero, then it means that the
>remainder from the % operator is negative to match.
Oh, that's interesting. I'd thought I remembered K&R specifying the
sign-of-remainder == sign-of-numerator rule (which, yes, implies division
rounded toward zero). Looking again, I see that was indeed left unspecified --
it just behaves that way on all the implementations I've used.
However fmod(3) *does* specify that same pain-in-the-neck (IMO) behavior.
>In C99, the implementation choice is removed: the result must be
>closer to zero---and so the div() and ldiv() functions are now
>superflous.
Thanks -- good to know it's at least reliable now, even if it's
reliably broken.
>So you see, it's not a case of preferring a negative residue in
>the remainder operator, but rather a case of preferring the rounding
>toward zero in the division operator, which provides a nice
>symmetry, so that
>
> a/b == -(-a/b) == -(a/-b) == (-a/-b)
That looks nice on paper, but how often is it what you want when coding,
given the effect on the remainder?
Stuart Levy, sl...@ncsa.uiuc.edu
Stuart Levy
>sl...@niri.ncsa.uiuc.edu (Stuart Levy) writes:
>
>> but something like
>> r = (a<0) ? (a%b) + b : (a%b);
>
>Incidently, is this expression strictly confomringly correct to work
>for circular arrays?
I would think that, for incrementing/decrementing around circular arrays,
you could avoid the test and just use
r = (a+b) % b
where a is some_valid_index +/- some_small_increment.
So long as some_valid_index is in 0 .. b-1 and
abs(some_small_increment) < b, (and oh yeah 0 < 2*b < MAXINT)
this guarantees (a+b) >= 0, which is all you'd need.
>Bill, has a big file of macros.
Stuart Levy
Peter Pichler
news:slrn9pvska...@niri.ncsa.uiuc.edu...
> The annoyance is in the case a/b or a%b,
> where a<0 and b>0. In every single case I can
> ever remember programming, I've wanted a%b (b>0, any a) to
> yield a non-negative value in range 0 .. b-1. But no,
> C makes the sign of the remainder match the sign
> of the numerator, not the denominator.
> On the other hand, has anyone here ever actually
> *wanted* the sign-of-remainder = sign-of-numerator behavior?
I don't know, but to me (-6) / 3 = 2, remainder 0 makes more
sense than (-6) / 3 = 0, remainder -6.
If two people share a debt of $6, they owe $3 each, don't they?
--
Peter Pichler, Abingdon, Oxfordshire, UK
My "From" address is valid; try pichloN+1 should pichloN bounce.
Kaz Kylheku
Pichler wrote:
>"Stuart Levy" <sl...@niri.ncsa.uiuc.edu> wrote in message
>news:slrn9pvska...@niri.ncsa.uiuc.edu...
>> The annoyance is in the case a/b or a%b,
>> where a<0 and b>0. In every single case I can
>> ever remember programming, I've wanted a%b (b>0, any a) to
>> yield a non-negative value in range 0 .. b-1. But no,
>> C makes the sign of the remainder match the sign
>> of the numerator, not the denominator.
>...
>> On the other hand, has anyone here ever actually
>> *wanted* the sign-of-remainder = sign-of-numerator behavior?
>
>I don't know, but to me (-6) / 3 = 2, remainder 0 makes more
>sense than (-6) / 3 = 0, remainder -6.
In this case there is no contention, because the division produces
an exact result. If the division is exact, why would you want
a positive or negative remainder?
Stuart Levy
>> On the other hand, has anyone here ever actually
>> *wanted* the sign-of-remainder = sign-of-numerator behavior?
>
>I don't know, but to me (-6) / 3 = 2, remainder 0 makes more
>sense than (-6) / 3 = 0, remainder -6.
>
>If two people share a debt of $6, they owe $3 each, don't they?
Yes, they do. But under either division rule,
(-6) / 3 = -2, remainder 0.
No matter which rule you choose, the remainder always lies in
the range 0 <= |rem| < |divisor|, so it couldn't be -6.
They would differ in, for example
(-7) / 3
where the now-official rule gives
(-7) / 3 = -2, remainder -1
while the alternative round-quotient-toward-negative-infinity gives
(-7) / 3 = -3, remainder +2
- Stuart Levy