Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C Programming (http://www.velocityreviews.com/forums/f42-c-programming.html)
-   -   Integer Rounding in C (http://www.velocityreviews.com/forums/t645694-integer-rounding-in-c.html)

 Mr. Burns 11-23-2008 03:01 AM

Integer Rounding in C

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 11-23-2008 03:15 AM

Re: Integer Rounding in C

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

 Nate Eldredge 11-23-2008 04:02 AM

Re: Integer Rounding in C

Mr. Burns <burns@snpp.invalid> 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;
}

 Andrey Tarasevich 11-23-2008 06:47 AM

Re: Integer Rounding in C

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

 Bartc 11-23-2008 11:20 AM

Re: Integer Rounding in C

"Nate Eldredge" <nate@vulcan.lan> wrote in message
news:8663mf144q.fsf@vulcan.lan...
> Mr. Burns <burns@snpp.invalid> 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

 Willem 11-23-2008 11:34 AM

Re: Integer Rounding in C

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 11-23-2008 12:11 PM

Re: Integer Rounding in C

"Willem" <willem@stack.nl> wrote in message
news:slrngiifu6.23gt.willem@snail.stack.nl...
> 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

 Phil Carmody 11-23-2008 12:18 PM

Re: Integer Rounding in C

"Bartc" <bc@freeuk.com> writes:
> "Nate Eldredge" <nate@vulcan.lan> wrote in message
> news:8663mf144q.fsf@vulcan.lan...
>> Mr. Burns <burns@snpp.invalid> 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 /.

 James Kuyper 11-23-2008 12:54 PM

Re: Integer Rounding in C

Bartc wrote:
>
> "Willem" <willem@stack.nl> 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.

 Ben Bacarisse 11-23-2008 01:08 PM

Re: Integer Rounding in C

Mr. Burns <burns@snpp.invalid> 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.

All times are GMT. The time now is 04:49 PM.