User:ItsMutual/sandbox

Weyl Sequence

This refers to the sequence from the equidistribution theorem (proven by Hermann Weyl):

The sequence of all multiples of an irrational α,

0, α, 2α, 3α, 4α, ...

is equidistributed modulo 1.

In other words, the sequence of the fractional parts of each term will be uniformly distributed in the interval [0, 1).

In computing, an integer version of this sequence is often used. An irrational number cannot be represented on a digital computer and an integer is used in its place. The theorem might be worded as follows:

The sequence of all multiples of an odd integer k,

0, k, 2k, 3k, 4k, …

is equidistributed modulo 2$^{n}$.

That is, the sequence of the remainders of each term when divided by 2$^{n}$ will be uniformly distributed in the interval [0, 2$^{n}$).

An example of such a sequence is shown in Marsaglia’s paper "Xorshift RNGS". The following C code generates what Marsaglia calls a "Weyl Sequence":

d += 362437;

In this case, the odd integer is 362437 and results are equidistributed modulo 2$^{32}$.

It is likely that Marsaglia’s paper is the origin of “Weyl Sequence” in the context of computing.

Middle Square Weyl Sequence RNG

The defects associated with the original middle-square generator can be rectified by running the middle square with a Weyl sequence. The Weyl sequence prevents convergence to zero. The Weyl sequence also prevents the repeating cycle problem described above. A C implementation is shown below.

#include <stdint.h>

uint64_t x = 0, w = 0, s = 0xb5ad4eceda1ce2a9;

inline static uint32_t msws() {

   x *= x; 
   x += (w += s); 
   return x = (x>>32) | (x<<32);

}

The Weyl sequence (w += s) is added to the square of x. The middle is extracted by shifting right 32 bits. This generator passes all the tests in the stringent Bigcrush battery in TestU01. A free software package is available here

A simple pen-and-paper method for generating random numbers is the so-called middle square method suggested by John von Neumann. While simple to implement, its output is of poor quality. It has a very short period and severe weaknesses, such as the output sequence almost always converging to zero. A recent innovation is to combine the middle square with a Weyl sequence. This method produces high quality output through a long period. See Middle Square Weyl Sequence PRNG.

The errors revealed by PractRand in the lower two bits also show in the TestU01 BigCrush by simply rotating the output of xoroshiro two bits left. For example, if one runs the following program with BigCrush, errors in the MatrixRank and LinearComplexity tests appear:

#include <stdint.h>
uint32_t xoroshiro_r2() {
   uint64_t t;
   t = next();             /* get 64-bit xoroshiro output */
   t = (t<<2) | (t>>62);   /* rotate 2 bits left */
   return t;               /* return lower 32 bits */
}

========= Summary results of BigCrush =========

 Version:          TestU01 1.2.3
 Generator:        xoroshiro_r2 seed = { 0x123456789abcdef, 0xfedcba987654321 }
 Number of statistics:  160
 Total CPU time:   02:59:17.35
 The following tests gave p-values outside [0.001, 0.9990]:
 (eps  means a value < 1.0e-300):
 (eps1 means a value < 1.0e-15):

       Test                          p-value
 ----------------------------------------------
 69  MatrixRank, L=1000, r=26         eps
 70  MatrixRank, L=5000               eps
 71  MatrixRank, L=5000               eps
 81  LinearComp, r = 29             1 - eps1
 ----------------------------------------------
 All other tests were passed

The MatrixRank and LinearComplexity tests in BigCrush only test the left 30 bits of the input and not the lower two bits. For this reason, the standard xoroshiro passes BigCrush. Rotating left two bits puts the lower bits in a position that will be actually tested by BigCrush.

The weakness in the 2nd lowest bit of xoroshiro is confirmed with BigCrush by rotating the output one bit left:

#include <stdint.h>
uint32_t xoroshiro_r1() {
   uint64_t t;
   t = next();             /* get 64-bit xoroshiro output */
   t = (t<<1) | (t>>63);   /* rotate 1 bit left */
   return t;               /* return lower 32 bits */
}

========= Summary results of BigCrush =========

 Version:          TestU01 1.2.3
 Generator:        xoroshiro_r1 seed = { 0x123456789abcdef, 0xfedcba987654321 }
 Number of statistics:  160
 Total CPU time:   03:03:40.84
 The following tests gave p-values outside [0.001, 0.9990]:
 (eps  means a value < 1.0e-300):
 (eps1 means a value < 1.0e-15):

       Test                          p-value
 ----------------------------------------------
 81  LinearComp, r = 29             1 - eps1
 ----------------------------------------------
 All other tests were passed