# mod operator for signed integers

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

1. ### dr.oktopusGuest

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

2. ### GeoffGuest

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

3. ### GeoffGuest

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
4. ### WillemGuest

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
5. ### Eric SosmanGuest

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
6. ### Eric SosmanGuest

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;

--
Eric Sosman
d

Eric Sosman, Apr 9, 2011
7. ### Eric SosmanGuest

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
8. ### Eric SosmanGuest

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;[...]

this "solution" has exactly the same issues as the original,
with the question (and problems) unaddressed.

--
Eric Sosman
d

Eric Sosman, Apr 9, 2011
9. ### Eric SosmanGuest

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
10. ### WillemGuest

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
11. ### Tim RentschGuest

"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
12. ### Tim RentschGuest

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
13. ### Eric SosmanGuest

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