1439 views

Skip to first unread message

Jul 9, 1999, 3:00:00 AM7/9/99

to

Kim Sung-bom <musi...@bawi.org> writes:

> However, in C, the truncation of the quotient is toward zero and thus

> the sign of the remainder always follows that of the dividend.

> 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

Jul 9, 1999, 3:00:00 AM7/9/99

to

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;

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.

Jul 9, 1999, 3:00:00 AM7/9/99

to

egg...@twinsun.com (Paul Eggert) writes:

> 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;

>

> 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;

>

> Second, I don't agree that those are ``the standard mathematical values''.

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

Jul 9, 1999, 3:00:00 AM7/9/99

to

Paul Jarc <p...@po.cwru.edu> writes:

>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.

Jul 10, 1999, 3:00:00 AM7/10/99

to

In article <m3pv21d...@prj.student.cwru.edu>, Paul Jarc

<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.

<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

Jul 10, 1999, 3:00:00 AM7/10/99

to

"Clive D.W. Feather" wrote:

> Plus it's how Fortran does it. And I agree that it's a pain.

> 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.

Jul 12, 1999, 3:00:00 AM7/12/99

to

Paul Eggert wrote:

>

> 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;

[...]>

> 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

Jul 12, 1999, 3:00:00 AM7/12/99

to

Konrad Schwarz <konrad_...@mcd.motDOTcom> writes:

>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.

Jul 13, 1999, 3:00:00 AM7/13/99

to

Konrad Schwarz wrote:

> As an aside, shouldn't people be encouraged to use the standard library

> functions div()/ldiv() when both quotient and remainder are of interest?

> 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.

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu