Quotients and remainders in integer division
Paul Jarc
> However, in C, the truncation of the quotient is toward zero and thus
> the sign of the remainder always follows that of the dividend.
In C9X, yes - in C89, I think it's implementation-defined whether
rounding is toward zero or negative infinity.
> Can you give me the rationale of the current definition of quotients
> and remainders in integer division, or some practical examples where
> this way of behaviour is preferred over the "mathematical" one?
I believe it's because this is how most processors do integer
division, and C tries to stay somewhat close to the hardware for
efficiency. You do still have the property that a/b*b+a%b==a, and you
gain the property that -(a/b)==(-a)/b==a/(-b) (not using C's == there,
of course). You can get the standard mathematical values with a
little extra work:
q=a/b-(a%b<0);
r=(a%b+abs(b))%b;
paul
Paul Eggert
>You can get the standard mathematical values with a
>little extra work:
> q=a/b-(a%b<0);
> r=(a%b+abs(b))%b;
First, that remainder formula won't work in general, as either the abs
or the + might overflow.
Second, I don't agree that those are ``the standard mathematical values''.
For more on this subject -- much more than you'll find in a typical Usenet
posting -- please see:
Raymond T Boute
The Euclidean definitions of the functions div and mod
ACM transactions on programming languages and systems 14, 2 (1992-04), 127-144
Boute argues that almost all computer hardware and language definitions
use conventions that are inferior to to Euclid's original definition.
where the remainder is always nonnegative.
Here is my implementation of Euclidean div and mod in C9x:
div = a/b + (b<0 ? 0<a%b : -(a%b<0));
mod = a%b + (a%b<0 ? abs(b) : 0);
>in C89, I think it's implementation-defined whether
>rounding is toward zero or negative infinity.
C89 also allows other forms of rounding; e.g. it allows Euclidean division.
I'm sure that Boute would not approve of the fact that C9x will disallow
Euclidean division, but the pull of Fortran proved too strong in practice.
Paul Jarc
> Paul Jarc <p...@po.cwru.edu> writes:
> >You can get the standard mathematical values with a
> >little extra work:
> > q=a/b-(a%b<0);
> > r=(a%b+abs(b))%b;
>
Well, I was going for a=q*b+r, 0<=r<abs(b), but I didn't spend much
time thinking about it (not enough, apparently).
> >in C89, I think it's implementation-defined whether
> >rounding is toward zero or negative infinity.
>
> C89 also allows other forms of rounding; e.g. it allows Euclidean division.
How is that different from rounding toward negative infinity? I'm
taking it for granted that a=q*b+r and abs(r)<abs(b) for any choice of
sign handling, so there would be only two possibilities. Has it been
done some other way, or have I screwed up somewhere?
paul
Paul Eggert
>egg...@twinsun.com (Paul Eggert) writes:
>> C89 also allows other forms of rounding; e.g. it allows Euclidean division.
>How is that different from rounding toward negative infinity?
With Euclidean division, dividing 1 by -3 yields a quotient of 0 with a
remainder of 1; for this particular case, it's the same as truncation.
With flooring (i.e. rounding towards negative infinity), the quotient
is -1 and the remainder is -2.
Clive D.W. Feather
<p...@po.cwru.edu> writes
>> Can you give me the rationale of the current definition of quotients
>> and remainders in integer division, or some practical examples where
>> this way of behaviour is preferred over the "mathematical" one?
>
>I believe it's because this is how most processors do integer
>division, and C tries to stay somewhat close to the hardware for
>efficiency.
Plus it's how Fortran does it. And I agree that it's a pain.
--
Clive D.W. Feather | Internet Expert | Work: <cl...@demon.net>
Tel: +44 20 8371 1138 | Demon Internet Ltd. | Home: <cl...@davros.org>
Fax: +44 20 8371 1037 | | Web: <http://www.davros.org>
Written on my laptop; please observe the Reply-To address
Douglas A. Gwyn
> Plus it's how Fortran does it. And I agree that it's a pain.
That was in fact the main argument for C9x requiring truncation
toward zero. I drafted the wording for the change, because it
was the committee consensus, not because I personally think it
is a wise choice. (I would have preferred that integer division
act as a regular "step function" as zero is crossed, i.e. %
would be better as a true modulo operator.) Until C9x pushes
C89 implementations into the background, however, one has to
keep in mind that for negative integer operands, / and % have
implementation-dependent behavior. The best solution is to
make sure whenever you use them that the operands are positive.
Konrad Schwarz
>
> Paul Jarc <p...@po.cwru.edu> writes:
>
> >You can get the standard mathematical values with a
> >little extra work:
> > q=a/b-(a%b<0);
> > r=(a%b+abs(b))%b;
> Here is my implementation of Euclidean div and mod in C9x:
>
> div = a/b + (b<0 ? 0<a%b : -(a%b<0));
> mod = a%b + (a%b<0 ? abs(b) : 0);
As an aside, shouldn't people be encouraged to use the standard library
functions div()/ldiv() when both quotient and remainder are of interest?
(Many processors calculate remainders by dividing, multiplying, and subtracting.
Explicitly writing down the % and the / operators requires common sub-expression
elimination to prevent two expensive divisions/calls to the division routine,
and I beleive inlining of standard library functions to be a simpler optimization
than common sub-expression elimination and thus more likely to be applied.)
--
Konrad Schwarz konrad_...@mcdDOTmot.com
Motorola Computer Group
81829 M"unchen Schatzbogen 7 Tel: +49 89 92103 828
81809 M"unchen Postfach 820960 Fax: +49 89 92103 266
Paul Eggert
>Paul Eggert wrote:
>> Here is my implementation of Euclidean div and mod in C9x:
>> div = a/b + (b<0 ? 0<a%b : -(a%b<0));
>> mod = a%b + (a%b<0 ? abs(b) : 0);
>
>As an aside, shouldn't people be encouraged to use the standard library
>functions div()/ldiv() when both quotient and remainder are of interest?
No, on the contrary, people should generally be discouraged from using
div and ldiv, for several reasons:
* div and ldiv make the code harder to read.
* They often make the code slower. At least they did on the first test I
tried: a Sun Ultra 1/170E running Solaris 7 (32-bit), compiled with
Sun C 5.0 with the -xO2 option. When I rewrote the above code to
use div, I slowed it down by a factor of two, roughly.
* They mean the programmer must know the size and signedness of the operands.
This information is not always easily available. E.g. suppose you
want to do quotient and remainder on time_t values (which is relatively
common, at least in the POSIX world). It's a configuration nightmare
to use div and/or ldiv and/or lldiv and/or whatever else C9x has added
in this area (I don't recall offhand).
I suppose div and ldiv have their place, but I would normally stay away
from them, and use them only as a tuning device of last resort.
Douglas A. Gwyn
> As an aside, shouldn't people be encouraged to use the standard library
> functions div()/ldiv() when both quotient and remainder are of interest?
Yes, especially since the compiler may convert those function calls
to very efficient in-line code, in many cases.