Information Technology Reference
In-Depth Information
A variant of the multiple recursive generator is the multiply-with-carry gen-
erator, based on a linear recurrence with carry:
x
i
=(
a
1
x
i−
1
+
···
+
a
k
x
i−k
+
c
i−
1
)
d
mod
b,
c
i
=
(
a
0
x
i
+
a
1
x
i−
1
+
···
+
a
k
x
i−k
+
c
i−
1
)
/b
,
u
i
=
x
i
/b
+
x
i
+1
/b
2
+
···
where
b
≥
2 is an integer,
a
0
is relatively prime to
b
,and
d
is the multiplicative
inverse of
a
0
modulo
b
. In practice, the expansion that defines
u
i
is truncated
to a few terms. An important result, if we neglect this truncation, states that
−
this RNG is exactly equivalent to an LCG with modulus
m
=
k
=0
a
b
and
multiplier
a
equal to the inverse of
b
modulo
m
[38,39,40]. This means that
this RNG can be seen as a clever way of implementing an LCG with very large
modulus and large period (this RNG can be quite fast if
b
is a power of two,
for example), and that its uniformity can be measured in terms of the lattice
structure of this LCG [39].
4 RNGs Based on Linear Recurrences Modulo 2
Another important class of construction methods uses a linear recurrence as in
(11), but with
m
= 2 [41,42]. That is, all operations are performed in the finite
field
F
2
=
{
0
,
1
}
. This general construction canbewritteninmatrixformas
[3,31]:
w
y
i,−
1
2
−
,
x
i
=
Ax
i−
1
,
y
i
=
Bx
i
,
i
=
=1
where
x
i
=(
x
i,
0
,...,x
i,k−
1
)
t
is the
state
at step
i
,
A
is a
k
×
k
binary matrix,
y
i
=(
y
i,
0
,...,y
i,w−
1
)
t
,
B
is a
w
×
k
binary matrix,
k
and
w
are positive integers,
and
u
i
∈
[0
,
1) is the
output
at step
i
. (In practice, the output can be modified
slightly to avoid returning 0.)
This framework covers several well-known generators such that the Taus-
worthe, polynomial LCG, generalized feedback shift register (GFSR), twisted
GFSR, Mersenne twister, WELL, xorshift, linear cellular automaton, and com-
binations of these [43,3,31,44,42]. With a careful design, for which
A
has a prim-
itive characteristic polynomial over
F
2
, the period length can reach 2
k
1. The
matrices
A
and
B
should be constructed so that the products (14) and (14)
can be computed very quickly by a few simple binary operations on blocks of
bits, such as or, exclusive-or, shift, and rotation. A compromise must be made
between the number of such operations and a good uniformity of the point sets
Ψ
s
(with too few operations, there are in general limitations on the quality of the
uniformity that can be reached). For these types of generators, the uniformity of
the point sets
Ψ
s
is measured by their
equidistribution
properties, as explained
in Section 6.
Combined generators of this type, defined by xoring the output vectors
y
i
of
the components, are equivalent to yet another generator from the same class.
−
