Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > mod operator for signed integers

Reply
Thread Tools

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?
 
Reply With Quote
 
 
 
 
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;
 
Reply With Quote
 
 
 
 
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;
 
Reply With Quote
 
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
 
Reply With Quote
 
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
 
Reply With Quote
 
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
 
Reply With Quote
 
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
 
Reply With Quote
 
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
 
Reply With Quote
 
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
 
Reply With Quote
 
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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
was: "mod operator for signed integers" Luca Forlizzi C Programming 5 07-06-2011 10:00 PM
was: "mod operator for signed integers" dr.oktopus C Programming 19 04-18-2011 03:37 PM
difference between import from mod.func() and x=mod.func() Hari Sekhon Python 0 06-20-2006 08:07 AM
operator % and signed integers Thomas Matthews C++ 8 12-28-2005 05:33 PM
operator % and signed integers Thomas Matthews C Programming 9 12-28-2005 05:33 PM



Advertisments