Wraparound on multiply overflow

Wraparound on multiply overflow

[Paul Graham]

In C it is defined that the result of multiplying two unsigned integers
is the mathematical result modulo the value (int_max + 1), where int_max
is the maximum unsigned integer.  I'm interested in porting to Ada  a
random number generator which relies on this rule.  The code looks like:

    unsigned int X[10];
    ...
    X[0] = seed;
    for (i = 1; i <= 10; i++)
        X[i] = X[i-1] * 12345;

The idea is that a table of random looking numbers is created by
repeated multiplication of a seed by some constant.  This sequence is
guaranteed to be the same across conforming C implementations, because
of  the modulo rule I mentioned above.

Can this code be written in Ada?  A few iterations of the loop would
result in a range error or overflow.  I could suppress checks, but would
the result of an overflowing multiply be defined in that case?  Is there
any other way of emulating C's behavior for this program?  I know that
Ada has modular types, but these don't work with multiply, do they?

Paul

Re: Wraparound on multiply overflow

[Jacob Sparre Andersen]

Paul:

> In C it is defined that the result of multiplying two unsigned integers
> is the mathematical result modulo the value (int_max + 1), where int_max
> is the maximum unsigned integer.

That kind of integers are called modular types in Ada. Have
a look at 3.5.4(4) and 3.5.4(36) in the Ada Reference Manual
(1995 edition).

> I know that Ada has modular types, but these don't work with multiply,
> do they?

You might want to RTFM. 4.5.5(1):

   "The multiplying operators [...] are predefined for EVERY
    specific integer type T:"

(my emphasis) and modular types are together with signed
integer types classified as integer types.

Jacob
-- 
"You've got to build bypasses!"

Re: Wraparound on multiply overflow

[Florian Weimer]

Paul Graham <pgraham@cadence.com> writes:

> In C it is defined that the result of multiplying two unsigned integers
> is the mathematical result modulo the value (int_max + 1), where int_max
> is the maximum unsigned integer.

This is only true for unsigned types.

> Can this code be written in Ada?

Use a modular type.  They correspond to unsigned types in C.

Re: Wraparound on multiply overflow

[David Thompson]

Paul Graham <pgraham@cadence.com> wrote :
> In C it is defined that the result of multiplying two unsigned integers
> is the mathematical result modulo the value (int_max + 1), where int_max
> is the maximum unsigned integer.

More precisely, the result of any arithmetic operation in,
or conversion from a wider integer type to, an unsigned (integer)
type is taken modulo the maximum value _of that type_ plus 1,
which must be a power of two (because unsigned integer types,
and the magnitude portions of signed integer types, are
required to be in "pure binary").  For unsigned int in particular,
this is UINT_MAX in <limits.h>.  INT_MAX (uppercase;
C is case-sensitive) is the maximum value of _signed_ int.

> ... I'm interested in porting to Ada  a
> random number generator which relies on this rule.  The code looks like:
>
>     unsigned int X[10];
>     ...
>     X[0] = seed;
>     for (i = 1; i <= 10; i++)
>         X[i] = X[i-1] * 12345;
>
This code stores to X[10] which does not exist.
An array of size N in C has elements 0 .. N-1.

> The idea is that a table of random looking numbers is created by
> repeated multiplication of a seed by some constant.  This sequence is
> guaranteed to be the same across conforming C implementations, because
> of  the modulo rule I mentioned above.
>
It's guaranteed to be well-defined: not to produce a trap
or signal or garbage result or error message or any of
the many other possible faces of Undefined Behavior,
which does occur for _signed_ integer overflow in C.
But it is _not_ guaranteed to be the _same_, because
the number of (value) bits in unsigned int (or any other
integer type except as a bit-field member of a struct)
is not standardized, only (indirectly) a _minimum_
(16 for unsigned int), and using a different power-of-two
modulus gives a different sequence.

I hope (from your wording) this is just a learning exercise.
Know, if you don't already, that the numbers produced
by a Linear Congruential Generator (LCG) such as this
may "look random" to an unaided and untrained human,
but mathematically are easily distinguished from random.
No software/algorithm-generated numbers are truly random
(cf John von Neumann), but for many statistical and/or
security/cryptographic applications, there are much better
pseudo-random generators -- but not on topic here, except(?)
those provided by Ada implementations under A.5.2 (and G.2.5).

--
- David.Thompson 1 now at worldnet.att.net