Makoto Matsumoto
Abstract
The generalized feed back shift register (GFSR) algorithm suggested by Lewis and Payne is a widely used pseudorandom number generator, but has the following serious drawbacks: (1) an initialization scheme to assure higher order equidistribution is involved and is time consuming; (2) each bit of the generated words constitutes an m-sequence based on a primitive trinomials, which shows poor randomness with respect to weight distribution; (3) a large working area is necessary; (4) the period of sequence is far shorter than the theoretical upper bound. This paper presents the twisted GFSR (TGFSR) algorithm, a slightly but essentially modified version of the GFSR, which solves all the above problems without loss of merit. Some practical TGFSR generators were implemented and passed strict empirical tests. These new generators are most suitable for simulation of a large distributive system, which requires a number of mutually independent pseudorandom number generators with compact size.
- 1 BERLEKAMP, E. R Algebraic Codzng Theory. McGraw-Hill, New York, 1968.Google Scholar
- 2 BRmLUART, J., LEHMER, D. H.; SELFRIDGE, J. L., TUCKERMAN, B., AND WAGSTAFF, S. S., JR. Factorizations of b'~ + 1. In Contemporary Mathematics, Vol. 22, 2nd ed., AMS, Providence, R.I., 1988.Google Scholar
- 3 COMPAONER, A. The hierarchy of correlations in random binary sequences. J. Stat. Phys. 63 (1991), 883-896.Google Scholar
- 4 COMPA~NER, A. Defimtions of randomness. Am. J Phys. 59 (1991), 700 705,Google Scholar
- 5 FUSHIMI, M., AND TEZUKA, S. The k-distribution of generalized feedback shift register pseudorandom numbers. Commun. ACM 26 (1983), 516 523. Google Scholar
- 6 FUSHIMI, M. Ransuu. Applied Mathematics Series Vol. 12, Tokyo University Press, Tokyo, 1989 (m Japanese).Google Scholar
- 7 GOLOMB, S.W. Shift Register Sequences. Holden-Day, San Francisco, 1967. Google Scholar
- 8 KNUTH, D.E. The Art of Computer Programmtng, Vol. 2: Semtnumerzcal Algorzthms, 2nd Ed., Addison-Wesley, Reading, Mass., 1981. Google Scholar
- 9 KURITA, Y. Choosing parameters for congruential random number generators. In Recent Development in Statistics, J. R. Barra, Ed., North-Holland, Amsterdam, 1977.Google Scholar
- 10 KURITA, Y., AND MATSUMOTO, M. Primitive t-nomials (t - 3, 5) over GF(2) whose degree is a Mersenne exponent < 44497. Math. Comput. 56 (1991), 817-821.Google Scholar
- 11 L'EcusmR, P. Random numbers for simulation. Commun. ACM 33, 10 (1990), 85-97. Google Scholar
- 12 LEwis, T. G., AND PAYNE, W.H. Generalized feedback shift register pseudorandom number algorithms. J. ACM 20, 3 tJuly 1973), 456-468. Google Scholar
- 13 LIDL, R., AND NIEDE~RErTER, H. Fintte Fzelds. Addison-Wesley, Reading, Mass., 1983.Google Scholar
- 14 LINDHOLM, J.H. An analysis of the pseudo-randomness properties of subsequences of long m-sequences. IEEE Trans. Inf. Theor. IT-14 (July 1968), 569-576.Google Scholar
- 15 MATSUMOTO, M., AND KURITZ, Y. The fixed point of an m-sequence and local nonrandomness. Tech. Rep., Dept. of Information Science, Univ. Tokyo 88-027, 1988.Google Scholar
- 16 MARSAGLIA, G. A current view of random numbers. In Computer Science and Statzstics: The Interface, L. Billard, Ed., Elsevier, New York, 1985.Google Scholar
- 17 MARSAGLIA, G., AND ZAMAN. A. A new class of random number generators. Ann. Appl. Probab. I (1991), 462 480.Google Scholar
- 18 NIEDER~EITER, H. Random Number Generatton and Quasi-Monte Carlo Methods. SIAM, Philadelphia, Pa., 1992. Google Scholar
- 19 TOOTmL, J. P. R., ROBINSON, W. D., AND EAGLE, D.J. An asymptotically random Tausworthe sequence. J. ACM 20, 3 (July 1973), 469-481. Google Scholar
- 20 ZIERLER, N, AND BRILLHART, J. On primitive trinomials (Mod 2). Inf. Control 13 (1968), 541-554.Google Scholar
Index Terms
- Twisted GFSR generators
Recommendations
Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator
Special issue on uniform random number generationA new algorithm called Mersenne Twister (MT) is proposed for generating uniform pseudorandom numbers. For a particular choice of parameters, the algorithm provides a super astronomical period of 219937 −1 and 623-dimensional equidistribution up to 32-...
Twisted GFSR generators II
The twisted GFSR generators proposed in a previous article have a defect in k-distribution for k larger than the order of recurrence. In this follow up article, we introduce and analyze a new TGFSR variant having better k-distribution property. We ...
Spectral Analysis of the MIXMAX Random Number Generators
We study the lattice structure of random number generators of the MIXMAX family, a class of matrix linear congruential generators that produces a vector of random numbers at each step. The design of these generators was inspired by Kolmogorov K-systems ...
Comments