8

I've used MT19937 in a test harness to generate uniformly (unsigned) 32-bit [0, $2^{32}$- 1] values, based on the original Authors' mt19937.c implementation, to generate an (essentially inexhaustible) supply of statistically random stream of bit-octets. This is in lieu of a CSPRNG, which isn't necessary for these particular tests. However, I've recently been considering the WELL PRNGs - not because of the statistical properties as such (both seem more than adequate for my needs) - but they seem to suggest more a efficient implementation.

I lack the mathematical background for the academic papers, though I could at least follow the 'twist' matrix and tempering transform for the former. However, much of the code provided by the Authors of the WELL-n functions seem to focus of floating-point generation, with some magic floating point constants (e.g., 2.32830643653869628906e-10). Can steps be omitted from the WELL code to provide a uniform 32-bit distribution? Or is the algorithm designed / biased specifically for floating-point distributions?

Or I'm an incorrect in thinking that WELL will yield a performance gain for 'bulk' uint32 vector generation, while satisfying my requirements?

Brett Hale
  • 183
  • 4
  • 1
    If this is just curiosity, that's fine, but real performance always depends on what else is going on. If generating random numbers is consuming 10% of total time, and you can reduce it by half, that gives you a speedup of 5%, which might not be worth the trouble. – Mike Dunlavey Feb 09 '14 at 17:19
  • Perhaps off topic, but it's also worth considering counter mode generators such as https://www.deshawresearch.com/resources_random123.html, which require far, far less memory and parallelize trivially. – Geoffrey Irving Feb 09 '14 at 18:18
  • 1
    As an update, I'm now leaning toward the PCG RNGs. They are much faster, can supply very long periods (as well as multiple streams) with statistically excellent properties, and appear to recover very quickly from poor IVs. – Brett Hale Jul 14 '17 at 07:56

1 Answers1

4

I'd imagine that most users of random number generators are ultimately interested in floating-point values. This is why the Double precision SIMD-oriented Fast Mersenne Twister (dSFMT) exists. However, there is newer C code for the WELL RNG that returns unsigned long values. Looking at the code, it appears that the earlier version was casting unsigned long to double so you may be able to figure out what they were doing by comparing the two.

If you mainly care about speed, I don't think that this is the PRNG for you. The speed/performance that the authors refer to is not how fast the algorithm generates random variates, but rather how quickly it recovers from a poor initialization. This improves the statistical properties of the WELL generator. See section 6 of Mutsuo Saito's Master's thesis (PDF) for details on what this means. Such tests are performed with artificial worst-case initial states so it's unclear to me what the effect is in general use.

Random number generation can be quite expensive—often despite one's intuition—and is a very good candidate for optimization provided that your code is spending a reasonable amount of time producing random values. In my own simple performance tests (Retina MacBook Pro, OS X 10.9) I found the WELL RNG to be about one third as fast as the current integer-based SIMD-oriented Fast Mersenne Twister (SFMT) when producing uint32 values. SFMT also has support for uint64. I also found the classic mt19937ar.c code to be about half as fast as SFMT.

horchler
  • 763
  • 1
  • 5
  • 17