Luca Forlizzi
6/30/2011 9:04:00 AM
On 27 Giu, 19:47, Tim Rentsch <t...@alumni.caltech.edu> wrote:
> Luca Forlizzi <luca.forli...@gmail.com> 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