Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > was: "mod operator for signed integers"

Reply
Thread Tools

was: "mod operator for signed integers"

 
 
Luca Forlizzi
Guest
Posts: n/a
 
      06-25-2011
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" <(E-Mail Removed)> 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
 
Reply With Quote
 
 
 
 
Tim Rentsch
Guest
Posts: n/a
 
      06-27-2011
Luca Forlizzi <(E-Mail Removed)> 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" <(E-Mail Removed)> 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'?
 
Reply With Quote
 
 
 
 
Luca Forlizzi
Guest
Posts: n/a
 
      06-30-2011
On 27 Giu, 19:47, Tim Rentsch <(E-Mail Removed)> wrote:
> Luca Forlizzi <(E-Mail Removed)> 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
 
Reply With Quote
 
Tim Rentsch
Guest
Posts: n/a
 
      07-03-2011
Luca Forlizzi <(E-Mail Removed)> writes:

> On 27 Giu, 19:47, Tim Rentsch <(E-Mail Removed)> wrote:
>> Luca Forlizzi <(E-Mail Removed)> 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.
 
Reply With Quote
 
Luca Forlizzi
Guest
Posts: n/a
 
      07-05-2011
On 3 Lug, 23:23, Tim Rentsch <(E-Mail Removed)> wrote:
> Luca Forlizzi <(E-Mail Removed)> writes:
> > On 27 Giu, 19:47, Tim Rentsch <(E-Mail Removed)> wrote:
> >> Luca Forlizzi <(E-Mail Removed)> 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
 
Reply With Quote
 
Tim Rentsch
Guest
Posts: n/a
 
      07-06-2011
Luca Forlizzi <(E-Mail Removed)> writes:

> On 3 Lug, 23:23, Tim Rentsch <(E-Mail Removed)> wrote:
>> Luca Forlizzi <(E-Mail Removed)> writes:
>> > On 27 Giu, 19:47, Tim Rentsch <(E-Mail Removed)> wrote:
>> >> Luca Forlizzi <(E-Mail Removed)> 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'.
 
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
Convert a signed binary number into a signed one ? Rob1bureau VHDL 1 02-27-2010 12:13 AM
signed(12 downto 0) to signed (8 downto 0) kyrpa83 VHDL 1 10-17-2007 06:58 PM
Use of bitwise operator for signed number arunaling@yahoo.co.in C Programming 6 06-07-2006 12:30 PM
operator % and signed integers Thomas Matthews C Programming 9 12-28-2005 05:33 PM
operator >> on signed in c89 Simon Aittamaa C Programming 2 10-12-2005 06:42 PM



Advertisments