NetNews Usenet Archive 1992 #26/NN_1992_26.iso/spool/comp/lang/c/16166

Internet Message Format | 1992-11-08 | 2.9 KB

Path: sparky!uunet!spool.mu.edu!agate!dog.ee.lbl.gov!horse.ee.lbl.gov!torek
From: [e-mail] (Chris Torek)
Newsgroups: comp.lang.c
Subject: Re: Random Number Generator
Date: 8 Nov 1992 10:58:19 GMT
Organization: Lawrence Berkeley Laboratory, Berkeley
Lines: 70
Message-ID: <[e-mail]>
References: <[e-mail]> <[e-mail]> <[e-mail]> <[e-mail]>
Reply-To: [e-mail] (Chris Torek)
NNTP-Posting-Host: 128.3.112.15

>In article <[e-mail]> I wrote:
>> Time for another Netnews Rerun....

In article <[e-mail]> [e-mail]
(Steve Summit) writes:
>Chris may be thinking of an earlier draft.  The example
>implementation in the published ANSI standard (ANSI X3.159-1989,
>sec. 4.10.2.2, p. 155) is not a pure linear congruential random
>number generator; rather, it is a LCRNG with a 32-bit (or more)
>state value which returns 15 bits from the *top* (most
>significant) half.  Therefore, its actual return values are
>*not* subject to these particularly unfortunate regularities.
>(To recap: the low-order N bits of a pure LCRNG repeat with
>period 2-to-the-N.)

Several comments:

This is a problem with netnews reruns:  They get out of date.  I try to
take time to edit them, but....

The parenthetical recap is not quite right.  Rather, given an LCRNG
of the form:

    X[i+1] = (X[i] * a + c) mod m

(which has period <= m; if a and c are well-chosen, the period is
exactly m), we define a new sequence:

    Y[j] = X[j] mod d

If m is congruent to 0 mod d (i.e., m % d = 0), the sequence in Y
will repeat with period <= d.  The definition of Y corresponds
perfectly with taking rand() % d (think of X[j] as the j'th return
value from rand()).

Since typical C implementations of rand() use LCRNG's with 2^k (for
integer k, usually 16 or 32) as their `m', and since 2^k mod 2^N is 0,
the low order bits repeat with period 2^N.  But this only holds when
m = 2^k, not for LCRNG's in general.

>In other words, the prevailing advice is to consign rand() % N to
>the same dustbin that gets() has been demoted to: the code is
>there, and it is theoretically legal to use it, but you mustn't.

Right.

>I happen to think that the rand() % N problem is so common, and is
>so easily made by the unwary, that it's worth fixing ...

This is rather difficult (see your own note 2).  For what it is worth,
I ran a few simple 2-d scatter plot tests on the `ANSI C' generator
(which, incidentally, appears below), and saw no obvious patterns, but
I would want to know more about it before trusting it much.

/* ANSI C `portable random number generator' */
static unsigned long int next = 1;

int rand(void)        /* RAND_MAX assumed to be 32767 */
{
    next = next * 1103515245 + 12345;
    return (unsigned int)(next / 65536) % 32768;
}

void srand(unsigned int seed)
{
    next = seed;
}
--
In-Real-Life: Chris Torek, Lawrence Berkeley Lab CSE/EE ([phone])
Berkeley, CA        Domain:    [e-mail]