Twisted GFSR generators

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.

REFERENCES

• 1: BERLEKAMP, E. R Algebraic Codzng Theory. McGraw-Hill, New York, 1968.
• 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.
• 3: COMPAONER, A. The hierarchy of correlations in random binary sequences. J. Stat. Phys. 63 (1991), 883-896.
• 4: COMPA~NER, A. Defimtions of randomness. Am. J Phys. 59 (1991), 700 705,
• 5: M. Fushimi , S. Tezuka, The k-distribution of generalized feedback shift register pseudorandom numbers, Communications of the ACM, v.26 n.7, p.516-523, July 1983 [doi>10.1145/358150.358159]
• 6: FUSHIMI, M. Ransuu. Applied Mathematics Series Vol. 12, Tokyo University Press, Tokyo, 1989 (m Japanese).
• 7: Solomon W. Golomb , Soloman Golomb, Shift Register Sequences, Aegean Park Press, Laguna Hills, CA, 1981
• 8: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 9: KURITA, Y. Choosing parameters for congruential random number generators. In Recent Development in Statistics, J. R. Barra, Ed., North-Holland, Amsterdam, 1977.
• 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.
• 11: Pierre L'Ecuyer, Random numbers for simulation, Communications of the ACM, v.33 n.10, p.85-97, Oct. 1990 [doi>10.1145/84537.84555]
• 12: T. G. Lewis , W. H. Payne, Generalized Feedback Shift Register Pseudorandom Number Algorithm, Journal of the ACM (JACM), v.20 n.3, p.456-468, July 1973 [doi>10.1145/321765.321777]
• 13: LIDL, R., AND NIEDE~RErTER, H. Fintte Fzelds. Addison-Wesley, Reading, Mass., 1983.
• 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.
• 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.
• 16: MARSAGLIA, G. A current view of random numbers. In Computer Science and Statzstics: The Interface, L. Billard, Ed., Elsevier, New York, 1985.
• 17: MARSAGLIA, G., AND ZAMAN. A. A new class of random number generators. Ann. Appl. Probab. I (1991), 462 480.
• 18: Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 19: J. P. R. Tootill , W. D. Robinson , D. J. Eagle, An Asymptotically Random Tausworthe Sequence, Journal of the ACM (JACM), v.20 n.3, p.469-481, July 1973 [doi>10.1145/321765.321778]
• 20: ZIERLER, N, AND BRILLHART, J. On primitive trinomials (Mod 2). Inf. Control 13 (1968), 541-554.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Recurrences and difference equations

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Distributed

General Terms:
Algorithms, Experimentation, Theory

Keywords:
m-sequences, GF(2m/italic>), TLP-sequences, generalized feedback shift registers, matrix linear congruential generators