Integer Rounding in C

[Mr. Burns]

Hi group,

suppose I have a grid of cells of size (R,C) and coordinates (0..R-1,0..C-1) and
I'm translating pixel coordinates to grid coordinates by dividing by cell size.

Now, all works well for values >= 0, but for values < 0 I'm getting
inconsistent results.

On one platform, division of negative numbers rounds towards negative
infinity, i.e., (-1 / 10) gives -1. (this is what I want)

On another platform (solaris), rounding is towards zero, and (-1 / 10) is 0!

All numbers are plain ints.

Are both results legal? If so, is there a portable formula that will have
identical results on both kinds of platforms?

Thanks!

 

[CBFalconer]

.... snip ...

On one platform, division of negative numbers rounds towards
negative infinity, i.e., (-1 / 10) gives -1. (this is what I
want). On another platform (solaris), rounding is towards zero,
and (-1 / 10) is 0!

All numbers are plain ints.

Are both results legal? If so, is there a portable formula
that will have identical results on both kinds of platforms?

IIRC this was a change that came about with C99, and I am not
certain in which direction it went without looking it up. You need
to make your code sensitive to the C standard in use. See the C99
refs below.

Some useful references about C:
<http://www.ungerhu.com/jxh/clc.welcome.txt>
<http://c-faq.com/> (C-faq)
<http://benpfaff.org/writings/clc/off-topic.html>
<http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf> (C99)
<http://cbfalconer.home.att.net/download/n869_txt.bz2> (pre-C99)
<http://www.dinkumware.com/c99.aspx> (C-library}
<http://gcc.gnu.org/onlinedocs/> (GNU docs)
<http://clc-wiki.net/wiki/C_community:comp.lang.c:Introduction>

 

[Nate Eldredge]

Hi group,

suppose I have a grid of cells of size (R,C) and coordinates (0..R-1,0..C-1) and
I'm translating pixel coordinates to grid coordinates by dividing by cell size.

Now, all works well for values >= 0, but for values < 0 I'm getting
inconsistent results.

On one platform, division of negative numbers rounds towards negative
infinity, i.e., (-1 / 10) gives -1. (this is what I want)

On another platform (solaris), rounding is towards zero, and (-1 / 10) is 0!

All numbers are plain ints.

The C99 standard specifies truncation towards zero (like your Solaris
compiler). However, the previous C90 standard left it up to the
implementation to decide which way to round when one of the operands is
negative, as long as it is consistent with the % operator. So evidently
your first compiler isn't C99, though it may be C90.

Are both results legal? If so, is there a portable formula that will have
identical results on both kinds of platforms?

When both operands are positive, rounding is towards zero, so you could
take advantage of that (untested):

int divide_like_i_want(int a, int b) {
int sign = 1;
int q;
if (a < 0) {
sign = -sign;
a = -a;
}
if (b < 0) {
sign = -sign;
b = -b;
}
q = a / b;
q *= sign;
if (sign < 0 && a % b != 0) q--;
return q;
}

 

[Andrey Tarasevich]

On one platform, division of negative numbers rounds towards negative
infinity, i.e., (-1 / 10) gives -1. (this is what I want)

On another platform (solaris), rounding is towards zero, and (-1 / 10) is 0!

All numbers are plain ints.

Are both results legal?

Both results are legal in C89/90. An implementation might stick with
one, or it might provide you with an option to choose between the two.

In C99 it is required that the result is always rounded towards zero.

If so, is there a portable formula that will have
identical results on both kinds of platforms?

Well, you can always catch negative dividend and decrease it by 'divisor
- 1' before performing the division.

q = (a >= 0 ? a : a - (b - 1)) / b;

 

[Bartc]

The C99 standard specifies truncation towards zero (like your Solaris
compiler). However, the previous C90 standard left it up to the
implementation to decide which way to round when one of the operands is
negative, as long as it is consistent with the % operator.

You'd think that the result of (-1)/10, would be the same as -(1/10). In
other words both zero, assuming -0 is 0.

So in this code:

int a,b,c;
....
a = b / c;

The value of a depends not only on b and c, but on the implementation?!

 

[Willem]

Bartc wrote:
) You'd think that the result of (-1)/10, would be the same as -(1/10). In
) other words both zero, assuming -0 is 0.

Yes, but you'd also think that (-1)%10, would be 9, because then
it strokes with the mathematical way that modulo calculus works.

But for that to be true, (-1)/10 would have to be -1.

This is because you want the following to hold:
(b * (a/b)) + (a%b) == a

) So in this code:
)
) int a,b,c;
) ...
) a = b / c;
)
) The value of a depends not only on b and c, but on the implementation?!

That's because C90 allows the implementation to use the CPU's DIV
instruction, and both flavours of DIV instructions exist.
With the new rules, a compiler is forced to add extra code to make
sure that it truncates towards zero on those CPU's that don't.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[Bartc]

Bartc wrote:
) You'd think that the result of (-1)/10, would be the same as -(1/10). In
) other words both zero, assuming -0 is 0.

Yes, but you'd also think that (-1)%10, would be 9, because then
it strokes with the mathematical way that modulo calculus works.

But for that to be true, (-1)/10 would have to be -1.

This is because you want the following to hold:
(b * (a/b)) + (a%b) == a

) So in this code:
)
) int a,b,c;
) ...
) a = b / c;
)
) The value of a depends not only on b and c, but on the implementation?!

That's because C90 allows the implementation to use the CPU's DIV
instruction, and both flavours of DIV instructions exist.

That's often the reason for these various quirks in C.

It still doesn't change the fact that this is a little like allowing 2+2 to
be either 4 or 5 depending on the implementation.

With the new rules, a compiler is forced to add extra code to make
sure that it truncates towards zero on those CPU's that don't.

I would expect so.

 

[Phil Carmody]

You'd think that the result of (-1)/10, would be the same as
-(1/10).

I certainly wouldn't. I don't believe anyone with any background
in numerical analysis would do either. _Clearly_ a rounding
operation is taking place, and _clearly_ rounding is direction
(increasing vs. decreasing in value) sensitive. Given that unary
minus changes the direction, it's far from obvious that the unary
operators '-' and rounding should commute under composition.

Which is why we shouldn't "think", we should read and learn.
Rounding is a well-studied field, which has led large numbers
of intelligent and well-read people to come to completely
different conclusions. From this we should learn to not guess,
but instead to simply look at the standards and be aware of
whichever of the arbitrary choices have been selected.

In other words both zero, assuming -0 is 0.

So in this code:

int a,b,c;
...
a = b / c;

The value of a depends not only on b and c, but on the implementation?!

If that's what the standard says, then yes. If that's not what the
standard says, then no.

Phil

 

[James Kuyper]

That's often the reason for these various quirks in C.

It still doesn't change the fact that this is a little like allowing 2+2
to be either 4 or 5 depending on the implementation.

The key difference is that there's a unique, widely accepted value for
2+2. The idea that (-3)/2 even has a meaningful value when the range is
restricted to integers is an artifact of machine computing. What that
value should be is a question that different systems answered
differently. The original C standard merely reflected this state of affairs.

The current standard made what I consider to be the wrong choice: when
exactly one of the operands in an integer division is negative, I have
never have had reason to want rounding toward 0; what I wanted has
always been rounding toward negative infinity. However, a consistent
decision is still better than leaving it up to the implementation.

 

[Ben Bacarisse]

On one platform, division of negative numbers rounds towards negative
infinity, i.e., (-1 / 10) gives -1. (this is what I want)

On another platform (solaris), rounding is towards zero, and (-1 /
10) is 0!

The OP has an explanation, but now I find I want to ask an auxiliary
question. Can this problem be solved using the pre-processor in C90
or is the pre-processor permitted to use a different
implementation-defined division to that of the execution environment?

The standard requires (in section 3.4 referenced by section 3.8.1)
that "The semantic rules for the evaluation of a constant expression
are the same as for non-constant expressions". These rules, however,
allow for implementation defined behaviour. Is the implementation
permitted to define different rules for constant expressions?

My guess would be "no". Partly because that is the useful answer, but
also because the intent (of other wording) seems to be ensure that
compile-time arithmetic be done in a way that is as similar to that
of the execution environment as is practically possible. It also
seems to be a counter-intuitive reading of those words.

If others can support this guess, then the OP can define a division
function using conditional includes.

 

[Nate Eldredge]

The OP has an explanation, but now I find I want to ask an auxiliary
question. Can this problem be solved using the pre-processor in C90
or is the pre-processor permitted to use a different
implementation-defined division to that of the execution environment?

The standard requires (in section 3.4 referenced by section 3.8.1)
that "The semantic rules for the evaluation of a constant expression
are the same as for non-constant expressions". These rules, however,
allow for implementation defined behaviour. Is the implementation
permitted to define different rules for constant expressions?

My guess would be "no". Partly because that is the useful answer, but
also because the intent (of other wording) seems to be ensure that
compile-time arithmetic be done in a way that is as similar to that
of the execution environment as is practically possible. It also
seems to be a counter-intuitive reading of those words.

If others can support this guess, then the OP can define a division
function using conditional includes.

You mean something like

#if ((-1)/10 == 0)
#define MY_DIV(a,b) my_div_func((a),(b))
#else
#define MY_DIV(a,b) ((a)/(b))
#endif

?

Hmm, very interesting. If that's meant to work, however, I'd bet
there's systems that get it wrong. For instance, in the case of a cross
compiler, the compiler pass might know about arithmetic details of the
target platform, but the preprocessor pass is usually generic and
probably would not.

 

[Phil Carmody]

You mean something like

#if ((-1)/10 == 0)
#define MY_DIV(a,b) my_div_func((a),(b))
#else
#define MY_DIV(a,b) ((a)/(b))
#endif

Any half-decent optimiser should be able to remove the if and unused
branch in if((-1)/10==0) { return mydiv(a,b); } else { return a/b; }

Phil

 

[Ben Bacarisse]

Any half-decent optimiser should be able to remove the if and unused
branch in if((-1)/10==0) { return mydiv(a,b); } else { return a/b; }

That's true -- there may be no run-time cost -- I was just curious
about the consequences of the wording of C90. (The wording is similar
in C99 but the issue does not arise with division.)

 

[Thad Smith]

Hi group,

suppose I have a grid of cells of size (R,C) and coordinates (0..R-1,0..C-1) and
I'm translating pixel coordinates to grid coordinates by dividing by cell size.

Now, all works well for values >= 0, but for values < 0 I'm getting
inconsistent results.

On one platform, division of negative numbers rounds towards negative
infinity, i.e., (-1 / 10) gives -1. (this is what I want)

On another platform (solaris), rounding is towards zero, and (-1 / 10) is 0!

All numbers are plain ints.

Are both results legal? If so, is there a portable formula that will have
identical results on both kinds of platforms?

As others have said, C89 accepted both results. The way to get
consistent results with C89 is with the div or ldiv library function,
which gives consistent results (quotient for your example is -1).

 

[CBFalconer]

The C99 standard specifies truncation towards zero (like your
Solaris compiler). However, the previous C90 standard left it
up to the implementation to decide which way to round when one
of the operands is negative, as long as it is consistent with
the % operator. So evidently your first compiler isn't C99,
though it may be C90.


When both operands are positive, rounding is towards zero, so you
could take advantage of that (untested):

int divide_like_i_want(int a, int b) {
int sign = 1;
int q;
if (a < 0) {
sign = -sign;
a = -a;
}
if (b < 0) {
sign = -sign;
b = -b;
}
q = a / b;
q *= sign;
if (sign < 0 && a % b != 0) q--;
return q;
}

I suggest you first convert all values to negative integers. That
way your process will not run into integer overflow, and
implementation defined results.