Integer Rounding in C

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

  1. Mr. Burns

    Mr. Burns Guest

    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
    #1
    1. Advertising

  2. Mr. Burns

    CBFalconer Guest

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

    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>

    --
    [mail]: Chuck F (cbfalconer at maineline dot net)
    [page]: <http://cbfalconer.home.att.net>
    Try the download section.
     
    CBFalconer, Nov 23, 2008
    #2
    1. Advertising

  3. 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
    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;
    }
     
    Nate Eldredge, Nov 23, 2008
    #3
  4. 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
    #4
  5. Mr. Burns

    Bartc Guest

    "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
    #5
  6. Mr. Burns

    Willem Guest

    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
    #6
  7. Mr. Burns

    Bartc Guest

    "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
    #7
  8. Mr. Burns

    Phil Carmody Guest

    "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
    #8
  9. Mr. Burns

    James Kuyper Guest

    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
    #9
  10. 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
    #10
  11. 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
    #11
  12. Mr. Burns

    Phil Carmody Guest

    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
    #12
  13. 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
    #13
  14. Mr. Burns

    Thad Smith Guest

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

    --
    Thad
     
    Thad Smith, Nov 24, 2008
    #14
  15. Mr. Burns

    CBFalconer Guest

    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>
    Try the download section.
     
    CBFalconer, Nov 24, 2008
    #15
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. walala
    Replies:
    12
    Views:
    1,879
  2. valentin tihomirov

    rounding to integer

    valentin tihomirov, Feb 15, 2004, in forum: VHDL
    Replies:
    2
    Views:
    9,646
    Jonathan Bromley
    Feb 16, 2004
  3. =?Utf-8?B?Sm9l?=

    CType(x,Integer) vs. Integer.Parse(x)

    =?Utf-8?B?Sm9l?=, Feb 6, 2006, in forum: ASP .Net
    Replies:
    7
    Views:
    5,957
    =?Utf-8?B?RGF2aWQgQW50b24=?=
    Feb 7, 2006
  4. =?ISO-8859-1?Q?Thomas_Gagn=E9?=

    No Math.min(Integer, Integer)?

    =?ISO-8859-1?Q?Thomas_Gagn=E9?=, Jul 29, 2003, in forum: Java
    Replies:
    0
    Views:
    511
    =?ISO-8859-1?Q?Thomas_Gagn=E9?=
    Jul 29, 2003
  5. Mr. Ken
    Replies:
    2
    Views:
    639
    Tomás
    May 25, 2006
Loading...

Share This Page