New simple full-period psu-random generator ====Warren D. Smith Feb 2012========= In the below let "a+b" mean (a+b) mod 2^w where w is the machine's word size. Let F(x) be any function at all that maps one machine word x to another. The "parity of F" is the sum over all 2^w words x, of F(x) computed mod 2. So for example, the parity of F(x) = C + D*x + E(x*x) where C, D are any integer constants and E() is any function from integers to machine words, is equal to E(0) + E(2^(w-1)) mod 2. (This also works if any of the + are replaced by XOR.) Proof: use symmetry E(x*x)=E((-x)*(-x)) to pair x with -x for x not equal to 0 or 2^(w-1), which are the two numbers whose negation is the same as they are. Similarly mentally pair x and x+1 to handle the linear term. QED. If F() has even parity you can convert it to a new function F'() having odd parity as follows: F'(x) = F(x) + (C if x is zero, else D) where C and D are any integer constants with opposite parities. Also any of the "+" here could be replaced by XOR, that also works. THEOREM: Let x[0], x[1], ..., x[N-1] be a set of N machine words. Let C be any odd constant and F be any odd-parity function. Then the following code: x[0] += C; for(i=1 to N){ x[i] += F(x[i-1]); } will update the x-vector in a manner which has the maximum possible period=2^(n*w). So the random generator that I suggest is simply to do that update then output x[N-1]. However, that can be criticized thus: "the above update procedure is sequential not parallel." You can defeat that criticism as follows: Instead run the updating "in reverse": for(i=N down to 1){ x[i] += F(x[i-1]); } x[0] += C; which you can easily see makes no real difference (period still maximal... different guys are still doing their same thing, just shifted in time) but now all loop iterations and the final line all can be done in parallel. As a concrete example, this F(x) works: 1. Compute y=x*x as a double-length word. 2. F(x) = (lo(y) XOR hi(y)) + (x >> (w-1)) where "a>>h" is the C-language "right shift by h hops" operator. (The + optionally could be replaced by XOR.) ADVANTAGES: Very simple and foolproof. Does not care what wordsize your machine has in the sense you do not need, if the machine wordsize changes, to redesign a new set of mysterious careful constants or change the code. Does not care what n is, for any n at all will still have max period=2^(w*n) so you can increase n to get greater randomness but lower speed. Trivially easy to parallelize. For the particular F(x) suggested above, every bit of x potentially affects every bit of F(x), and the operation-types are well mixed preventing any particular part of the processor from experiencing "traffic jams."