Division and Modular Reduction

Discussion in 'C++' started by Jeffrey Walton, Jul 29, 2011.

  1. Hi All,

    I'm building test cases for a third party library, and wanted a
    clarification. Searching the FAQ did not turn up hits for division and
    modulo or reduction [1].

    INT_MIN / -1 = overflow since the result is INT_MAX+1. For example
    (using int16 types):

    32768 = -32768 / -1

    Below, the result is within the reange of the datattype.

    32767 = -32768 % -1

    However Seacord tells us the result is undefined in CERT's Secure
    Programming Guide [2]. Also, I seem to recall that reduction is
    defined similar to division for consistency.

    What is the state of modular reduction (eg, INT_MIN % -1)?

    Jeff

    [1] http://www.parashift.com/c -faq-lite/
    [2]
    https://www.securecoding.cert.org/c...ations do not result in divide-by-zero errors
     
    Jeffrey Walton, Jul 29, 2011
    #1
    1. Advertising

  2. On 7/29/2011 2:25 PM, Jeffrey Walton wrote:
    > Hi All,
    >
    > I'm building test cases for a third party library, and wanted a
    > clarification. Searching the FAQ did not turn up hits for division and
    > modulo or reduction [1].
    >
    > INT_MIN / -1 = overflow since the result is INT_MAX+1. For example
    > (using int16 types):
    >
    > 32768 = -32768 / -1


    Actually, 5/4 says the result is not overflow, it's undefined: "If
    during the evaluation of an expression, the result is not mathematically
    defined or not in the range of representable values for its type, the
    behavior is undefined."

    > Below, the result is within the reange of the datattype.
    >
    > 32767 = -32768 % -1


    The modulo operand (or the remainder) (a % b) is defined to produce the
    number (c) such that

    (a / b) * b + c == a

    So, if we allow the division to go through (i.e. not be undefined), then
    the remainder should satisfy the equation

    (-32768 / -1) * -1 + c = -32768,

    which yields c==0 (if I didn't mess up).

    Generally speaking for any 'i' (i % 1) => 0. Considering that the
    remainder is specified to have the same sign as the left operand, if
    negative zero is representable on the system, then for any negative
    number 'j' (j % 1) => -0 and (j %-1) => 0.

    At least that's how I understand it.

    >
    > However Seacord tells us the result is undefined in CERT's Secure
    > Programming Guide [2]. Also, I seem to recall that reduction is
    > defined similar to division for consistency.
    >
    > What is the state of modular reduction (eg, INT_MIN % -1)?
    >
    > Jeff
    >
    > [1] http://www.parashift.com/c -faq-lite/
    > [2]
    > https://www.securecoding.cert.org/c...ations do not result in divide-by-zero errors
    >


    V
    --
    I do not respond to top-posted replies, please don't ask
     
    Victor Bazarov, Jul 29, 2011
    #2
    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. Replies:
    94
    Views:
    4,689
    ┬Ča\\/b
    Feb 9, 2007
  2. Jeffrey Walton

    Division and Modular Reduction (Repost)

    Jeffrey Walton, Jul 29, 2011, in forum: C++
    Replies:
    0
    Views:
    221
    Jeffrey Walton
    Jul 29, 2011
  3. jimbo1qaz
    Replies:
    12
    Views:
    361
  4. Cameron Simpson
    Replies:
    0
    Views:
    194
    Cameron Simpson
    Sep 7, 2012
  5. Mark Lawrence
    Replies:
    0
    Views:
    216
    Mark Lawrence
    Sep 7, 2012
Loading...

Share This Page