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