Velocity Reviews > Integer Rounding in C

# Integer Rounding in C

Mr. Burns
Guest
Posts: n/a

 11-23-2008
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
Guest
Posts: n/a

 11-23-2008
"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
Guest
Posts: n/a

 11-23-2008
Mr. Burns <(E-Mail Removed)> 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
Guest
Posts: n/a

 11-23-2008
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
Guest
Posts: n/a

 11-23-2008

"Nate Eldredge" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> Mr. Burns <(E-Mail Removed)> 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
Guest
Posts: n/a

 11-23-2008
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
Guest
Posts: n/a

 11-23-2008

"Willem" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> 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
Guest
Posts: n/a

 11-23-2008
"Bartc" <(E-Mail Removed)> writes:
> "Nate Eldredge" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed)...
>> Mr. Burns <(E-Mail Removed)> 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
Guest
Posts: n/a

 11-23-2008
Bartc wrote:
>
> "Willem" <(E-Mail Removed)> 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
Guest
Posts: n/a

 11-23-2008
Mr. Burns <(E-Mail Removed)> 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.

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Mr. Ken C++ 2 05-25-2006 12:54 PM =?Utf-8?B?Sm9l?= ASP .Net 7 02-07-2006 02:30 AM valentin tihomirov VHDL 2 02-16-2004 10:07 AM walala VHDL 12 09-14-2003 03:49 PM =?ISO-8859-1?Q?Thomas_Gagn=E9?= Java 0 07-29-2003 07:46 PM