Information Technology Reference
In-Depth Information
We see that for the 32-bit computer, PM is faster than SW when
k
≥
44497,
whereas for the 64-bit machine, PM is faster for
k
19937. The results agree
with the computational complexity approximations, which are
O
(
k
2
) for SW and
O
(
k
1
.
59
)forPM.
≥
7Con lu on
The proposed jump ahead algorithm based on polynomial multiplication is ad-
vantageous over the sliding window method when the dimension
k
of state space
is large enough, since the new PM method has time complexity
O
(
k
1
.
59
), com-
pared with
O
(
k
2
) for the sliding window method. Our empirical experiments
confirm this and show that this large enough
k
corresponds roughly to the
value of
k
used in the most popular implementation of MT. Much more impor-
tantly, the new PM method has space complexity of
O
(
k
), which is much smaller
than that of the sliding window method, namely
O
(
k
2
q
). The main limitation
is that the new method requires the availability of an ecient algorithm to com-
pute the inverse of
o
(
k
)
.
References
1. Law, A.M., Kelton, W.D.: Simulation Modeling and Analysis, 3rd edn. McGraw-
Hill, New York (2000)
2. L'Ecuyer, P., Buist, E.: Simulation in Java with SSJ. In: Proceedings of the 2005
Winter Simulation Conference, pp. 611-620. IEEE Press, Los Alamitos (2005)
3. L'Ecuyer, P.: Pseudorandom number generators. In: Platen, E., Jaeckel, P. (eds.)
Simulation Methods in Financial Engineering. Encyclopedia of Quantitative Fi-
nance. Wiley, Chichester (forthcoming, 2008)
4. Matsumoto, M., Nishimura, T.: Mersenne twister: A 623-dimensionally equidis-
tributed uniform pseudo-random number generator. ACM Transactions on Model-
ing and Computer Simulation 8(1), 3-30 (1998)
5. Panneton, F., L'Ecuyer, P., Matsumoto, M.: Improved long-period generators
based on linear recurrences modulo 2. ACM Transactions on Mathematical Soft-
ware 32(1), 1-16 (2006)
6. Haramoto, H., Matsumoto, M., Nishimura, T., Panneton, F., L'Ecuyer, P.: E-
cient jump ahead for
F
2
-linear random number generators. INFORMS Journal on
Computing (to appear, 2008)
7. Panneton, F., L'Ecuyer, P.: Infinite-dimensional highly-uniform point sets defined
via linear recurrences in
F
2
w
. In: Niederreiter, H., Talay, D. (eds.) Monte Carlo
and Quasi-Monte Carlo Methods 2004, pp. 419-429. Springer, Berlin (2006)
8. L'Ecuyer, P.: Uniform random number generation. Annals of Operations Re-
search 53, 77-120 (1994)
9. L'Ecuyer, P., Panneton, F.:
F
2
-linear random number generators. In: Alexopoulos,
C., Goldsman, D. (eds.) Advancing the Frontiers of Simulation: A Festschrift in
Honor of George S. Fishman, Spinger, New York (to appear, 2007)
10. Couture, R., L'Ecuyer, P.: Lattice computations for random numbers. Mathematics
of Computation 69(230), 757-765 (2000)
