PRNS with 32 bits of state

September 27th, 2017

A quick description of a 32-bit state Weyl sequence¹ (logically additive recurrence) followed by a bit-finializing operation which can be used for generating permutations of $\left[0,~2^{32}\right)$ or for random number generation which supports random access queries. The goal is to find a sweet-spot of time complexity, statistical quality and number of unique statistically independent permutations generated.

Bullet-points:

Random access is the key point. If that’s not needed then there are a number of other options.
Structurally equivalent to the 64-bit version described HERE.
Passes² Smallcrush³.
Single and/or multiple stream (aka different permutations)
Example implementation as a public domain single header file library (lprns.h).
Approximately the same complexity as the roughly equivalent PCG⁴ generator: godbolt. We’re trading statistical quality for random access operations.

Briefly the state is updated by a Weyl sequence which allows very fast queries. To provide reasonable statistical quality this is then passed through a bit finalizing function. Example from the library:

// non-stream variant has no second parameter and multiplier is a constant
static inline uint32_t lprns_stream_mix(uint32_t x, uint32_t m)
{
  x ^= x >> LPRNS_S0; x *= m;
  x ^= x >> LPRNS_S1; x *= LPRNS_M1; 
  x ^= x >> LPRNS_S2;
  return x;
}

Non-paramaterized version loses the second input parameter and m becomes a constant. This is common-ish finalizer used (for example) in murmurhash 3, xxhash, etc. In an ideal world I’d have run a search/optimization to provide the constants. Constants from murmur/xxhash are designed for high-entropy input with a goodness measure of bit avalanche. Here we have a low entropy input (a low-discrepancy sequence) which we want to transform into a reasonable pseudo-random sequence. Since it’s doing good enough at testing…I couldn’t be bothered.

The example code above requires each stream to have a pretty good constant m otherwise statistical quality will be decreased⁵. The library provides an inital value and function to create the next from it, etc. The function simply drops the bottom 3 bits (fixed at 101), computes the next larger integer with the same population count and sets the bottom 3 bits to 101. Minimal testing indicates that this scheme works well but that doesn’t mean much. Frankly I don’t consider it very interesting. Getting the m values is a pain, its probably one more extra thing to store and it limits the number of unique permutations. Tossing it out since these downsides might not be an issue for some cases.

Recently I discovered that my 64-bit variant is virtually identical to a generator in the Java system library informally called splitmix⁶. This generator supports multiple streams by parameterizing the Weyl constant. Although somewhat easier than the version above all of the same problems apply here as well. Instead let’s toss together one that allows any unique integer to define a stream:

// alternate streaming variant
static inline uint32_t lprns_stream_mix(uint32_t x, uint32_t m)
{
  x ^= m;                              // any integer 'm' gives a unique stream
  x ^= x >> LPRNS_S0; x *= LPRNS_M0;
  x ^= x >> LPRNS_S1; x *= LPRNS_M1; 
  x ^= x >> LPRNS_S2;
  return x;
}

The previous is less than ideal in my eyes since we have two $\mathbb{F}_2$ operations in a row (xor with m followed by an xorshift) but I’m attempting to not extended the operation chain any longer than needed. If lower quality is fine we can drop one xorshift-multiply (and say just grab murmurhash 2 constants) or even lower by dropping all after then xor by m and returning a product with a good (M)LCG constant. The last becomes equivalent to a minimal 2D white noise generator I previously posted⁷ about.

Footnotes

“Weyl sequence overview” (local post) ↩
Statistics police might call me on declaring a pass:
- TestU01 requires p-values within a 99.9% confidence level to declare a test passes. Otherwise it reports the questionable p-value or a complete fail.
- Test driver can be found here and runs of 100 batteries for fixed and streaming version here and here respectively. Streaming test changes the permutation using the library provided function each battery run. If you inspect these runs you’ll find one questionable p-value in each just outside of the confidence range. On about 20k runs hitting a questionable p-value about 2.2% of the time and no fails. The questionable p-values are scattered across eight of the fifteen tests in the battery.
- Ideally I’d re-run test with questionable p-values with increased sample sizes and rince-and-repeat until it moves into pass or fail. Oh wait! I did do that. SmallCrushAdaptive (source)
↩
Smallcrush is a TestU01⁸ battery, roughly speaking passing this means you’re good for ~$2 \times 10^5$ samples per problem. ↩
“PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation”, Melissa E. O’Neill (web site) ↩
Questionable p-values rate increases from ~2.2% to ~3.7% with a set of constants I expect to be pretty good. ↩
java.util.SplittableRandom originally described in “Fast splittable pseudorandom number generators.”, Guy Steele Jr., Doug Lea, and Christine Flood, 2014 ↩
The original version in “minimal quality 2D hashing with Weyl” (local post) ↩
“TestU01: A C library for empirical testing of random number generators”, Pierre L’Ecuyer and Richard Simard, 2007. (original source/paper) (hacked source) ↩

Comments

SHF (3)