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 >> direct access to the entire state in Nico's design. >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