Sci.QRNG: Quasi RNG

This module implements quasi random number generators (qrngs), also known as low discrepancy sequence generators. Differently from prngs, which aim to mimic a source of true randomness, qrngs aim to progressively fill a multi-dimensional hypercube \( (0, 1)^d \) in a homogeneous way:

Name States Maximum Dimensionality
sobol 2^32-1 21201

States indicates how many states the qrng can generate. Each state corresponds to a different point in the the d-dimensional hypercube. Samples correspond to the coordinates of this point, so there are d samples for each state. It is an error to generate more states than allowed for any qrng.

The dimensionality of each qrng is set automatically without the need of user intervention based on the number of times the rng:sample() function is called between rng:nextstate() invocations. The rng:sample() function must be called always the same number of times between rng:nextstate() invocations. It is an error to use a dimensionality higher than the maximum dimensionality allowed for any qrng.

The following example illustrates the use of the Sobol qrng for the generation of samples over a three-dimensional hypercube:


local qrng = require "sci.qrng"

local r = qrng:sobol()

for i=1,10 do
  r:nextstate()
  print(r:sample(), r:sample(), r:sample())
end
--> 0.5     0.5     0.5
--> 0.75    0.25    0.25
--> 0.25    0.75    0.75
--> 0.375   0.375   0.625
--> 0.875   0.875   0.125
--> 0.625   0.125   0.875
--> 0.125   0.625   0.375
--> 0.1875  0.3125  0.9375
--> 0.6875  0.8125  0.4375
--> 0.9375  0.0625  0.6875

r:nextstate()
print(r:sample(), r:sample(), r:sample(), r:sample()) --> error

API

In the following rng represents a generic qrng.

rng:nextstate()

Initializes rng to the next (or initial) state. It must be called before calling rng:sample(), and not the other way around.

u = rng:sample()

The i-th call of this function after rng:nextstate() has been called returns the sample corresponding to the i-th dimension for the current state of rng up to its maximum dimension. The sample is guaranteed to belong to the interval (0,1) extremes excluded. This function must be called always the same number of times between rng:nextstate() invocations.

rng = prng.sobol()

Returns a qrng based on the Sobol algorithm. The primitive polynomials, the initial direction numbers and the implementation for generating Sobol sequences are based on the S. Joe and F. Y. Kuo project to which we refer for further information on this qrng. More specifically the set of direction numbers based on search criterion \( D^{(6)} \) is used which allows for the generation of samples up to dimension 21201. It should be noted that this LuaJIT port is not endorsed in any way by these authors nor did they participate in its development. Also notice that in our implementation we discard the initial state which corresponds to samples with value 0.