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)