Calculation of Fibonacci polynomials for GFSR sequences with low discrepancies
HTML articles powered by AMS MathViewer
- by Shu Tezuka and Masanori Fushimi PDF
- Math. Comp. 60 (1993), 763-770 Request permission
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
- Debra A. André, Gary L. Mullen, and Harald Niederreiter, Figures of merit for digital multistep pseudorandom numbers, Math. Comp. 54 (1990), no. 190, 737–748. MR 1011436, DOI 10.1090/S0025-5718-1990-1011436-4
- Itshak Borosh and Harald Niederreiter, Optimal multipliers for pseudorandom number generation by the linear congruential method, BIT 23 (1983), no. 1, 65–74. MR 689604, DOI 10.1007/BF01937326
- Masanori Fushimi, An equivalence relation between Tausworthe and GFSR sequences and applications, Appl. Math. Lett. 2 (1989), no. 2, 135–137. MR 1003844, DOI 10.1016/0893-9659(89)90006-2
- Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878 T. G. Lewis and W. H. Payne, Generalized feedback shift register pseudorandom number algorithm, J. Assoc. Comput. Mach. 20 (1973), 456-468.
- Jill P. Mesirov and Melvin M. Sweet, Continued fraction expansions of rational expressions with irreducible denominators in characteristic $2$, J. Number Theory 27 (1987), no. 2, 144–148. MR 909833, DOI 10.1016/0022-314X(87)90058-8
- G. L. Mullen and H. Niederreiter, Optimal characteristic polynomials for digital multistep pseudorandom numbers, Computing 39 (1987), no. 2, 155–163 (English, with German summary). MR 919665, DOI 10.1007/BF02310104
- Harald Niederreiter, Pseudozufallszahlen und die Theorie der Gleichverteilung, Österreich. Akad. Wiss. Math.-Natur. Kl. Sitzungsber. II 195 (1986), no. 1-3, 109–138 (German). MR 881335
- Harald Niederreiter, A statistical analysis of generalized feedback shift register pseudorandom number generators, SIAM J. Sci. Statist. Comput. 8 (1987), no. 6, 1035–1051. MR 911073, DOI 10.1137/0908084
- Harald Niederreiter, Rational functions with partial quotients of small degree in their continued fraction expansion, Monatsh. Math. 103 (1987), no. 4, 269–288. MR 897953, DOI 10.1007/BF01318069
- Harald Niederreiter, Point sets and sequences with small discrepancy, Monatsh. Math. 104 (1987), no. 4, 273–337. MR 918037, DOI 10.1007/BF01294651
- Harald Niederreiter, The serial test for digital $k$-step pseudorandom numbers, Math. J. Okayama Univ. 30 (1988), 93–119. MR 976736
- Robert C. Tausworthe, Random numbers generated by linear recurrence modulo two, Math. Comp. 19 (1965), 201–209. MR 184406, DOI 10.1090/S0025-5718-1965-0184406-1
- Shu Tezuka, On the discrepancy of GFSR pseudorandom numbers, J. Assoc. Comput. Mach. 34 (1987), no. 4, 939–949. MR 913848, DOI 10.1145/31846.31848 —, On Fibonacci polynomials, Proc. of the IPSJ meeting on Algorithms, 3-7, Information Processing Soc. Japan, 1988. (in Japanese). —, Random number generation based on polynomial arithmetic modulo two, IBM TRL Research Report, RT-0017 (Oct. 1989). —, 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. —, 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. J. P. R. Tootill, W. D. Robinson, and D. J. Eagle, An asymptotically random Tausworthe sequence, J. Assoc. Comput. Mach. 20 (1973), 469-481.
Additional Information
- © Copyright 1993 American Mathematical Society
- Journal: Math. Comp. 60 (1993), 763-770
- MSC: Primary 65C10; Secondary 11B39, 11Y99
- DOI: https://doi.org/10.1090/S0025-5718-1993-1160278-0
- MathSciNet review: 1160278