mod operator for signed integers

Discussion in 'C Programming' started by dr.oktopus, Apr 9, 2011.

  1. dr.oktopus

    dr.oktopus Guest

    Ok, today I seems to be a little dumb.
    What I have to do is to make mod operator (m % n) work even
    if m is a negative number.

    This is what I mean:

    given n = 5

    7 became 2
    6 .. 1
    5 .. 0
    4 .. 4
    3 .. 3
    2 .. 2
    1 .. 1
    0 .. 0
    -1 .. 4
    -2 .. 3
    -3 .. 2
    -4 .. 1
    -5 .. 0
    -6 .. 4
    -7 .. 3

    I think that, for a operation like m % n, it could be:

    unsigned my_mod (int m, unsigned n)
    {
    unsigned um;

    if (m < 0) {
    um = -m;
    return n - um % n;
    }
    return m % n;
    }

    but, if m is INT_MIN, for example, its two complement (um)
    is 0, right? So, my_mod returns n (that is wrong).

    What's the right (and smart) way?
     
    dr.oktopus, Apr 9, 2011
    #1
    1. Advertising

  2. dr.oktopus

    Geoff Guest

    On Sat, 9 Apr 2011 07:53:05 -0700 (PDT), "dr.oktopus"
    <> wrote:

    >Ok, today I seems to be a little dumb.
    >What I have to do is to make mod operator (m % n) work even
    >if m is a negative number.
    >
    >This is what I mean:
    >
    >given n = 5
    >
    > 7 became 2
    > 6 .. 1
    > 5 .. 0
    > 4 .. 4
    > 3 .. 3
    > 2 .. 2
    > 1 .. 1
    > 0 .. 0
    >-1 .. 4
    >-2 .. 3
    >-3 .. 2
    >-4 .. 1
    >-5 .. 0
    >-6 .. 4
    >-7 .. 3
    >
    >I think that, for a operation like m % n, it could be:
    >
    >unsigned my_mod (int m, unsigned n)
    >{
    > unsigned um;
    >
    > if (m < 0) {
    > um = -m;
    > return n - um % n;
    > }
    > return m % n;
    >}
    >
    >but, if m is INT_MIN, for example, its two complement (um)
    >is 0, right? So, my_mod returns n (that is wrong).
    >
    >What's the right (and smart) way?


    r = m < 0 ? -m % n : m % n;
    return r;
     
    Geoff, Apr 9, 2011
    #2
    1. Advertising

  3. dr.oktopus

    Geoff Guest

    On Sat, 09 Apr 2011 09:51:59 -0700, Geoff <>
    wrote:

    >On Sat, 9 Apr 2011 07:53:05 -0700 (PDT), "dr.oktopus"
    ><> wrote:
    >
    >>Ok, today I seems to be a little dumb.
    >>What I have to do is to make mod operator (m % n) work even
    >>if m is a negative number.
    >>
    >>This is what I mean:
    >>
    >>given n = 5
    >>
    >> 7 became 2
    >> 6 .. 1
    >> 5 .. 0
    >> 4 .. 4
    >> 3 .. 3
    >> 2 .. 2
    >> 1 .. 1
    >> 0 .. 0
    >>-1 .. 4
    >>-2 .. 3
    >>-3 .. 2
    >>-4 .. 1
    >>-5 .. 0
    >>-6 .. 4
    >>-7 .. 3
    >>
    >>I think that, for a operation like m % n, it could be:
    >>
    >>unsigned my_mod (int m, unsigned n)
    >>{
    >> unsigned um;
    >>
    >> if (m < 0) {
    >> um = -m;
    >> return n - um % n;
    >> }
    >> return m % n;
    >>}
    >>
    >>but, if m is INT_MIN, for example, its two complement (um)
    >>is 0, right? So, my_mod returns n (that is wrong).
    >>
    >>What's the right (and smart) way?

    >
    > r = m < 0 ? -m % n : m % n;
    > return r;


    Correction:

    r = m < 0 ? 0-m % n : m % n;
    return r;
     
    Geoff, Apr 9, 2011
    #3
  4. dr.oktopus

    Willem Guest

    dr.oktopus wrote:
    ) Ok, today I seems to be a little dumb.
    ) What I have to do is to make mod operator (m % n) work even
    ) if m is a negative number.

    % is the remainder operator, not the mod operator.
    However, observe that the result is still equivalent within
    the given modulus.

    Therefore, this should work:

    r = m % n;
    if (r < 0) r += n;

    Or if you want a single expression:

    r = ((m % n) + n) % n;


    HTH.


    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, Apr 9, 2011
    #4
  5. dr.oktopus

    Eric Sosman Guest

    On 4/9/2011 10:53 AM, dr.oktopus wrote:
    > Ok, today I seems to be a little dumb.
    > What I have to do is to make mod operator (m % n) work even
    > if m is a negative number.
    >
    > This is what I mean:
    >
    > given n = 5
    >
    > 7 became 2
    > 6 .. 1
    > 5 .. 0
    > 4 .. 4
    > 3 .. 3
    > 2 .. 2
    > 1 .. 1
    > 0 .. 0
    > -1 .. 4
    > -2 .. 3
    > -3 .. 2
    > -4 .. 1
    > -5 .. 0
    > -6 .. 4
    > -7 .. 3
    >
    > I think that, for a operation like m % n, it could be:
    >
    > unsigned my_mod (int m, unsigned n)
    > {
    > unsigned um;
    >
    > if (m< 0) {
    > um = -m;
    > return n - um % n;
    > }
    > return m % n;
    > }
    >
    > but, if m is INT_MIN, for example, its two complement (um)
    > is 0, right? So, my_mod returns n (that is wrong).


    If `m' is INT_MIN, `-m' is either INT_MAX (on some very rare
    machines) or undefined (on most). The commonest "undefined" outcome
    is -INT_MIN -> INT_MIN, still negative.

    > What's the right (and smart) way?


    I don't know if this is "the" right or smart way, but:

    unsigned my_mod(int m, unsigned n) {
    if (m < 0) {
    unsigned um;
    m += (int)n; /* now m > INT_MIN */
    um = -m;
    return n - um % n;
    }
    return m % n;
    }

    This will not work if `n' is zero (obviously) or >INT_MAX.

    --
    Eric Sosman
    d
     
    Eric Sosman, Apr 9, 2011
    #5
  6. dr.oktopus

    Eric Sosman Guest

    On 4/9/2011 1:37 PM, Geoff wrote:
    > On Sat, 09 Apr 2011 09:51:59 -0700, Geoff<>
    > wrote:
    >
    >> On Sat, 9 Apr 2011 07:53:05 -0700 (PDT), "dr.oktopus"
    >> <> wrote:
    >>
    >>> Ok, today I seems to be a little dumb.
    >>> What I have to do is to make mod operator (m % n) work even
    >>> if m is a negative number.
    >>>
    >>> This is what I mean:
    >>>
    >>> given n = 5
    >>>
    >>> 7 became 2
    >>> 6 .. 1
    >>> 5 .. 0
    >>> 4 .. 4
    >>> 3 .. 3
    >>> 2 .. 2
    >>> 1 .. 1
    >>> 0 .. 0
    >>> -1 .. 4
    >>> -2 .. 3
    >>> -3 .. 2
    >>> -4 .. 1
    >>> -5 .. 0
    >>> -6 .. 4
    >>> -7 .. 3
    >>>
    >>> I think that, for a operation like m % n, it could be:
    >>>
    >>> unsigned my_mod (int m, unsigned n)
    >>> {
    >>> unsigned um;
    >>>
    >>> if (m< 0) {
    >>> um = -m;
    >>> return n - um % n;
    >>> }
    >>> return m % n;
    >>> }
    >>>
    >>> but, if m is INT_MIN, for example, its two complement (um)
    >>> is 0, right? So, my_mod returns n (that is wrong).
    >>>
    >>> What's the right (and smart) way?

    >>
    >> r = m< 0 ? -m % n : m % n;
    >> return r;

    >
    > Correction:
    >
    > r = m< 0 ? 0-m % n : m % n;
    > return r;


    Still wrong when m==INT_MIN, the case the O.P. asked about.

    --
    Eric Sosman
    d
     
    Eric Sosman, Apr 9, 2011
    #6
  7. dr.oktopus

    Eric Sosman Guest

    On 4/9/2011 2:02 PM, Willem wrote:
    > dr.oktopus wrote:
    > ) Ok, today I seems to be a little dumb.
    > ) What I have to do is to make mod operator (m % n) work even
    > ) if m is a negative number.
    >
    > % is the remainder operator, not the mod operator.
    > However, observe that the result is still equivalent within
    > the given modulus.
    >
    > Therefore, this should work:
    >
    > r = m % n;
    > if (r< 0) r += n;


    Observe that `n' is `unsigned', so `m % n' is equivalent
    to `(unsigned)m + n', which for negative `m' is equivalent to
    (in mathematical notation now) `(UINT_MAX + 1 + m) % n', which
    means the expression is wrong unless `n' divides UINT_MAX+1,
    that is, unless `n' is an integral power of 2.

    For example, with `m == -1' `n == 5u', `UINT_MAX=65535',
    this formula produces the answer 0, while the O.P. wanted 4.

    > Or if you want a single expression:
    >
    > r = ((m % n) + n) % n;


    Same problem.

    --
    Eric Sosman
    d
     
    Eric Sosman, Apr 9, 2011
    #7
  8. dr.oktopus

    Eric Sosman Guest

    On 4/9/2011 2:14 PM, io_x wrote:
    > [...]
    > unsigned myModAlternative(int m, unsigned n)
    > {unsigned mm;
    >
    > // prevent seg fault on error but wrong result
    > if(n==0) return -1;
    > if(m>=0) {mm=m; return mm%n;}
    > mm=-m;[...]


    The O.P. specifically asked about the case m==INT_MIN, and
    this "solution" has exactly the same issues as the original,
    with the question (and problems) unaddressed.

    --
    Eric Sosman
    d
     
    Eric Sosman, Apr 9, 2011
    #8
  9. dr.oktopus

    Eric Sosman Guest

    On 4/9/2011 3:40 PM, Eric Sosman wrote:
    > On 4/9/2011 2:02 PM, Willem wrote:
    >> dr.oktopus wrote:
    >> ) Ok, today I seems to be a little dumb.
    >> ) What I have to do is to make mod operator (m % n) work even
    >> ) if m is a negative number.
    >>
    >> % is the remainder operator, not the mod operator.
    >> However, observe that the result is still equivalent within
    >> the given modulus.
    >>
    >> Therefore, this should work:
    >>
    >> r = m % n;
    >> if (r< 0) r += n;

    >
    > Observe that `n' is `unsigned', so `m % n' is equivalent
    > to `(unsigned)m + n', [...]


    Oops. s/+/%/

    --
    Eric Sosman
    d
     
    Eric Sosman, Apr 9, 2011
    #9
  10. dr.oktopus

    Willem Guest

    Eric Sosman wrote:
    ) On 4/9/2011 2:02 PM, Willem wrote:
    )> Therefore, this should work:
    )>
    )> r = m % n;
    )> if (r< 0) r += n;
    )
    ) Observe that `n' is `unsigned', so `m % n' is equivalent
    ) to `(unsigned)m + n', which for negative `m' is equivalent to
    ) (in mathematical notation now) `(UINT_MAX + 1 + m) % n', which
    ) means the expression is wrong unless `n' divides UINT_MAX+1,
    ) that is, unless `n' is an integral power of 2.

    'n' was only unsigned in the example function the OP provided,
    and I didn't think it was a required feature, as he didn't mention
    it specifically.

    But even then, you're probably best off with special-casing large n:

    unsigned mod(int m, unsigned n) {
    if (n <= MAX_INT) {
    m %= (signed)n;
    if (m < 0) m += n;
    return (unsigned)m;
    } else if (m < 0) {
    return n + m;
    } else {
    return (unsigned)m;
    }
    }

    However, for normal use this should suffice:

    int mod(int m, int n) {
    m %= n;
    if (m < 0) m += n;
    return m;
    }


    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, Apr 9, 2011
    #10
  11. dr.oktopus

    Tim Rentsch Guest

    "dr.oktopus" <> writes:

    > Ok, today I seems to be a little dumb.
    > What I have to do is to make mod operator (m % n) work even
    > if m is a negative number.
    >
    > This is what I mean:
    >
    > given n = 5
    >
    > 7 became 2
    > 6 .. 1
    > 5 .. 0
    > 4 .. 4
    > 3 .. 3
    > 2 .. 2
    > 1 .. 1
    > 0 .. 0
    > -1 .. 4
    > -2 .. 3
    > -3 .. 2
    > -4 .. 1
    > -5 .. 0
    > -6 .. 4
    > -7 .. 3
    >
    > I think that, for a operation like m % n, it could be:
    >
    > unsigned my_mod (int m, unsigned n)
    > {
    > unsigned um;
    >
    > if (m < 0) {
    > um = -m;
    > return n - um % n;
    > }
    > return m % n;
    > }
    >
    > but, if m is INT_MIN, for example, its two complement (um)
    > is 0, right? So, my_mod returns n (that is wrong).
    >
    > What's the right (and smart) way?


    This statement

    return m < 0 ? n-1 - -(m+1)%n : m%n;

    gives correct results for all values of m and
    all values of n with n>0.

    Exercise: prove the expression for the m<0 case
    works (and does not have undefined behavior).
    (Hint: proving it works can be done in about 5 lines.)
     
    Tim Rentsch, Apr 10, 2011
    #11
  12. dr.oktopus

    Tim Rentsch Guest

    Eric Sosman <> writes:

    > On 4/9/2011 10:53 AM, dr.oktopus wrote:
    >> Ok, today I seems to be a little dumb.
    >> What I have to do is to make mod operator (m % n) work even
    >> if m is a negative number.
    >>
    >> This is what I mean:
    >>
    >> given n = 5
    >>
    >> 7 became 2
    >> 6 .. 1
    >> 5 .. 0
    >> 4 .. 4
    >> 3 .. 3
    >> 2 .. 2
    >> 1 .. 1
    >> 0 .. 0
    >> -1 .. 4
    >> -2 .. 3
    >> -3 .. 2
    >> -4 .. 1
    >> -5 .. 0
    >> -6 .. 4
    >> -7 .. 3
    >>
    >> I think that, for a operation like m % n, it could be:
    >>
    >> unsigned my_mod (int m, unsigned n)
    >> {
    >> unsigned um;
    >>
    >> if (m< 0) {
    >> um = -m;
    >> return n - um % n;
    >> }
    >> return m % n;
    >> }
    >>
    >> but, if m is INT_MIN, for example, its two complement (um)
    >> is 0, right? So, my_mod returns n (that is wrong).

    >
    > If `m' is INT_MIN, `-m' is either INT_MAX (on some very rare
    > machines) or undefined (on most). The commonest "undefined" outcome
    > is -INT_MIN -> INT_MIN, still negative.
    >
    >> What's the right (and smart) way?

    >
    > I don't know if this is "the" right or smart way, but:
    >
    > unsigned my_mod(int m, unsigned n) {
    > if (m < 0) {
    > unsigned um;
    > m += (int)n; /* now m > INT_MIN */
    > um = -m;
    > return n - um % n;
    > }
    > return m % n;
    > }


    Not quite right. Consider m == -n, for example.
     
    Tim Rentsch, Apr 10, 2011
    #12
  13. dr.oktopus

    Eric Sosman Guest

    On 4/10/2011 4:27 AM, Tim Rentsch wrote:
    > Eric Sosman<> writes:
    >
    >> On 4/9/2011 10:53 AM, dr.oktopus wrote:
    >>> [...]
    >>> What's the right (and smart) way?

    >>
    >> I don't know if this is "the" right or smart way, but:
    >>
    >> unsigned my_mod(int m, unsigned n) {
    >> if (m< 0) {
    >> unsigned um;
    >> m += (int)n; /* now m> INT_MIN */
    >> um = -m;
    >> return n - um % n;
    >> }
    >> return m % n;
    >> }

    >
    > Not quite right. Consider m == -n, for example.


    Good catch; thanks. (That's what I get for considering only
    the question asked and not thinking about the rest of the code...)

    --
    Eric Sosman
    d
     
    Eric Sosman, Apr 10, 2011
    #13
    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. Hari Sekhon
    Replies:
    0
    Views:
    513
    Hari Sekhon
    Jun 20, 2006
  2. ryles
    Replies:
    3
    Views:
    537
    Piet van Oostrum
    Jul 26, 2009
  3. dr.oktopus

    was: "mod operator for signed integers"

    dr.oktopus, Apr 16, 2011, in forum: C Programming
    Replies:
    19
    Views:
    442
    Keith Thompson
    Apr 18, 2011
  4. Luca Forlizzi

    was: "mod operator for signed integers"

    Luca Forlizzi, Jun 25, 2011, in forum: C Programming
    Replies:
    5
    Views:
    389
    Tim Rentsch
    Jul 6, 2011
  5. T. Onoma
    Replies:
    9
    Views:
    355
    Dave Thomas
    Dec 15, 2003
Loading...

Share This Page