It seems natural to exploit the fact that computers work in binary
arithmetic and to design RNGs defined directly in terms of bit strings
and sequences. We do this under the following framework, taken from
[54]. Let
denote the finite field with two
elements, 0 and
, in which the operations are equivalent to
addition and multiplication modulo
.
Consider the RNG defined by a matrix linear recurrence over
,
as follows:
It is well-known ([80,36]) that when the
's
obey (2.12), for each
, the sequence
follows the linear recurrence
![]() ![]() |
To jump ahead directly from
to
with this
type of generator, it suffices to precompute the matrix
(in
) and then multiply
by this matrix.
Several popular classes of RNGs fit this framework as special cases,
by appropriate choices of the matrices
and
. This includes
the Tausworthe or LFSR, polynomial LCG, GFSR, twisted GFSR, Mersenne
twister, multiple recursive matrix generators, and combinations of
these ([54,78,81,88]). We detail some of them
after discussing measures of their uniformity.
The uniformity of point sets produced by RNGs based on linear
recurrences over
is usually assessed by measures of
equidistribution defined as follows
([38,54,45,88]).
For an arbitrary vector
of non-negative
integers, partition the unit hypercube
into
intervals of the same length along axis
, for each
. This
determines a partition of
into
rectangular boxes of the same size and shape. We call this partition
the
-equidissection of the unit hypercube.
For some index set
, if
has
points, we say that
is
-equidistributed in
base
if
there are exactly
points in each box of the
-equidissection, where
. This means
that among the
points
of
, if
we consider the first
bits of
, the first
bits of
, and the first
bits of
, each of the
possibilities occurs exactly the same number of times. This
is possible only if
.
The
-equidistribution of
depends only on the first
bits of
for
, for the points
that belong to
. The vector of
these
bits can always be expressed as
a linear function of the
bits of the initial state
, i.e.,
as
for some
binary matrix
, and it is easily seen that
is
-equidistributed if and only if
has full rank
.
This provides an easy way of checking equidistribution
([22,38,88]).
If is
-equidistributed for some
, it is called
-distributed with
bits of
accuracy, or
-equidistributed ([38]).
The largest value of
for which this holds is called the
resolution of the set
and is denoted by
.
This value has the upper bound
. The resolution gap of
is defined
as
. In the same vein as for MRGs,
a worst-case figure of merit can be defined here by
![]() |
The point set is a
-net in base
(often
called a
-net in the context of quasi-Monte Carlo
methods, where a different notation is used ([80])), if it is
-equidistributed in base
for all non-negative
integers
summing to
. We call the smallest such
the
-value of
. The smaller it is, the
better. One candidate for a figure of merit could be the
-value of
for some large
. A major drawback of this measure is that
it is extremely difficult to compute for good long-period generators
(for which
is large), because there are too many vectors
for which equidistribution needs to be checked. In practice, one must
settle for figures of merit that involve a smaller number of
equidissections.
When
for all sets
of the form
, for
, the RNG is said to be
maximally equidistributed or asymptotically random
for the word size
([38,88,91]).
This property ensures perfect equidistribution of all sets
,
for any partition of the unit hypercube into subcubes of equal sizes,
as long as
and the number of subcubes does not exceed the
number of points in
. Large-period maximally equidistributed
generators, together with their implementations, can be found in
[43,54], and [84], for example.
The RNGs defined via (2.12)-(2.14) do not have
a lattice structure in the real space like MRGs, but they do have
a lattice structure in a space of formal series, as explained in
[12,45,65], and [88]. The real space
is replaced by the space
of formal power series with
coefficients in
, of the form
for some integer
. In that setting, the lattices
have the form
![]() |
![]() |
The Tausworthe or linear feedback shift register
(LFSR) generator ([87,38,88]) is a special case of
(2.12)-(2.14) with
(in
) for some
positive integer
, where
![]() |
(2.17) |
![]() |
(2.18) |
LFSR generators can be expressed as LCGs in a space of polynomials ([89,88,36]). With this representation, their lattice structure as discussed in Sect. 2.4.3 follows immediately.
Here we take
as the
matrix
![]() |
More generally, we can define
as the bitwise exclusive-or
of
where
, so
that each bit of
follows a recurrence in
whose
characteristic polynomial
has
nonzero terms. However,
the period length is still bounded by
, whereas considering the
-bit state, we should rather expect a period length close to
.
This was the main motivation for the twisted GFSR (TGFSR)
generator. In the original version introduced by [75],
and the matrix
is defined as the transpose of
in (2.16), with
replaced by
. The characteristic
polynomial of
is then
, where
is the characteristic polynomial of
,
and its degree is
. If the parameters are selected so that
is primitive over
, then the TGFSR has period
length
. [76] pointed out important weaknesses of
the original TGFSR and proposed an improved version that uses
a well-chosen matrix
whose lines differ from those of the
identity. The operations implemented by this matrix are called
tempering and their purpose is to improve the uniformity of
the points produced by the RNG.
The Mersenne twister ([78,83]) is a variant of
the TGFSR where
is slightly less than
and can be a prime
number. A specific instance proposed by [78] is fast,
robust, has the huge period length of
, and has become
quite popular.
In the multiple recursive matrix method of [81],
the first row of matrices in
contains arbitrary
matrices. However, a fast implementation is possible only when these
matrices are sparse and have a special structure.
Many of the best generators based on linear recurrences over
are constructed by combining the outputs of two or more RNGs having
a simple structure. The idea is the same as for MRGs: select simple
components that can run fast but such that their combination has
a more complicated structure and highly-uniform sets
for the
sets
considered important.
Consider distinct recurrences of the form
(2.12)-(2.13), where the
th recurrence has parameters
and state
at
step
, for
. The output of the combined generator at
step
is defined by
With this method, by selecting the parameters carefully,
the combination of LFSR generators with characteristic polynomials
gives yet another LFSR with characteristic
polynomial
and period length equal
to the product of the period lengths of the components
([89,97,38,88]). Tables and fast
implementations of maximally equidistributed combined
LFSR generators are given in [38].
The TGFSR and Mersenne twister generators proposed in
[76,78] and [83] cannot be maximally
equidistributed. However, concrete examples of maximally
equidistributed combined TGFSR generators with period lengths near
and
are given in [54]. These
generators have the additional property that the resolution gaps
are zero for a class of small sets
with indices not too
far apart.