Information Technology Reference
In-Depth Information
increasing
k
. Because of the linearity, jumping ahead from
x
i
to
x
i
+
ν
is easy,
regardless of
ν
:Onecanwrite
x
i
+
ν
=
A
ν
x
i
mod
m
,where
A
ν
is a
k
×
k
matrix
that can be precomputed once for all [3].
It is well-known that in this case,
Ψ
s
is the intersection of a lattice
⎧
⎨
⎫
⎬
s
L
s
=
v
=
h
j
v
j
such that each
h
j
∈
Z
(12)
⎩
⎭
j
=1
with the unit hypercube [0
,
1)
s
[1,36], where a lattice basis
is easy
to obtain [36]. Theoretical measures of uniformity used in practice are defined in
terms of the geometry of this lattice. The lattice structure implies in particular
that
Ψ
s
is contained in a family of equidistant parallel hyperplanes. For the
family for which the successive hyperplanes are farthest apart, the inverse of the
distance between the successive hyperplanes is equal to the Euclidean length of
the shortest nonzero vector in the dual lattice
L
s
, defined by
L
s
=
{
v
1
,...,
v
s
}
s
{
h
∈
R
:
h
t
v
∈
Z
L
1
length of the shortest nonzero vector in
L
s
gives
the number of hyperplanes required to cover the points. The computing time of
these shortest vectors is exponential in
s
(in the worst case, with the best known
algorithms), but depends very little on
m
and
k
. In practice, one can handle
values of
s
up to 50 (or more, for easier lattices), even with
m
k
>
2
1000
[32].
Note that for every subset of coordinates
for all
v
∈
L
s
}
.The
u
=
{
i
1
,...,i
d
}
, the projection set
) is also the intersection of a lattice with the unit hypercube [0
,
1)
d
,andone
can compute the length
(
Ψ
(
u
u
) of a shortest nonzero vector in the corresponding
dual lattice
L
∗
(
). Moreover, for any given number of points
n
=
m
k
and a given
dimension
d
, there is a theoretical upper bound
d
(
n
)onthislength
(
u
u
). One
can divide
(
) by such an upper bound to obtain a standardized value between
0 and 1, and take the worst case over a selected class
u
J
of index sets
u
.This
gives a figure of merit of the form
)
/
|
u
|
min
u
∈J
(
u
(
n
)
.
(13)
This type of criterion has been proposed in [17]. Simplified versions, where
J
contains only the subsets of successive coordinates up to a given dimension, have
been used for a long time to measure the quality of RNGs [34,1,32,3].
It is important to look at the projections
Ψ
(
), because fast long-period (but
otherwise poorly designed) RNGs often have some very bad low-dimensional
projections. For example,
lagged-Fibonacci
generators follow the recurrence (11)
with only two nonzero coecients, say
a
r
and
a
k
, both equal to
u
±
1. It turns
out that for these generators, with
) lie
in only two parallel planes in the three-dimensional cube. This type of structure
can have a disastrous impact on certain simulations. The add-with-carry and
subtract-with-borrow generators, proposed in [37] and still available in some
popular software, have exactly the same problem. A well-chosen figure of merit
of the form (13) should give high penalties to these types of bad projections.
u
=
{
0
,k
−
r, k
}
,allthepointsof
Ψ
s
(
u
