Bug 1239479: Add comments to mfbt/XorShift128PlusRNG.h from the RNG's designer. DONTBUILD r=Waldo
authorJim Blandy <jimb@mozilla.com>
Wed, 13 Jan 2016 12:46:40 -0800
changeset 315029 9092fd77df19045999fb34c6db1744475c283e82
parent 315028 24e0645f9c31e717586e287adb863e5c3f68c2f3
child 315030 f001a01c85d7979a9b9e44ee198587a772b06f46
push id5703
push userraliiev@mozilla.com
push dateMon, 07 Mar 2016 14:18:41 +0000
treeherdermozilla-beta@31e373ad5b5f [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersWaldo
bugs1239479
milestone46.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1239479: Add comments to mfbt/XorShift128PlusRNG.h from the RNG's designer. DONTBUILD r=Waldo
mfbt/XorShift128PlusRNG.h
--- a/mfbt/XorShift128PlusRNG.h
+++ b/mfbt/XorShift128PlusRNG.h
@@ -28,52 +28,64 @@ namespace non_crypto {
  * That paper says:
  *
  *     In particular, we propose a tightly coded xorshift128+ generator that
  *     does not fail systematically any test from the BigCrush suite of TestU01
  *     (even reversed) and generates 64 pseudorandom bits in 1.10 ns on an
  *     Intel(R) Core(TM) i7-4770 CPU @3.40GHz (Haswell). It is the fastest
  *     generator we are aware of with such empirical statistical properties.
  *
+ * The stream of numbers produced by this method repeats every 2**128 - 1 calls
+ * (i.e. never, for all practical purposes). Zero appears 2**64 - 1 times in
+ * this period; all other numbers appear 2**64 times. Additionally, each *bit*
+ * in the produced numbers repeats every 2**128 - 1 calls.
+ *
  * This generator is not suitable as a cryptographically secure random number
  * generator.
  */
 class XorShift128PlusRNG {
   uint64_t mState[2];
 
  public:
   /*
    * Construct a xorshift128+ pseudo-random number stream using |aInitial0| and
-   * |aInitial1| as the initial state. These may not both be zero; ideally, they
-   * should have an almost even mix of zero and one bits.
+   * |aInitial1| as the initial state.  These MUST NOT both be zero.
+   *
+   * If the initial states contain many zeros, for a few iterations you'll see
+   * many zeroes in the generated numbers.  It's suggested to seed a SplitMix64
+   * generator <http://xorshift.di.unimi.it/splitmix64.c> and use its first two
+   * outputs to seed xorshift128+.
    */
   XorShift128PlusRNG(uint64_t aInitial0, uint64_t aInitial1) {
     setState(aInitial0, aInitial1);
   }
 
-  /* Return a pseudo-random 64-bit number. */
+  /**
+   * Return a pseudo-random 64-bit number.
+   */
   uint64_t next() {
     /*
      * The offsetOfState*() methods below are provided so that exceedingly-rare
      * callers that want to observe or poke at RNG state in C++ type-system-
      * ignoring means can do so. Don't change the next() or nextDouble()
      * algorithms without altering code that uses offsetOfState*()!
      */
     uint64_t s1 = mState[0];
     const uint64_t s0 = mState[1];
     mState[0] = s0;
     s1 ^= s1 << 23;
     mState[1] = s1 ^ s0 ^ (s1 >> 17) ^ (s0 >> 26);
     return mState[1] + s0;
   }
 
   /*
-   * Return a pseudo-random floating-point value in the range [0, 1).
-   * More precisely, choose an integer in the range [0, 2**53) and
-   * divide it by 2**53.
+   * Return a pseudo-random floating-point value in the range [0, 1). More
+   * precisely, choose an integer in the range [0, 2**53) and divide it by
+   * 2**53. Given the 2**128 - 1 period noted above, the produced doubles are
+   * all but uniformly distributed in this range.
    */
   double nextDouble() {
     /*
      * Because the IEEE 64-bit floating point format stores the leading '1' bit
      * of the mantissa implicitly, it effectively represents a mantissa in the
      * range [0, 2**53) in only 52 bits. FloatingPoint<double>::kExponentShift
      * is the width of the bitfield in the in-memory format, so we must add one
      * to get the mantissa's range.