Richard Brent extended some efficient XOR-based PRNGs designed by George Marsaglia into a family of "xorgen" generators which are efficent, non-sparse, maximal-period polynomials of length 64, 128, 256,... 4096 bits.
(It ends there because proving period 2^n-1 requires knowing the factorization of 2^n-1, and 2^8192-1 = (2^4096+1)*(2^2048+1)*...*(2^1+1). The factorization of 2^4096+1 = F_12 is currently stuck on an 1133-digit composite residue; see http://caramel.loria.fr/f12.txt) http://maths-people.anu.edu.au/~brent/pub/pub224.html "Some long-period random number generators using shifts and xors", Related background papers: http://www.jstatsoft.org/v08/i14/paper "Xorshift RNGs" http://maths-people.anu.edu.au/~brent/pub/pub218.html "Note on Marsaglia's xorshift RNGs" Anyway, the algorithm boils down to t1 = x[i-r]; t2 = x[i-s]; t1 ^= t1 << a; t2 ^= t2 << c; t1 ^= t1 >> b; t2 ^= t2 >> d; x[i] = t1 ^ t2; For various constants r = 2..128, s < r, and shifts a, b, c and d. Both 32- and 64-bit versions are included. This is both more efficient and (especually using 64-bit words) more thorough than the current code, for sizes up to 4096 bits. Although the current code has tables for larger pools, everything larger than 32x128 = 4096 bits is currenty commented out and not used. Would you be interested in a patch to revise _mix_pool_bytes()? I'm also thinking of revising the input rotate-by-7 to use Marsaglia's original xorshift as a whitener. -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
