# was: "mod operator for signed integers"

Discussion in 'C Programming' started by Luca Forlizzi, Jun 25, 2011.

1. ### Luca ForlizziGuest

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

>"dr.oktopus" <> writes:
>>> It's not guaranteed to work portably.

>> Why?

>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

Luca Forlizzi, Jun 25, 2011

2. ### Tim RentschGuest

Luca Forlizzi <> writes:

> 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
>
>>"dr.oktopus" <> writes:
>>>> It's not guaranteed to work portably.

>
>>> Why?

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

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

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

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

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

Tim Rentsch, Jun 27, 2011

3. ### Luca ForlizziGuest

On 27 Giu, 19:47, Tim Rentsch <> wrote:
> Luca Forlizzi <> writes:

[snip]
> >>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

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

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

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

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

Luca Forlizzi, Jun 30, 2011
4. ### Tim RentschGuest

Luca Forlizzi <> writes:

> On 27 Giu, 19:47, Tim Rentsch <> wrote:
>> Luca Forlizzi <> 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.

Tim Rentsch, Jul 3, 2011
5. ### Luca ForlizziGuest

On 3 Lug, 23:23, Tim Rentsch <> wrote:
> Luca Forlizzi <> writes:
> > On 27 Giu, 19:47, Tim Rentsch <> wrote:
> >> Luca Forlizzi <> 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

Luca Forlizzi, Jul 5, 2011
6. ### Tim RentschGuest

Luca Forlizzi <> writes:

> On 3 Lug, 23:23, Tim Rentsch <> wrote:
>> Luca Forlizzi <> writes:
>> > On 27 Giu, 19:47, Tim Rentsch <> wrote:
>> >> Luca Forlizzi <> 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.

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

Tim Rentsch, Jul 6, 2011