COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

Unsigned Integer Overflow on Multiplication and Division

• Follow

```What do the standards say about when you multiply two unsigned integers and
the result is too big?

Is the compiler required to give you the actual result modulo 2^32 or 2^64,
or is the behavior pretty much undefined?

Thanks, Datesfat

```
 0

```On 5/13/2010 3:52 PM, Datesfat Chicks wrote:
> What do the standards say about when you multiply two unsigned integers
> and the result is too big?
>
>
> Is the compiler required to give you the actual result modulo 2^32 or
> 2^64, or is the behavior pretty much undefined?

--
Eric Sosman
esosman@ieee-dot-org.invalid
```
 0

```"Datesfat Chicks" <datesfat.chicks@gmail.com> writes:
> What do the standards say about when you multiply two unsigned integers and
> the result is too big?
>
>
> Is the compiler required to give you the actual result modulo 2^32 or 2^64,
> or is the behavior pretty much undefined?

For future reference, the latest post-C99 draft is freely available at
<http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf>.

6.2.5p9 says:

... A computation involving unsigned operands can never overflow,
because a result that cannot be represented by the resulting
unsigned integer type is reduced modulo the number that is one
greater than the largest value that can be represented by the
resulting type.

So yes, for a 32-bit unsigned integer type, the result of any arithmetic
operation is reduced module 2^32; likewise for 64.

--
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Nokia
"We must do something.  This is something.  Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
```
 0

```"Eric Sosman" <esosman@ieee-dot-org.invalid> wrote in message
news:hshlhg\$cdb\$3@news.eternal-september.org...
> On 5/13/2010 3:52 PM, Datesfat Chicks wrote:
>> What do the standards say about when you multiply two unsigned integers
>> and the result is too big?
>>
>>
>> Is the compiler required to give you the actual result modulo 2^32 or
>> 2^64, or is the behavior pretty much undefined?
>
>     What does your textbook say?

Thanks for the humor, but this is not a homework problem.

I'm implementing a pseudo-random number generator using a microcontroller C
compiler, and (as I'm sure you know) arithmetic modulo 2^32 is what I'm
looking for.

I know what the library that comes with the compiler will do (it is fairly
obvious on a microcontroller because of the instruction set), but I'm just
curious if that is required behavior or coincidentally convenient behavior.

Datesfat

```
 0

```On 2010-05-13, Datesfat Chicks <datesfat.chicks@gmail.com> wrote:
> What do the standards say about when you multiply two unsigned integers and
> the result is too big?

They don't, because the result is never too big.  That's because the
operation always occurs modulo FOO_MAX+1.  :)

-s
--
Copyright 2010, all wrongs reversed.  Peter Seebach / usenet-nospam@seebs.net
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
```
 0

```On 5/13/2010 4:07 PM, Datesfat Chicks wrote:
> "Eric Sosman" <esosman@ieee-dot-org.invalid> wrote in message
> news:hshlhg\$cdb\$3@news.eternal-september.org...
>> On 5/13/2010 3:52 PM, Datesfat Chicks wrote:
>>> What do the standards say about when you multiply two unsigned integers
>>> and the result is too big?
>>>
>>>
>>> Is the compiler required to give you the actual result modulo 2^32 or
>>> 2^64, or is the behavior pretty much undefined?
>>
>> What does your textbook say?
>
> Thanks for the humor, but this is not a homework problem.

No implication of homework intended.  Still: What does your
textbook say?  If you are such a C newbie that you need to ask so
basic a question, you *need* a textbook.  Really, truly.  Get one.

(Odd that someone unversed in the use of unsigned arithmetic

> I'm implementing a pseudo-random number generator using a
> microcontroller C compiler, and (as I'm sure you know) arithmetic modulo
> 2^32 is what I'm looking for.
>
> I know what the library that comes with the compiler will do (it is
> fairly obvious on a microcontroller because of the instruction set), but
> I'm just curious if that is required behavior or coincidentally
> convenient behavior.

no sense, try posting a confusing passage or two (and mention what
textbook they come from).

--
Eric Sosman
esosman@ieee-dot-org.invalid
```
 0

```"Keith Thompson" <kst-u@mib.org> wrote in message
news:lnbpcj1scz.fsf@nuthaus.mib.org...
> "Datesfat Chicks" <datesfat.chicks@gmail.com> writes:
>> What do the standards say about when you multiply two unsigned integers
>> and
>> the result is too big?
>>
>>
>> Is the compiler required to give you the actual result modulo 2^32 or
>> 2^64,
>> or is the behavior pretty much undefined?
>
> For future reference, the latest post-C99 draft is freely available at
> <http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf>.
>
> 6.2.5p9 says:
>
>    ... A computation involving unsigned operands can never overflow,
>    because a result that cannot be represented by the resulting
>    unsigned integer type is reduced modulo the number that is one
>    greater than the largest value that can be represented by the
>    resulting type.
>
> So yes, for a 32-bit unsigned integer type, the result of any arithmetic
> operation is reduced module 2^32; likewise for 64.

Ah, OK, and how does one know what standards a compiler has to adhere to?

Are there any standards earlier than C99?

Thanks.

Datesfat

```
 0

```"Datesfat Chicks" <datesfat.chicks@gmail.com> writes:
> "Keith Thompson" <kst-u@mib.org> wrote in message
> news:lnbpcj1scz.fsf@nuthaus.mib.org...
[...]
> Ah, OK, and how does one know what standards a compiler has to adhere to?

Read its documentation and/or check the value of __STDC__ and/or
__STDC_VERSION__ (look them up in n1256).  Note that many compilers
have different conformance characteristics depending on how you
invoke them.

> Are there any standards earlier than C99?

See question 11.1 of the comp.lang.c FAQ, <http://www.c-faq.com/>.

The first edition of Kernighan & Ritchie (K&R1) was the de facto
pre-ANSI standard.

In addition, there have been three Technical Corrigenda on top of
C99, all of which are incorporated into n1256.  The C99 standard
officially supersedes the C90 standard, but adoption has not been
universal.  Work is in progress on a new ISO C standard that will
supersede C99, currently referred to as C201X; the latest draft I'm
aware of is n1425.pdf, available from the same place as n1256.pdf.

--
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Nokia
"We must do something.  This is something.  Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
```
 0

```On 2010-05-13, Datesfat Chicks <datesfat.chicks@gmail.com> wrote:
> Ah, OK, and how does one know what standards a compiler has to adhere to?

It never HAS to adhere to ANY standards.

But if it doesn't, it doesn't adhere to any standards.

> Are there any standards earlier than C99?

Yes, C89.

In practice, most compilers will be quite good about anything in C89, and
pretty good about most of C99, with some exceptions.  I use C99 features
like VLAs and compound literals without worrying about it, and it doesn't
seem to cause me any trouble.

-s
--
Copyright 2010, all wrongs reversed.  Peter Seebach / usenet-nospam@seebs.net
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
```
 0

8 Replies
549 Views

Similiar Articles:

7/22/2012 12:51:38 AM