James said:
I based my statement on the article "Random Number Generators:
Good Ones Are Hard to Find", by Park and Miller (CACM, Oct.
1988).
That paper mostly concerns itself with choosing the right modulus and
multiplier. It does, however, in passing, also address the question how to
turn the result into a random bit: on page 1200 left-column it points out
that the k-th bit it Grogono's RNG cycles with period 2^k. And they quote
Knuth to point out that this is typical for mixed linear congruence RNGs
with modulus 2^n. We shall see below what the reason is.
Could you point me to some further analysis to support what you are
saying?
What I was thinking of is mostly the Table 1 in Section 3.3.4 of Knuth TAOCP
(I have the third edition, published several years after Park and Miller).
It lists the results of the spectral test for various linear congruence
RNGs and shows that there are some pretty decent ones even with modulus
2^n. Knuth also points out a reason as to why the spectral test is
relevant: "all generators known to be bad actually fail it" [beginning of
3.3.4].
Note that Park and Miller also acknowledge that with a carefully chosen
multiplier linear congruence RNGs with modulus 2^n can have period 2^n/4
and mixed linear congruence RNGs can have full period 2^n: in fact they do
if the multiplier is congruent 1 mod 4 and the shift constant is odd
[Knuth, 3.2.1.2 Theorem A].
Now for the claim that any (mixed) linear congruence RNG with modulus 2^n
will have weak low order bits: consider a mixed linear congruence RNG
x = ( a * x + c ) % 2^n
that has full period (i.e., a is cong 1 mod 4 and c is odd). Then the lowest
k bits obey the recursion
y = ( a * y + c ) % 2^k.
which also has full period 2^k (since a and c did not change!). In
particular, the lowest-order bit always alternates.
On the other hand, the highest-order bit alone has full period 2^n. For
contradiction, assume it had period 2^m with m < n (note that the period
must be a divisor of 2^n and hence a power of 2). Then, since the first n-1
bits have period 2^(n-1), the overall period would be LCM(2^m, 2^(n-1))
which is 2^(n-1) contradicting the assumption that the RNG has full period
2^n.
As for the quality of high-order bits, one also should consider what results
of the spectral tests (and many others) mean. The spectral test by and in
itself applies to a sequence of real numbers in [0,1) that are presented as
a sequence of independent uniformly distributed values. The results from
the RNG are translated into real numbers by dividing each by the modulus
(2^n). Note that the highest-order bit tells you which half of the
unit-interval contains the number. Thus, if tests say that the sequence is
good, they also say (at least morally) that the high-order bits are good
whereas the lowest order bits are insignificant since they only amount to
small perturbations of the real number.
My remark that the low-order bits should be considered part of the internal
state derives largely from this. E.g., in Table 1 [mentioned above], line
26 there is a good multiplier for the modulus 2^64. I would not hesitate to
use that with an unsigned long long as the internal state. However, I would
have the generator return only and unsigned long exposing just the highest
32 bits of the state to the client. Then, even the lowest bit of the
observable sequence will have period 2^33 and the resulting RNG can be
expected to pass all tests with flying colors (at least it will pass the
spectral test).
Best
Kai-Uwe Bux
