```Newsgroups: sci.crypt
Path: cactus.org!ritter
From: ritter@cactus.org (Terry Ritter)

Subject: Re: IBM-PC random generator, source included
Message-ID: <1992Jun26.231737.4649@cactus.org>
Organization: Capital Area Central Texas UNIX Society, Austin, Tx
References: <2673@accucx.cc.ruu.nl> <1992Jun23.080147.15804@cactus.org>
+           <1992Jun26.075116.20752@jarvis.csri.toronto.edu>
Date: Fri, 26 Jun 1992 23:17:37 GMT

In <1992Jun26.075116.20752@jarvis.csri.toronto.edu>
colin@eecg.toronto.edu (Colin Plumb) writes:

>In article <1992Jun25.071702.8945@cactus.org> ritter@cactus.org
>   (Terry Ritter) writes:
>> It should be obvious that if we have a well-designed 32-bit
>> RNG and use it to produce "a few hundred thousand" consecutive
>> 32-bit internal state results, there will be no duplicates at
>> all.  A normal statistical RNG steps through (almost) its entire
>> state without repetition.  But we may not agree that we have

>Unfortunately, it's false. You can expect a collision at around
>the 64K mark.  Here's the proof: given n random numbers x_1..x_n
>in some range 0..N-1, there are no duplicates if and only if each
>of the n(n+1)/2 pairs is distinct.  Thus, it is equivalent to generating
>n(n+1) random numbers and checking that each even-odd pair is distinct.
>If n = 2^16, n(n+1) is just over 2^32, and if N is 2^32, the expected
>number of duplicates is just over 1.

A bit quick on the draw there, aren't we?

Although I appreciate the introduction to birthday testing,
your comment on my comment is simply wrong.

Most computer language RNG's are small (32 bits total state)
Linear Congruential Generators or Multiplicative generators
designed to traverse their entire 32-bit state-space.  If you
use one of these generators, and use the entire seed value
from it, or use a real number translated in such a way as to
maintain the full 32-bit range, then you will indeed see the
RNG simply traverse 2**32 - 1 or 2**32 states without
repetition.  There will be no collisions.

Is this random?  No, but it is a good distribution.  It is
also the way that the simple statistical RNG's work.

---
Terry Ritter    ritter@cactus.org

```