Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Calculation of Fibonacci polynomials for GFSR sequences with low discrepancies

Authors: Shu Tezuka and Masanori Fushimi
Journal: Math. Comp. 60 (1993), 763-770
MSC: Primary 65C10; Secondary 11B39, 11Y99
MathSciNet review: 1160278
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Fibonacci polynomials are defined in the context of the two-dimensional discrepancy of Tausworthe pseudorandom sequences as an analogue to Fibonacci numbers, which give the best figure of merit for the two-dimensional discrepancy of linear congruential sequences. We conduct an exhaustive search for the Fibonacci polynomials of degree less than 32 whose associated Tausworthe sequences can be easily implemented and very quickly generated.

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

  • [1] D. A. André, G. L. Mullen, and H. Niederreiter, Figures of merit for digital multistep pseudorandom numbers, Math. Comp. 54 (1990), 737-748. MR 1011436 (91d:65012)
  • [2] I. Borosh and H. Niederreiter, Optimal multipliers for pseudorandom number generation by the linear congruential method, BIT 23 (1983), 65-74. MR 689604 (84e:65012)
  • [3] M. Fushimi, An equivalence relation between Tausworthe and GFSR sequences and applications, Applied Math. Lett. 2 (1989), 135-137. MR 1003844 (91e:65013)
  • [4] D. E. Knuth, The art of computer programming: Vol. 2, Seminumerical algorithms, 2nd ed., Addison-Wesley, Reading, MA, 1981. MR 633878 (83i:68003)
  • [5] T. G. Lewis and W. H. Payne, Generalized feedback shift register pseudorandom number algorithm, J. Assoc. Comput. Mach. 20 (1973), 456-468.
  • [6] J. P. Mesirov and M. M. Sweet, Continued fraction expansions of rational expressions with irreducible denominators in characteristic 2, J. Number Theory 27 (1987), 144-148. MR 909833 (89a:11016)
  • [7] G. L. Mullen and H. Niederreiter, Optimal characteristic polynomials for digital multistep pseudorandom numbers, Computing 39 (1987), 155-163. MR 919665 (88m:65011)
  • [8] H. Niederreiter, Pseudozufallszahlen und die Theorie der Gleichverteilung, Sitzungsber. Österreich. Akad. Wiss. Math.-Natur. Kl. Sitzungsber. II 195 (1986), 109-138. MR 881335 (88g:11045)
  • [9] -, A statistical analysis of generalized feedback shift register pseudorandom number generators, SIAM J. Sci. Statist. Comput. 8 (1987), 1035-1051. MR 911073 (89f:65009)
  • [10] -, Rational functions with partial quotients of small degree in their continued fraction expansion, Monatsh. Math. 103 (1987), 269-288. MR 897953 (88h:12002)
  • [11] -, Point sets and sequences with small discrepancy, Monatsh. Math. 104 (1987), 273-337. MR 918037 (89c:11120)
  • [12] -, The serial test for digital k-step pseudorandom numbers, Math. J. Okayama Univ. 30 (1988), 93-119. MR 976736 (90g:65011)
  • [13] R. C. Tausworthe, Random numbers generated by linear recurrence modulo two, Math. Comp. 19 (1965), 201-209. MR 0184406 (32:1878)
  • [14] S. Tezuka, On the discrepancy of GFSR pseudorandom numbers, J. Assoc. Comput. Mach. 34 (1987), 939-949. MR 913848 (88j:65014)
  • [15] -, On Fibonacci polynomials, Proc. of the IPSJ meeting on Algorithms, 3-7, Information Processing Soc. Japan, 1988. (in Japanese).
  • [16] -, Random number generation based on polynomial arithmetic modulo two, IBM TRL Research Report, RT-0017 (Oct. 1989).
  • [17] -, Low-discrepancy point sets based on a lattice in $ GF{\{ 2,x\} ^k}$, Proc. of the IPSJ meeting on Numerical Analysis, 31-1, Information Processing Soc. Japan, 1989.
  • [18] -, Lattice structure of pseudorandom sequences from shift register generators, Proceedings of the Winter Simulation Conference '90 (O. Balci, R. P. Sadowski, and R. E. Nance, eds.), IEEE Press, 1990, pp. 266-269.
  • [19] J. P. R. Tootill, W. D. Robinson, and D. J. Eagle, An asymptotically random Tausworthe sequence, J. Assoc. Comput. Mach. 20 (1973), 469-481.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65C10, 11B39, 11Y99

Retrieve articles in all journals with MSC: 65C10, 11B39, 11Y99

Additional Information

Keywords: Tausworthe sequences, Fibonacci polynomials, discrepancy, GFSR algorithms
Article copyright: © Copyright 1993 American Mathematical Society

American Mathematical Society