Re: Wraparound on multiply overflow

["David Thompson" <david.thompson1@worldnet.att.net>]

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