was: "mod operator for signed integers"

Discussion in 'C Programming' started by Luca Forlizzi, Jun 25, 2011.

  1. hello I try to "resurrect" the thread "was: "mod operator for signed
    integers"" because I tried to find the answers to the following
    questions posed by Tim Rentsch

    >"dr.oktopus" <> writes:
    >>> It's not guaranteed to work portably.


    >> Why?


    >If we have 'int m;' and 'unsigned n;', with m in [ INT_MIN .. -1 ]
    >and n in [ 1 .. UINT_MAX ], consider the expression


    > (m + INT_MAX) + n


    >Question 1: What is the maximum value of this expression,
    >considered as a mathematical expression?


    it should be (INT_MAX-1)+UINT_MAX, which is greater then the maximum
    value representable in an unsigned int. So the expression can exhibit
    overflow

    >Question 2: Considered as a C expression, what is the
    >type of the expression? (Hint: there is more than one
    >possibility.)


    this confuses me, since at first glance I only see one possibility,
    unsigned int.
    Indeed, m and INT_MAX have type int. Maybe UINT_MAX is the tricky one:
    if an int can
    represent all values of unsigned int, UINT_MAX has int type (by
    5.2.4.2.1 p1). So in this case the whole expression has type int,
    while in all other cases it has type unsigned int, because of the
    usual arithmetic convertions

    >Question 3: Have you tried working through the solution
    > that was posted, to see how it works?


    the proposed solution to the OP's question was:
    m < 0 ? n-1 - -(m+1)%n : m%n

    I tried to prove that it's correct (for the case m<0) but I did not
    succeed
    yet. My difficulty is maybe that I am unable to find an analitical
    definition
    of what result the OP was expecting. Could someone provide more hints?

    LF
    Luca Forlizzi, Jun 25, 2011
    #1
    1. Advertising

  2. Luca Forlizzi

    Tim Rentsch Guest

    Luca Forlizzi <> writes:

    > hello I try to "resurrect" the thread "was: "mod operator for signed
    > integers"" because I tried to find the answers to the following
    > questions posed by Tim Rentsch
    >
    >>"dr.oktopus" <> writes:
    >>>> It's not guaranteed to work portably.

    >
    >>> Why?

    >
    >>If we have 'int m;' and 'unsigned n;', with m in [ INT_MIN .. -1 ]
    >>and n in [ 1 .. UINT_MAX ], consider the expression

    >
    >> (m + INT_MAX) + n

    >
    >>Question 1: What is the maximum value of this expression,
    >>considered as a mathematical expression?

    >
    > it should be (INT_MAX-1)+UINT_MAX,


    Yes.

    > which is greater then the maximum value representable in an
    > unsigned int.


    Yes, and also greater than INT_MAX.

    > So the expression can exhibit overflow


    You mean it can exhibit modular behavior when the sum is
    performed in type 'unsigned int'.

    If the sum were performed in type 'int', then there could
    be overflow.


    >>Question 2: Considered as a C expression, what is the
    >>type of the expression? (Hint: there is more than one
    >>possibility.)

    >
    > this confuses me, since at first glance I only see one possibility,
    > unsigned int.
    > Indeed, m and INT_MAX have type int. Maybe UINT_MAX is the tricky one:
    > if an int can
    > represent all values of unsigned int, UINT_MAX has int type (by
    > 5.2.4.2.1 p1). So in this case the whole expression has type int,
    > while in all other cases it has type unsigned int, because of the
    > usual arithmetic convertions


    C allows implementations where UINT_MAX == INT_MAX. In C99
    (as amended by a later TC, I believe), the rules for integer
    promotions specify (presumably unintentionally) that such
    implementation "promote" unsigned int to int. In such cases
    the expression in question could be of type 'int'.


    >>Question 3: Have you tried working through the solution
    >> that was posted, to see how it works?

    >
    > the proposed solution to the OP's question was:
    > m < 0 ? n-1 - -(m+1)%n : m%n
    >
    > I tried to prove that it's correct (for the case m<0) but I did not
    > succeed
    > yet. My difficulty is maybe that I am unable to find an analitical
    > definition
    > of what result the OP was expecting. Could someone provide more hints?


    Here is a start. I will use MOD to mean modulo, % for
    the C remainder operation. We want m MOD n

    m MOD n === (n + m ) MOD n
    === ((n-1) + (m+1)) MOD n
    === ((n-1) - -(m+1)) MOD n
    === ((n-1) MOD n - (-(m+1)) MOD n) MOD n

    Q1: What is (n-1) MOD n (assuming n > 0)?

    Q2: Can you relate (-(m+1)) MOD n to -(m+1)%n, given that
    -(m+1) >= 0 and n > 0?

    Q3: How can you get rid of the final outside 'MOD n'?
    Tim Rentsch, Jun 27, 2011
    #2
    1. Advertising

  3. On 27 Giu, 19:47, Tim Rentsch <> wrote:
    > Luca Forlizzi <> writes:

    [snip]
    > >>If we have 'int m;' and 'unsigned n;', with m in [ INT_MIN .. -1 ]
    > >>and n in [ 1 .. UINT_MAX ], consider the expression

    >
    > >>   (m + INT_MAX) + n

    >
    > >>Question 1:  What is the maximum value of this expression,
    > >>considered as a mathematical expression?

    >
    > > it should be (INT_MAX-1)+UINT_MAX,

    >
    > Yes.
    >
    > > which is greater then the maximum value representable in an
    > > unsigned int.

    >
    > Yes, and also greater than INT_MAX.
    >
    > > So the expression can exhibit overflow

    >
    > You mean it can exhibit modular behavior when the sum is
    > performed in type 'unsigned int'.
    >
    > If the sum were performed in type 'int', then there could
    > be overflow.


    yes, thanks for the correction

    > >>Question 2:  Considered as a C expression, what is the
    > >>type of the expression?  (Hint:  there is more than one
    > >>possibility.)

    >
    > > this confuses me, since at first glance I only see one possibility,
    > > unsigned int.
    > > Indeed, m and INT_MAX have type int. Maybe UINT_MAX is the tricky one:
    > > if an int can
    > > represent all values of unsigned int, UINT_MAX has int type (by
    > > 5.2.4.2.1 p1). So in this case the whole expression has type int,
    > > while in all other cases it has type unsigned int, because of the
    > > usual arithmetic convertions

    >
    > C allows implementations where UINT_MAX == INT_MAX.  In C99
    > (as amended by a later TC, I believe), the rules for integer
    > promotions specify (presumably unintentionally) that such
    > implementation "promote" unsigned int to int.  In such cases
    > the expression in question could be of type 'int'.


    That's what I had guessed.
    However I now remember from other discussion that the possibility of
    promoting unsigned int to int was introduced unintentionally in C99
    TC2. I think that Larry Jones confirmed that the change was
    unintentional. In the latest C1X draft such a possibility is rules
    out, because the text says that the integer promotions apply to
    integer types "other than int or unsigned int" (with rank less than
    or equal to the rank of int).
    Then I think that in C89, unamended C99 and the current draft of C1X,
    there is just one posssibility for the type of (m + INT_MAX) + n,
    which is unsigned int, because m and INT_MAX are int and n in unsigned
    int.

    > >>Question 3:  Have you tried working through the solution
    > >> that was posted, to see how it works?

    >
    > > the proposed solution to the OP's question was:
    > > m < 0  ?  n-1 - -(m+1)%n  :  m%n

    >
    > > I tried to prove that it's correct  (for the case m<0) but I did not
    > > succeed
    > > yet. My difficulty is maybe that I am unable to find an analitical
    > > definition
    > > of what result the OP was expecting. Could someone provide more hints?


    In the previous days I developed a proof different from the one you
    give below, based on the fact that m MOD n is equal to the difference
    between m and the maximum integer x which is a multiple of n (I mean
    x=k*n for some integer k, is "multiple" the correct english term?) and
    is not bigger than m. For me it was easier given that I don't have
    much experience with the MOD properties.
    In any case thanks a lot for your proof sketch, which seems to me
    almost complete, is very instructive. I will try to answer you
    questions

    >
    > Here is a start.  I will use MOD to mean modulo, % for
    > the C remainder operation.  We want m MOD n
    >
    >    m MOD n   ===   (n     +   m   )  MOD n
    >              ===   ((n-1) +  (m+1))  MOD n
    >              ===   ((n-1) - -(m+1))  MOD n
    >              ===   ((n-1) MOD n  -  (-(m+1)) MOD n)  MOD n


    all the steps but the last one are straightforward. I can see that the
    last one comes from
    the fact that (a+b) MOD c === (a MOD c + b MOD c) MOD c, which I
    verified with a picture

    >
    > Q1:  What is (n-1) MOD n (assuming n > 0)?


    it should be equal to n-1

    >
    > Q2:  Can you relate (-(m+1)) MOD n to -(m+1)%n, given that
    >      -(m+1) >= 0 and n > 0?


    they should be equal

    >
    > Q3:  How can you get rid of the final outside 'MOD n'?


    it should follow from the same property you used in the last step
    above:
    (a+b) MOD c === (a MOD c + b MOD c) MOD c
    or, more simply, one can say that since -(m+1)%n is a positive number
    not greater than n-1,
    n-1 - (-(m+1)%n) is also a positive number not greater than n-1.
    For any positive number x not greater than n-1, x MOD N is equal to x.

    Thanks for your time, by the way
    Luca Forlizzi, Jun 30, 2011
    #3
  4. Luca Forlizzi

    Tim Rentsch Guest

    Luca Forlizzi <> writes:

    > On 27 Giu, 19:47, Tim Rentsch <> wrote:
    >> Luca Forlizzi <> writes:

    > [snip]
    > In the previous days I developed a proof different from the one you
    > give below, based on the fact that m MOD n is equal to the difference
    > between m and the maximum integer x which is a multiple of n (I mean
    > x=k*n for some integer k, is "multiple" the correct english term?) and
    > is not bigger than m. For me it was easier given that I don't have
    > much experience with the MOD properties.
    >
    > [snip]
    >
    > Thanks for your time, by the way


    You are most welcome, sir. Always a pleasure posting for
    people who are polite and appreciative.
    Tim Rentsch, Jul 3, 2011
    #4
  5. On 3 Lug, 23:23, Tim Rentsch <> wrote:
    > Luca Forlizzi <> writes:
    > > On 27 Giu, 19:47, Tim Rentsch <> wrote:
    > >> Luca Forlizzi <> writes:

    > > [snip]
    > > In the previous days I developed a proof different from the one you
    > > give below, based on the fact that m MOD n is equal to the difference
    > > between m and the maximum integer x which is a multiple of n (I mean
    > > x=k*n for some integer k, is "multiple" the correct english term?) and
    > > is not bigger than m. For me it was easier given that I don't have
    > > much experience with the MOD properties.

    >
    > > [snip]

    >
    > > Thanks for your time, by the way

    >
    > You are most welcome, sir.  Always a pleasure posting for
    > people who are polite and appreciative.


    Time and knowledge are among the few important things in life, for me,
    so I very much appreciate when people spend their time to share it
    with me.
    Since you didn't comment my answers the questions, I guess you
    consider them, more or less, correct.

    thanks again
    Luca
    Luca Forlizzi, Jul 5, 2011
    #5
  6. Luca Forlizzi

    Tim Rentsch Guest

    Luca Forlizzi <> writes:

    > On 3 Lug, 23:23, Tim Rentsch <> wrote:
    >> Luca Forlizzi <> writes:
    >> > On 27 Giu, 19:47, Tim Rentsch <> wrote:
    >> >> Luca Forlizzi <> writes:
    >> > [snip]
    >> > In the previous days I developed a proof different from the one you
    >> > give below, based on the fact that m MOD n is equal to the difference
    >> > between m and the maximum integer x which is a multiple of n (I mean
    >> > x=k*n for some integer k, is "multiple" the correct english term?) and
    >> > is not bigger than m. For me it was easier given that I don't have
    >> > much experience with the MOD properties.

    >>
    >> > [snip]

    >>
    >> > Thanks for your time, by the way

    >>
    >> You are most welcome, sir. Always a pleasure posting for
    >> people who are polite and appreciative.

    >
    > Time and knowledge are among the few important things in life, for me,
    > so I very much appreciate when people spend their time to share it
    > with me.
    > Since you didn't comment my answers the questions, I guess you
    > consider them, more or less, correct.


    Yes, with only a minor observation that at one point
    you say 'positive' but what's right is 'positive
    or zero'.
    Tim Rentsch, Jul 6, 2011
    #6
    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. dr.oktopus

    mod operator for signed integers

    dr.oktopus, Apr 9, 2011, in forum: C Programming
    Replies:
    12
    Views:
    425
    Eric Sosman
    Apr 10, 2011
  2. dr.oktopus

    was: "mod operator for signed integers"

    dr.oktopus, Apr 16, 2011, in forum: C Programming
    Replies:
    19
    Views:
    419
    Keith Thompson
    Apr 18, 2011
Loading...

Share This Page