# Integer Rounding in C

Discussion in 'C Programming' started by Mr. Burns, Nov 23, 2008.

1. ### Mr. BurnsGuest

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!

Mr. Burns, Nov 23, 2008

2. ### CBFalconerGuest

"Mr. Burns" wrote:
>

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

<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://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>

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>

CBFalconer, Nov 23, 2008

3. ### Nate EldredgeGuest

Mr. Burns <> writes:

> 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

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

Nate Eldredge, Nov 23, 2008
4. ### Andrey TarasevichGuest

Mr. Burns wrote:
>
> 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;

--
Best regards,
Andrey Tarasevich

Andrey Tarasevich, Nov 23, 2008
5. ### BartcGuest

"Nate Eldredge" <> wrote in message
news:...
> Mr. Burns <> writes:
>
>> 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.

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?!

--
Bartc

Bartc, Nov 23, 2008
6. ### WillemGuest

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

Willem, Nov 23, 2008
7. ### BartcGuest

"Willem" <> wrote in message
news:...
> 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.

--
Bartc

Bartc, Nov 23, 2008
8. ### Phil CarmodyGuest

"Bartc" <> writes:
> "Nate Eldredge" <> wrote in message
> news:...
>> Mr. Burns <> writes:
>>> 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.

>
> 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
--
I tried the Vista speech recognition by running the tutorial. I was
amazed, it was awesome, recognised every word I said. Then I said the
wrong word ... and it typed the right one. It was actually just
detecting a sound and printing the expected word! -- pbhj on /.

Phil Carmody, Nov 23, 2008
9. ### James KuyperGuest

Bartc wrote:
>
> "Willem" <> wrote in message

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

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.

James Kuyper, Nov 23, 2008
10. ### Ben BacarisseGuest

Mr. Burns <> writes:

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

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.

--
Ben.

Ben Bacarisse, Nov 23, 2008
11. ### Nate EldredgeGuest

Ben Bacarisse <> writes:

> Mr. Burns <> writes:
>
> <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!

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

Nate Eldredge, Nov 23, 2008
12. ### Phil CarmodyGuest

Nate Eldredge <> writes:
> Ben Bacarisse <> writes:
>
>> Mr. Burns <> writes:
>>
>> <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!

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

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
--
I tried the Vista speech recognition by running the tutorial. I was
amazed, it was awesome, recognised every word I said. Then I said the
wrong word ... and it typed the right one. It was actually just
detecting a sound and printing the expected word! -- pbhj on /.

Phil Carmody, Nov 23, 2008
13. ### Ben BacarisseGuest

Phil Carmody <> writes:

> Nate Eldredge <> writes:
>> Ben Bacarisse <> writes:
>>
>>> Mr. Burns <> writes:
>>>
>>> <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!
>>>
>>> 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?

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

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

--
Ben.

Ben Bacarisse, Nov 23, 2008

Mr. Burns wrote:
> 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).

--

15. ### CBFalconerGuest

Nate Eldredge wrote:
> Mr. Burns <> writes:
>
>> 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;
> }

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

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>

CBFalconer, Nov 24, 2008