Velocity Reviews > mod operator for signed integers

# mod operator for signed integers

dr.oktopus
Guest
Posts: n/a

 04-09-2011
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?

Geoff
Guest
Posts: n/a

 04-09-2011
On Sat, 9 Apr 2011 07:53:05 -0700 (PDT), "dr.oktopus"
<(E-Mail Removed)> 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
Guest
Posts: n/a

 04-09-2011
On Sat, 09 Apr 2011 09:51:59 -0700, Geoff <(E-Mail Removed)>
wrote:

>On Sat, 9 Apr 2011 07:53:05 -0700 (PDT), "dr.oktopus"
><(E-Mail Removed)> 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;

Willem
Guest
Posts: n/a

 04-09-2011
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

Eric Sosman
Guest
Posts: n/a

 04-09-2011
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
http://www.velocityreviews.com/forums/(E-Mail Removed)d

Eric Sosman
Guest
Posts: n/a

 04-09-2011
On 4/9/2011 1:37 PM, Geoff wrote:
> On Sat, 09 Apr 2011 09:51:59 -0700, Geoff<(E-Mail Removed)>
> wrote:
>
>> On Sat, 9 Apr 2011 07:53:05 -0700 (PDT), "dr.oktopus"
>> <(E-Mail Removed)> 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
(E-Mail Removed)d

Eric Sosman
Guest
Posts: n/a

 04-09-2011
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
(E-Mail Removed)d

Eric Sosman
Guest
Posts: n/a

 04-09-2011
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
(E-Mail Removed)d

Eric Sosman
Guest
Posts: n/a

 04-09-2011
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
(E-Mail Removed)d

Willem
Guest
Posts: n/a

 04-09-2011
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