[math-fun] linear psu-random generators with linear "feed-in"

28 Sep 2013

      THEOREM:
The linear congruential generator
   x  <--   x*a + R mod 2^w
(where  w>=2  and  a mod 4=1) has period = 2^w  if R is any odd constant.
If however R is actually ANOTHER psu-random generator with odd period
and odd period-sum, then the result is a generator whose period
is the product of R's period with 2^w.

Here R's "period-sum" means the sum of all the R-values in R's period.

EXAMPLE (in C language using 32-bit unsigned integers)
  if(z >= 1588146105U){ z -= 1588146105U; }else{ z -= 1588146108U; }
implements a Weyl generator modulo 2^32-3, using step size
1588146105 which is chosen because 1588146105/(2^32-3) has only 1s and
2s in its
continued fraction expansion.  Its period-sum is odd because  2^32-3 mod 4 = 1.

Hence
  x *= 2891336453U;
  if(z >= 1588146105U){ z -= 1588146105U; }else{ z -= 1588146108U; }
  x += z;
  (output x)

implements a generator with period = (2^32-3) * (2^32)
using the two state-variables w and x.
(Here 2891336453 is spectrally-good multiplier mod 2^32.)

THEOREM:
If
   y <-- T y
where y is an n-bit vector and T is an nXn matrix over GF(2)
is a psu-random generator with period=2^n-1 for nonzero vectors y, then
   y <-- (T y) XOR R
also is a period=2^n-1 generator if R is any constant n-vector.
If however R is itself a psu-random generator whose period is
relatively prime to 2^n-1, then the result is a psu-random generator whose
period is the product of the two original periods.

EXAMPLE (again in C with 32-bit unsigned int words):
  y ^= (y << 5); y ^= (y >> 7); y ^= (y << 22);
is a psu-random generator with period-2^32-1 (state is a nonzero 32-bit word y).
We could feed the output of the preceding example into it to get a generator
with period = (2^32-1) * (2^32-3) * 2^32:
  x *= 2891336453U;
  y ^= (y << 5); y ^= (y >> 7); y ^= (y << 22);
  if(z >= 1588146105U){ z -= 1588146105U; }else{ z -= 1588146108U; }
  x += z;
  y ^= x;
  (output y)
and so on.

It also would be possible, of course, to combine two generators by
just (say) XORing
(or adding mod 2^32) their outputs.  However, it seems intuitively
that "feeding in" generator 1 to generator 2 usually will produce a
result "more random" than just XORing their outputs, whenever
generator 2 "amplifies randomness."  The feed-in option is open to us
essentially whenever generator 2 is a "linear recurrence" in some
ring.

For nonlinear psu-random generators, such as
   v <-- v*(975403184785438903-2*v)+856300274470584321     mod 2^64
(I chose these numbers randomly subject to 975403184785438903 mod 4 = 3
and 856300274470584321=odd, here the state is odd 64-bit unsigned int v
and the period is 2^63)
I have no feedin theorem, but these can still be used as "generator 1."

For example in C now with 64-bit unsigned integers:
   v = v*(975403184785438903-2*v)+856300274470584321
   x ^= x<<7; x ^= x>>9;
   x ^= v;
   (output x)
is a generator with period=(2^64-1)*2^63.
Here x is a linear-GF2 generator with state being nonzero 64-bit words;
it has feed-in from the quadratic v-generator with state being odd 64-bit words.

Richard Brent devised a class of generators he calls "xorgens"
   http://arxiv.org/pdf/1004.3115.pdf
which are linear over GF2 and have period=2^(n*w)-1
which is maximal considering their state is n words, each w bits, not all zero.
He then wanted to combine these with a 1-word Weyl generator with period=2^w.

In doing so, Brent made two small mistakes, in my opinion (better
would be calling them
"missed opportunities" not "mistakes").  First, he could have "fed in" the Weyl
generator into his xorgen instead of just combining their two outputs.  Second,
he used step size in the Weyl generator based on the golden ratio times 2^w
where w is the word size.    Better would have been to employ an odd
step size S chosen
so S/2^w had only 1's and 2's in its continued fraction expansion.
With w=32 the
following 5 S's work:
S=1774682003=69C77F93,
S=1812433253=6C078965,
S=2482534043=93F8769B,
S=2520285293=9638806D,
S=3140748093=BB34033D.
With w=16 this S works: S=46073=B3F9.
I'm not sure whether it will be feasible to find such an S for w=64,
but it is feasible to find examples with max partial quotient <=3 for
every word size w, see
H.Neiderreiter: Dyadic fractions with small partial quotients,
Monatshefte fur Mathematik 101,4 (1986) 309-315.
[If anybody could send me a pdf of this, would appreciate that.]

Although I have no feedin theorem for nonlinear generators,
sometimes nonlinear generators are really linear ones "in disguise" in
which case
feedin theorems can be made.  For example, the lagged Fibonacci generator
   x[n] = x[n-55] * x[n-24]
where the x's are odd numbers and multiplication is mod 2^w, is linear using
discrete log as the disguise.   Hence one could use multiplicative
feedin like this
   x[n] = x[n-55] * x[n-24] * R
where R is any generator that always outputs odd values, and has an odd period
relatively prime to  2^55-1.
The resulting generator will have period of (x mod 4) equal to
(2^55-1)*period(R).

-- 
Warren D. Smith
http://RangeVoting.org  <-- add your endorsement (by clicking
"endorse" as 1st step)

Warren D Smith

Warren D Smith

Warren D Smith

Eugene Salamin

David Makin

Dan Asimov

David Makin

meekerdb

Eugene Salamin

David Makin

Hilarie Orman

James Propp

tags

participants (7)