Re: SeedRandom oddity/flaw/bug/imperfection

*To*: mathgroup at smc.vnet.net*Subject*: [mg5249] Re: SeedRandom oddity/flaw/bug/imperfection*From*: Daniel Lichtblau <danl>*Date*: Fri, 15 Nov 1996 03:34:00 -0500*Organization*: wolfram.com*Sender*: owner-wri-mathgroup at wolfram.com

Christian Brechbuehler wrote: > > Dear readers of comp.soft-sys.math.mathematica, > > I would like to bring to your attention a flaw I suspect in seeding > the integer random number generator of Mathematica. This is for your > information -- I mailed it to support at wolfram.com > $VersionNumber -> 2.2 > $Version -> Solaris 2.2 (April 28, 1993) > > Symptom > ------- > Random[Integer, {...}] ignores some of the bits of the seed that was > previously given to SeedRandom[...]. Example: > > SeedRandom[3] > Table[Random[Integer,{0, 99}], {5}] -> {94, 88, 87, 55, 30} > SeedRandom[131] > Table[Random[Integer,{0, 99}], {5}] -> {94, 88, 87, 55, 30} > > Regularities > ------------ > I found the following patterns in the influence of the sees (or lack > of influence). Maybe a person with access to the source code can > interprete these patterns. > * For seeds below 2^31, the bits 6,7, and 24 are ignored; the > corresponding binary digits have the respective values 2^6(==64), 2^7 > (as in the example above), and 2^24. > * For bigger seeds (i.e., not machine size integers), the bits 6, 7, > and 24 do take effect, but the bits 40, 54, 55, 72, 86, and 87 are > always ignored. On the other hand, adding, e.g., 2^50 always has an > influence on the pseudo- random sequence that will be generated. I > did not check for seeds above 2^100. > > Other Aspects of Random[] etc. > ------------------------------ > The effect does not depend on the range of integers requested in the > call to Random. Real-valued random numbers (e.g. Random[]) are not > affected. > $RandomState, the state of the random number generator, is an > integer and seems evenly distributed with equal probability (1/2) in > either of the intervals [0,2^1854] or [2^1854, 3*2^1854]. > Generating an integer random number changes $RandomState > generating a real does not (!); these seem to be disjoint random > streams. > > Workaround > ---------- > Multiply the seeds by 5 (or 256). > > Hoping this might help some of you, or you might help me > > Christian Brechbuehler > > Communication Technology Laboratory, Image Science Group > Swiss Federal Institute of Technology (ETH), Zurich It would take a bit more time than I have to track down every last detail, but I can respond to some of this. First, at present we use two algorithms for random number generation. One is a callular automaton (CA) method, the other uses "subtract-with-borrow" (SWB). The CA algorithm is used to generate machine-size random integers, and SWB is primarily responsible for big integers, with CA accounting for the highest bits. This is because SWB generates 31 bits at a time, so we use CA for any excess if the log-base-two of the range size is not a multiple of 31. In your examples, we use CA because the ranges are small. For CA, if you seed with a random machine integer, it is indeed true that certain bits e.g. bit 8 (2^7) will have no influence. They affect the value of $RandomState, but only in positions that are ignored. This is because the states are, in effect, arrays of 31 bit quantities, so 32nd bits are ignored. Possibly we should change SeedRandom so that all bits play a role in affecting essential bits of the $RandomState. The missing effect of bit 7 (2^6) may in fact be a bug. I'll look into this. I have not looked closely at what happens when bignum integer seeds are used, but it seems likely that your findings stem from the same source; certain bits affect only inessential bits of the $RandomState re the CA method. The reason Random[] is not affected by this is that it uses SWB exclusively, and the SWB state is influenced by all bits(so far as I could discern without running examples). Generating any random number should change $RandomState. If you can replicate an example where this is not so, please send it to me and perhaps also report it as a bug. Daniel Lichtblau Wolfram Research danl at wolfram.com