*state size*and

*output size*. E.g. Mersenne twister has a very long period, but with 624-bit state. You can get repeats on the 32-bit outputs -- as Jeff found. It might be nice to get all 2^32 32-bit integers, permuted, without repeats.

Jeff's approach is to use properties of the finite field

*F_p,*for large

*p*near 2^32 -- in particular, 4296967291 is just 5 shy of 2^32 and he worked around that neatly. But there are also finite fields of order

*p*^

*n*for all

*p*and

*n --*in particular,

*p*=2 and

*n*=32.

The neat thing is that all

*p*^

*n*-1 non-zero elements of a finite field always form a cyclic group -- there is one non-zero number

*g*(many, really) such that all others are powers of it. For example, mod

*p*=11,

*g*=2 is a generator: its successive powers are 2, 4, 8, 16=5, 32=10, 64=9, 128=7, 256=3, 512=6, 1024=1. You can convince yourself that other generators mod 11 are 6, 7, and 8.

For

*n*>1 the arithemetic is a little (although not too much) more involved. You just have to find an irreducible polynomial

*r*of degree

*n*with coefficients mod

*p -- t*his plays the role of the prime -- as well as a generator

*g*. The details are here (including Berlekamp's algorithm) but for example one can use

*r*= 0x17bc0cb37 -- a 33-bit number so all the residues have 32 bits -- and

*g*= 0xb139e84d. (I got these particular values using RUFFL, generating random 32-degree polynomials until I found one which is irreducible, and likewise found a

*g*with full period 2^32-1.) Note that if you need period 2^32 rather than 2^32-1 you can special-case that: e.g. if the PNRG gives

*a*maps to

*f*(

*a*) then just use an if-statement to splice in

*a*maps to 0 maps to

*f*(

*a*); maybe pick

*a*= 0xdeadbeef, or anything else.

Jeff used TestU01 to run some statistical tests on his cyclic generator. This is a C library so I used iff2 to try it out.

The generator is simply

int degr = 32;

unsigned r = 0x7bc0cb37;

unsigned g = 0xb139e84d; // 2 ** 65539

unsigned state = 2;

unsigned f232() {

state = iff2mul(state, g, r, degr);

return state;

}

and you can seed it by setting state to anything non-zero.

Using this I found:

* (+) The mathematical theory gives you full period very cleanly.

* (+) You can seed by simply setting the state variable.

* (+) State is only 32 bits (96 if you count

*r*and

*g*).

* (-) To generate a different permutation entirely, you need not just any 32-bit number

*g*but rather one which is a generator. This makes the parameterization a bit less user-friendly.

* (-) I didn't get as good results with TestU01's SmallCrush suite as Jeff got with his permuteQPR -- tests 1 and 8 have p-value of eps. More experimenting with

*r*'s and

*g*'s might give better results.

## No comments:

## Post a Comment