Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

On the periods of generalized Fibonacci recurrences


Author: Richard P. Brent
Journal: Math. Comp. 63 (1994), 389-401
MSC: Primary 11B37; Secondary 11B39
DOI: https://doi.org/10.1090/S0025-5718-1994-1216256-7
MathSciNet review: 1216256
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We give a simple condition for a linear recurrence $ \pmod {2^w}$ of degree r to have the maximal possible period $ {2^{w - 1}}({2^r} - 1)$. It follows that the period is maximal in the cases of interest for pseudorandom number generation, i.e., for three-term linear recurrences defined by trinomials which are primitive $ \pmod 2$ and of degree $ r > 2$. We consider the enumeration of certain exceptional polynomials which do not give maximal period, and list all such polynomials of degree less than 15.


References [Enhancements On Off] (What's this?)

  • [1] S. L. Anderson, Random number generators on vector supercomputers and other advanced architectures, SIAM Rev. 32 (1990), 221-251. MR 1056053 (91g:65015)
  • [2] R. P. Brent, On the periods of generalized Fibonacci recurrences, Technical Report TR-CS-92-03, Computer Sciences Laboratory, Australian National University, Canberra, March 1992.
  • [3] -, Uniform random number generators for supercomputers, Proc. Fifth Australian Supercomputer Conference, Melbourne, Dec. 1992, pp. 95-104.
  • [4] A. M. Ferrenberg, D. P. Landau, and Y. J. Wong, Monte Carlo simulations: Hidden errors from "good" random number generators, Phys. Rev. Lett. 69 (1992), 3382-3384.
  • [5] S. W. Golomb, Shift register sequences, Holden-Day, San Francisco, 1967. MR 0242575 (39:3906)
  • [6] B. F. Green, J. E. K. Smith, and L. Klem, Empirical tests of an additive random number generator, J. Assoc. Comput. Mach. 6 (1959), 527-537. MR 0107957 (21:6678)
  • [7] F. James, A review of pseudorandom number generators, Comput. Phys. Comm. 60 (1990), 329-344. MR 1076267 (91i:65013)
  • [8] D. E. Knuth, The art of computer programming, Volume 2: Seminumerical algorithms (2nd ed.), Addison-Wesley, Menlo Park, CA, 1981. MR 633878 (83i:68003)
  • [9] E. V. Krishnamurthy, Error-free polynomial matrix computations, Chapter 4, Springer-Verlag, New York, 1985. MR 811639 (88e:68003)
  • [10] H. T. Kung, On computing reciprocals of power series, Numer. Math. 22 (1974), 341-348. MR 0351045 (50:3536)
  • [11] Y. Kurita and M. Matsumoto, Primitive t-nomials $ (t = 3,5)$ over GF(2) whose degree is a Mersenne exponent $ \leq 44497$, Math. Comp. 56 (1991), 817-821. MR 1068813 (91h:11138)
  • [12] G. Marsaglia, A current view of random number generators, Computer Science and Statistics: The Interface (edited by L. Billard), Elsevier Science Publishers B. V. (North-Holland), 1985, 3-10.
  • [13] G. Marsaglia and L. H. Tsay, Matrices and the structure of random number sequences, Linear Algebra Appl. 67 (1985), 147-156. MR 787372 (86g:65018)
  • [14] J. F. Reiser, Analysis of additive random number generators, Ph. D. thesis, Department of Computer Science, Stanford University, Stanford, CA, 1977. Also Technical Report STAN-CS-77-601.
  • [15] E. R. Rodemich and H. Rumsey, Jr., Primitive trinomials of high degree, Math. Comp. 22 (1968), 863-865. MR 0238813 (39:177)
  • [16] I. Schur, Ganzzahlige Potenzreihen und linear rekurrente Zahlenfolgen, Issai Schur Gesammelte Abhandlungen, Band 3, Springer-Verlag, Berlin, 1973, pp. 400-421.
  • [17] W. Stahnke, Primitive binary polynomials, Math. Comp. 27 (1973), 977-980. MR 0327722 (48:6064)
  • [18] R. C. Tausworthe, Random numbers generated by linear recurrence modulo two, Math. Comp. 19 (1965), 201-209. MR 0184406 (32:1878)
  • [19] B. L. van der Waerden, Algebra, Vol. 1, Chapter 7 (English transl. by Fred Blum, 5th ed.), Ungar, New York, 1953.
  • [20] M. Ward, The arithmetical theory of linear recurring series, Trans. Amer. Math. Soc. 35 (1933), 600-628. MR 1501705
  • [21] E. J. Watson, Primitive polynomials $ \pmod 2$, Math. Comp. 16 (1962), 368-369. MR 0148256 (26:5764)
  • [22] H. Zassenhaus, On Hensel factorization, J. Number Theory 1 (1969), 291-311. MR 0242793 (39:4120)
  • [23] N. Zierler and J. Brillhart, On primitive trinomials $ \pmod 2$, Inform. and Control 13 (1968), 541-554. Also part II, ibid. 14 (1969), 566-569.
  • [24] N. Zierler, Primitive trinomials whose degree is a Mersenne exponent, Inform. and Control 15 (1969), 67-69. MR 0244205 (39:5522)
  • [25] -, On $ {x^n} + x + 1$ over GF(2), Inform. and Control 16 (1970), 502-505. MR 0271072 (42:5955)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11B37, 11B39

Retrieve articles in all journals with MSC: 11B37, 11B39


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1994-1216256-7
Keywords: Fibonacci sequence, generalized Fibonacci sequence, irreducible trinomial, linear recurrence, maximal period, periodic integer sequence, primitive trinomial, pseudorandom numbers
Article copyright: © Copyright 1994 American Mathematical Society

American Mathematical Society