was: "mod operator for signed integers"

[Luca Forlizzi]

hello I try to "resurrect" the thread "was: "mod operator for signed
integers"" because I tried to find the answers to the following
questions posed by Tim Rentsch

If we have 'int m;' and 'unsigned n;', with m in [ INT_MIN .. -1 ]
and n in [ 1 .. UINT_MAX ], consider the expression

(m + INT_MAX) + n

Question 1: What is the maximum value of this expression,
considered as a mathematical expression?

it should be (INT_MAX-1)+UINT_MAX, which is greater then the maximum
value representable in an unsigned int. So the expression can exhibit
overflow

Question 2: Considered as a C expression, what is the
type of the expression? (Hint: there is more than one
possibility.)

this confuses me, since at first glance I only see one possibility,
unsigned int.
Indeed, m and INT_MAX have type int. Maybe UINT_MAX is the tricky one:
if an int can
represent all values of unsigned int, UINT_MAX has int type (by
5.2.4.2.1 p1). So in this case the whole expression has type int,
while in all other cases it has type unsigned int, because of the
usual arithmetic convertions

Question 3: Have you tried working through the solution
that was posted, to see how it works?

the proposed solution to the OP's question was:
m < 0 ? n-1 - -(m+1)%n : m%n

I tried to prove that it's correct (for the case m<0) but I did not
succeed
yet. My difficulty is maybe that I am unable to find an analitical
definition
of what result the OP was expecting. Could someone provide more hints?

LF

 

[Tim Rentsch]

hello I try to "resurrect" the thread "was: "mod operator for signed
integers"" because I tried to find the answers to the following
questions posed by Tim Rentsch

If we have 'int m;' and 'unsigned n;', with m in [ INT_MIN .. -1 ]
and n in [ 1 .. UINT_MAX ], consider the expression

(m + INT_MAX) + n

Question 1: What is the maximum value of this expression,
considered as a mathematical expression?

it should be (INT_MAX-1)+UINT_MAX,
Yes.

which is greater then the maximum value representable in an
unsigned int.

Yes, and also greater than INT_MAX.

So the expression can exhibit overflow

You mean it can exhibit modular behavior when the sum is
performed in type 'unsigned int'.

If the sum were performed in type 'int', then there could
be overflow.

this confuses me, since at first glance I only see one possibility,
unsigned int.
Indeed, m and INT_MAX have type int. Maybe UINT_MAX is the tricky one:
if an int can
represent all values of unsigned int, UINT_MAX has int type (by
5.2.4.2.1 p1). So in this case the whole expression has type int,
while in all other cases it has type unsigned int, because of the
usual arithmetic convertions

C allows implementations where UINT_MAX == INT_MAX. In C99
(as amended by a later TC, I believe), the rules for integer
promotions specify (presumably unintentionally) that such
implementation "promote" unsigned int to int. In such cases
the expression in question could be of type 'int'.

the proposed solution to the OP's question was:
m < 0 ? n-1 - -(m+1)%n : m%n

I tried to prove that it's correct (for the case m<0) but I did not
succeed
yet. My difficulty is maybe that I am unable to find an analitical
definition
of what result the OP was expecting. Could someone provide more hints?

Here is a start. I will use MOD to mean modulo, % for
the C remainder operation. We want m MOD n

m MOD n === (n + m ) MOD n
=== ((n-1) + (m+1)) MOD n
=== ((n-1) - -(m+1)) MOD n
=== ((n-1) MOD n - (-(m+1)) MOD n) MOD n

Q1: What is (n-1) MOD n (assuming n > 0)?

Q2: Can you relate (-(m+1)) MOD n to -(m+1)%n, given that
-(m+1) >= 0 and n > 0?

Q3: How can you get rid of the final outside 'MOD n'?

 

[Luca Forlizzi]

If we have 'int m;' and 'unsigned n;', with m in [ INT_MIN .. -1 ]
and n in [ 1 .. UINT_MAX ], consider the expression
  (m + INT_MAX) + n
Question 1:  What is the maximum value of this expression,
considered as a mathematical expression?

it should be (INT_MAX-1)+UINT_MAX,
Yes.

which is greater then the maximum value representable in an
unsigned int.

Yes, and also greater than INT_MAX.

So the expression can exhibit overflow

You mean it can exhibit modular behavior when the sum is
performed in type 'unsigned int'.

If the sum were performed in type 'int', then there could
be overflow.

yes, thanks for the correction

C allows implementations where UINT_MAX == INT_MAX.  In C99
(as amended by a later TC, I believe), the rules for integer
promotions specify (presumably unintentionally) that such
implementation "promote" unsigned int to int.  In such cases
the expression in question could be of type 'int'.

That's what I had guessed.
However I now remember from other discussion that the possibility of
promoting unsigned int to int was introduced unintentionally in C99
TC2. I think that Larry Jones confirmed that the change was
unintentional. In the latest C1X draft such a possibility is rules
out, because the text says that the integer promotions apply to
integer types "other than int or unsigned int" (with rank less than
or equal to the rank of int).
Then I think that in C89, unamended C99 and the current draft of C1X,
there is just one posssibility for the type of (m + INT_MAX) + n,
which is unsigned int, because m and INT_MAX are int and n in unsigned
int.

In the previous days I developed a proof different from the one you
give below, based on the fact that m MOD n is equal to the difference
between m and the maximum integer x which is a multiple of n (I mean
x=k*n for some integer k, is "multiple" the correct english term?) and
is not bigger than m. For me it was easier given that I don't have
much experience with the MOD properties.
In any case thanks a lot for your proof sketch, which seems to me
almost complete, is very instructive. I will try to answer you
questions

Here is a start.  I will use MOD to mean modulo, % for
the C remainder operation.  We want m MOD n

   m MOD n   ===   (n     +   m   )  MOD n
             ===   ((n-1) +  (m+1))  MOD n
             ===   ((n-1) - -(m+1))  MOD n
             ===   ((n-1) MOD n  -  (-(m+1)) MOD n)  MOD n

all the steps but the last one are straightforward. I can see that the
last one comes from
the fact that (a+b) MOD c === (a MOD c + b MOD c) MOD c, which I
verified with a picture

Q1:  What is (n-1) MOD n (assuming n > 0)?

it should be equal to n-1

Q2:  Can you relate (-(m+1)) MOD n to -(m+1)%n, given that
     -(m+1) >= 0 and n > 0?

they should be equal

Q3:  How can you get rid of the final outside 'MOD n'?

it should follow from the same property you used in the last step
above:
(a+b) MOD c === (a MOD c + b MOD c) MOD c
or, more simply, one can say that since -(m+1)%n is a positive number
not greater than n-1,
n-1 - (-(m+1)%n) is also a positive number not greater than n-1.
For any positive number x not greater than n-1, x MOD N is equal to x.

Thanks for your time, by the way

 

[Tim Rentsch]

Luca Forlizzi <[email protected]> writes:

[snip]
In the previous days I developed a proof different from the one you
give below, based on the fact that m MOD n is equal to the difference
between m and the maximum integer x which is a multiple of n (I mean
x=k*n for some integer k, is "multiple" the correct english term?) and
is not bigger than m. For me it was easier given that I don't have
much experience with the MOD properties.

[snip]

Thanks for your time, by the way

You are most welcome, sir. Always a pleasure posting for
people who are polite and appreciative.

 

[Luca Forlizzi]

Luca Forlizzi <[email protected]> writes:

[snip]
In the previous days I developed a proof different from the one you
give below, based on the fact that m MOD n is equal to the difference
between m and the maximum integer x which is a multiple of n (I mean
x=k*n for some integer k, is "multiple" the correct english term?) and
is not bigger than m. For me it was easier given that I don't have
much experience with the MOD properties.

[snip]

Thanks for your time, by the way

You are most welcome, sir.  Always a pleasure posting for
people who are polite and appreciative.

Time and knowledge are among the few important things in life, for me,
so I very much appreciate when people spend their time to share it
with me.
Since you didn't comment my answers the questions, I guess you
consider them, more or less, correct.

thanks again
Luca

 

[Tim Rentsch]

[snip]
In the previous days I developed a proof different from the one you
give below, based on the fact that m MOD n is equal to the difference
between m and the maximum integer x which is a multiple of n (I mean
x=k*n for some integer k, is "multiple" the correct english term?) and
is not bigger than m. For me it was easier given that I don't have
much experience with the MOD properties.

[snip]

Thanks for your time, by the way

You are most welcome, sir. Always a pleasure posting for
people who are polite and appreciative.

Time and knowledge are among the few important things in life, for me,
so I very much appreciate when people spend their time to share it
with me.
Since you didn't comment my answers the questions, I guess you
consider them, more or less, correct.

Yes, with only a minor observation that at one point
you say 'positive' but what's right is 'positive
or zero'.