From: Phil Carmody <thefatphil@yahoo.co.uk>
uint64 Rand64(){ ? uint i; ? uint64 v; ? v = statevec[0]; ? for(i=NumWordsInState-1; i>0; i--){ //can be unrolled and all loop iterations run parallel ? ? v ^= statevec[i]; ? ? statevec[i] += UpdatorF(statevec[i-1]); ? } ? statevec[0] += RandStrideConst; ? return(v); //returns the XOR of all words in state vector }
I like the idea, but that XOR worries me. You've not demonstrated independence of the bits being XORed together and therefore the XOR may cancel out randomness. Phil
--no, that is ok. The fact that the proposed generator has maximum period 2^B where B is the number of bits in the state, means every bit pattern is equally likely and all state-patterns occur exactly once. If we now XOR various state words together, we therefore get something exactly uniformly distributed. Plus the fact that this has apparently passed the BigCrush tests (it slightly failed one of the 160 tests but that was presumably just because that was supposed to happen if you run that many tests) confirms. Furthermore, ANY combining function FF can be used instead of XOR(a,b) if it has the property that FF(a,b) is exactly uniformly distributed if at least one of its arguments is. For example in C using uints, FF(a,b) = (a|1)*b FF(a,b) = a XOR b FF(a,b) = a-b FF(a,b) = CyclicShift(a,b) all would work. Actually just FF(a,b)=b works too, but that did not seem good enough intuitively; if I just returned the top word in the state I suspect I might fail tests of independence of successive differences, because those are really just the outputs of my same sort of generator with one less stage. The main problem with my RandGen idea is it is not very fast on my machine. To solve that, I came up with the idea of outputting more than one machine word per "count" if the outputs are generated in "sufficiently independent" ways from the state bits. I suggest the following: let the words of the state be (in order from least to most sig) A B C D E... P Q R S ... W X Y Z and output E.S.Z, D.R.Y, C.Q.X, B.P.W where "." is some combining operator, such as XOR, and we make about n outputs for a (3n+1)-word state. That way each output word arises from XORing 3 state words together and has at least as much randomness as a (2n+1)-stage generator of the original type. Anyway, here is the current code which outputs only 1 word per "count" so it is not as fast as it could be. Perhaps you will refine the code further, it clearly can be done. #define uint32 uint32_t #define uint64 uint64_t #define uint128 __uint128_t #define RandStrideConst 14923729446516375051ull //must be odd //The below is written for a 64-bit machine. //The 32-bit version with NumWordsInState=4 passes BigCrush U01 tests. //I do not know whether decreasing to 3 words will still pass BigCrush. //If you have 32-bit machine then text-replace 64-->32 and then 128-->64 throughout //the following: //period will be 2^(64 * NumWordsInState), increase for more randomness but slower runtime: #define NumWordsInState 4 inline uint64 UpdatorF(uint64 x){ uint128 y; y = x; if( x <= (1<<(64-7)) ){ x ^= RandStrideConst; } //if(x<=Z), important that Z be even //the above line was done wrong in my original post so I had failed to get odd-parity F. y *= y; x += y ^ (y>>64); return(x); } uint64 statevec[NumWordsInState]; uint64 Rand64slow(){ uint i; uint64 v; v = statevec[0]; for(i=NumWordsInState-1; i>0; i--){ //can be unrolled and all loop iterations run parallel v ^= statevec[i]; statevec[i] += UpdatorF(statevec[i-1]); } statevec[0] += RandStrideConst; return(v); //currently returns the XOR of all words in state vector }