braner@batcomputer.tn.cornell.edu (Moshe Braner) (02/11/89)
/* * Generate random integers using the shift-register algorithm. * Copyright Moshe Braner, Nov. 1987. All rights reserved. * Permission granted for noncommercial usage. * * The algorithm here is basically x[i] = x[i-31] EOR x[i-7]. * (Could possibly improve by using x[i] = x[i-127] EOR x[i-63]?) * Each x[i] here is 32 bits wide, could also be 16 or whatever. */ /* "#define FRAND" to include the floating-point stuff */ static long gla[31]; /* array of randoms to shift */ static int glf=1; /* seeding flag */ static long *glp, *glq, *gls, *glt; /* pointers to shift register */ #ifdef FRAND static double glfm; #endif /* * Seed ran5 - always do this first. * The seed is any positive integer. */ void sran5(seed) int seed; { register int i; register long x; x = (long) seed; for(i=0; i<100; i++) x = 31821*x+1; for(i=0; i<31; i++) { x = 31821*x+1; gla[i] = x; } glf = 0; gls = &gla[0]; glp = &gla[0]; glq = &gla[24]; glt = &gla[31]; #ifdef FRAND glfm = 1.0; for (i=0; i<31; i++) glfm *= 0.5; /* EXACTLY 2^(-31) */ #endif } /* * The basic ran5() generator, which returns * a long integer uniform between 0 and 2^31-1. */ long ran5() { register long x, y; /* short form: x = ((*glp) ^ (*glq)); if (++glp == glt) glp = gls; if (++glq == glt) glq = gls; return (x & 0x7FFFFFFF); safer form: */ if (glf) sran5(0); y = x = ((*glp) ^ (*glq)); /* here FORTRAN dies */ x <<= 1; if (y < 0) x += 1; /* wish C had a 'rotate' operation */ *glp = x; if (++glp == glt) glp = gls; if (++glq == glt) glq = gls; return (y & 0x7FFFFFFF); } #ifdef FRAND /* * The floating-point ran5() generator. * Returns a double uniform on [0.0,1.0). */ double fran5() { return ((double)ran5() * glfm); } #endif FRAND
dg@lakart.UUCP (David Goodenough) (02/13/89)
braner@batcomputer.tn.cornell.edu (Moshe Braner) sez: > /* > * The algorithm here is basically x[i] = x[i-31] EOR x[i-7]. > * (Could possibly improve by using x[i] = x[i-127] EOR x[i-63]?) > * Each x[i] here is 32 bits wide, could also be 16 or whatever. > */ Sounds to me like you're running 16 or 32 LCG's in parallel. This means that: 1. Individual bits will have all the problems associated with a LCG. 2. Supposing all your seed values have bit 7 == 0. You'll never ever get a 1 bit in bit 7. A somwhat remote possibility, but it could occur. Comments anyone? -- dg@lakart.UUCP - David Goodenough +---+ IHS | +-+-+ ....... !harvard!xait!lakart!dg +-+-+ | AKA: dg%lakart.uucp@xait.xerox.com +---+
rayt@cognos.uucp (R.) (02/14/89)
Actually, CACM had an article on random number generators
a few months back (Nov or Dec) and gives the pseudocode for
some statistically PROVEN random generators.
--
Ray Tigg | Cognos Incorporated
| P.O. Box 9707
(613) 738-1440 x5013 | 3755 Riverside Dr.
UUCP: uunet!mitel!sce!cognos!rayt | Ottawa, Ontario CANADA K1G 3Z4
gwyn@smoke.BRL.MIL (Doug Gwyn ) (02/16/89)
In article <5269@cognos.UUCP> rayt@cognos.UUCP (R.) writes: >Actually, CACM had an article on random number generators >a few months back (Nov or Dec) and gives the pseudocode for >some statistically PROVEN random generators. Virtually all PRNG schemes in common use have provable statistical behavior. That doesn't mean they're always suitable. In fact I'm not enthised about that CACM article.
schwartz@shire.cs.psu.edu (Scott Schwartz) (02/16/89)
In article <9653@smoke.BRL.MIL>, gwyn@smoke (Doug Gwyn ) writes: >Virtually all PRNG schemes in common use have provable >statistical behavior. That doesn't mean they're always >suitable. In fact I'm not enthised about that CACM article. Didn't the article state that the generators they talked about were to be considered a lower bound in quality? In other words, there is now no excuse to use a |worse| PRNG than the ones in the article. -- Scott Schwartz <schwartz@shire.cs.psu.edu>
news@ism780c.isc.com (News system) (02/16/89)
In article <5269@cognos.UUCP> rayt@cognos.UUCP (R.) writes: >Actually, CACM had an article on random number generators >a few months back (Nov or Dec) and gives the pseudocode for >some statistically PROVEN random generators. > The article was in the Oct 88 issue of CACM. However, before you use the algorithm I suggest you read the FEB 88 issue. The letter on page 172 points out some problems. Marv Rubinstein
rayt@cognos.uucp (R.) (02/18/89)
In article <9653@smoke.BRL.MIL> gwyn@brl.arpa (Doug Gwyn) writes in response to my mention of the recent CACM article on random generators, that: "Virtually all PRNG schemes in common use have provable statistical behavior. That doesn't mean they're always suitable. In fact I'm not enthised about that CACM article." Are you refering to the need to have skewed or otherwise non-normal distributions? Also I'm interested in knowing what you found wanting in the CACM article. Ray Tigg -- Ray Tigg | Cognos Incorporated | P.O. Box 9707 (613) 738-1440 x5013 | 3755 Riverside Dr. UUCP: uunet!mitel!sce!cognos!rayt | Ottawa, Ontario CANADA K1G 3Z4
braner@batcomputer.tn.cornell.edu (Moshe Braner) (02/22/89)
[David Goodenough pointed out some supposed problems with my PRNG] My method (posted here recently) is NOT parallel LCGs, it is 16 or 32 parallel occurences of the (in)famous "shift register" algorithm. While it is true that each bit position, taken alone, is not a very good basis for PRNs, tests show that the 32 independent "registers" provide pretty good 32-bit random long ints. With my method there is no actual shifting of the bits in each register, instead I just bump a pointer to a position on a ring. MUCH faster. (To make merrier, I also roll one column in the matrix of bits (around the OTHER axis than the rows used for the "shift" of the registers) one bit per call. But that is not essential.) For seeding, I take ONE seed int and generate 31 "random" seeds out of it using a LCG (for the seeding only). It is true that, with VERY small probability, one bit position may be stuck at all 0's, but the extra rolling mentioned above will destroy that state. I still claim that this is a very fast generator with no deficiencies known to me. Anybody got their favorite killer PRNG tests ready to shoot? :-) - Moshe Braner Cornell Theory Center, 265 Olin Hall, Cornell University, Ithaca, NY 14853 (607) 255-9401 (Work) <braner@tcgould.tn.cornell.edu> (INTERNET) <braner@crnlthry> or <braner@crnlcam> (BITNET)
cik@l.cc.purdue.edu (Herman Rubin) (02/23/89)
In article <5313@cognos.UUCP>, rayt@cognos.uucp (R.) writes: > In article <9653@smoke.BRL.MIL> gwyn@brl.arpa (Doug Gwyn) writes > in response to my mention of the recent CACM article on random > generators, that: > > "Virtually all PRNG schemes in common use have provable > statistical behavior. That doesn't mean they're always > suitable. In fact I'm not enthised about that CACM article." They have good uniformity of distribution. But this by itself is meaningless. Suppose that the n-th PRN is n (modulo k). Then the distribution is uniform. Or one can use quasi-random numbers, such as the fractional part of n*2(.5). These are provably more uniform than random numbers. If they are to be used for estimating the integral of a "smooth" function, even in many dimensions, and are used one-at- a-time, then multidimensional quasi-random numbers are likely to be much better than random numbers. But the problem is independence. Suppose that one is using an acceptance- rejection or acceptance-replacement scheme to generate exponential or normal random variables. Then there is interaction between the uniform input at different places. So independence becomes important. The only really good ones here are the "cryptographically strong" generators, which are quite expensive. Some of the procedures with long seeds, like x[n] = x[n-460] XOR x[n-607] with a seed of 607 words of the longest type which could be used, are probably fairly good. Using any type of physical random numbers XORed with the pseudo-random numbers is likely to improve the performance; radioactive sources, using the parity of the number of counts in intervals, are quite good and even improve with a quite considerable dead time. If repeatability is needed, the physical random numbers should be stored. > Are you refering to the need to have skewed or otherwise non-normal > distributions? Also I'm interested in knowing what you found > wanting in the CACM article. The type of non-uniform random variables wanted has little to do with the problem. Now sometimes good results can be obtained with quasi- random numbers; in this case, one needs a QRNG, not a PRNG. But the circumstances in which QRNs work well are more restrictive. -- Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907 Phone: (317)494-6054 hrubin@l.cc.purdue.edu (Internet, bitnet, UUCP)