mod operator for signed integers

D

dr.oktopus

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?
 
G

Geoff

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;
 
W

Willem

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
 
E

Eric Sosman

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.
 
E

Eric Sosman

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.
 
E

Eric Sosman

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

Eric Sosman

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/+/%/
 
W

Willem

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
 
T

Tim Rentsch

dr.oktopus said:
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.)
 
T

Tim Rentsch

Eric Sosman said:
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.


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.
 
E

Eric Sosman

Eric Sosman said:
[...]
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...)
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top