Fast linear congruential pseudorandom number generators using the Messerschmitt pipelining transformation
Fast linear congruential pseudorandom number generators using the Messerschmitt pipelining transformation
- Author(s): N. Burgess and K.V. Lever
- DOI: 10.1049/ip-e.1992.0020
For access to this article, please select a purchase option:
Buy article PDF
Buy Knowledge Pack
IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.
Thank you
Your recommendation has been sent to your librarian.
- Author(s): N. Burgess 1 and K.V. Lever 1
-
-
View affiliations
-
Affiliations:
1: Department of Electrical Engineering and Electronics, Brunel University, Uxbridge, UK
-
Affiliations:
1: Department of Electrical Engineering and Electronics, Brunel University, Uxbridge, UK
- Source:
Volume 139, Issue 2,
March 1992,
p.
131 – 133
DOI: 10.1049/ip-e.1992.0020 , Print ISSN 0143-7062, Online ISSN 2053-7948
The speed of generation of uniformly distributed pseudorandom numbers by means of the conventional linear congruence algorithm is limited by the time taken to perform the arithmetic operations required. Iterating the system equation provides new forms of the algorithm which can be pipelined for higher speed.
Inspec keywords: pipeline processing; random number generation
Other keywords:
Subjects: Logic and switching circuits; Parallel architecture; Digital arithmetic methods
References
-
-
1)
- D. Zuras , W. McAllister . Balanced delay trees and combinatorial division in VLSI. IEEE J. , 814 - 819
-
2)
- Lehmer, D.H.: `Mathematical methods in large-scale computing units', Proceedings of the Second Symposium on Large-Scale Digital Calculating Machinery, 1951, Harvard University Press, , p. 141–146.
-
3)
- H.H. Lu , E.A. Lee , D.G. Messerschmitt . Fast recursive filtering with multiple slow processing elements. IEEE Trans. , 1119 - 1129
-
4)
- Messerschmitt, D.G.: `Breaking the recursive bottleneck', Proceedings of NATO Advanced Study Institute, 7–9 July 1986, Lucca , Matrinus Nijhoff, Performance limits in communication: theory and practice.
-
5)
- B. Liv , D.C. Munson . Generation of a random sequence having a jointly specified marginal distribution and autcovariance. IEEE Trans. , 6 , 973 - 983
-
6)
- Parhi, K.K., Hatamian, M.: `A high sample rate recursive digital filter chip', Proc. IEEE VLSI Signal Processing Workshop, November 1988, Monterey.
-
7)
- D.K. Knuth . (1981) The art of computer programming, Seminumerical algorithms.
-
8)
- K.K. Parhi , D.G. Messerschmitt . Pipeline interleaving and parallelism in recursive digital filters — Part I: Pipelining using scattered look-ahead and decomposition. IEEE Trans. , 7 , 1099 - 1117
-
9)
- Broste, N.E.: `Digital generation of random sequences with specified autocorrelation and probability density functions', RE-TR-70-5, Report, 6 March 1970, p. 17.
-
10)
- K. Hwang . (1979) , Computer arithmetic.
-
11)
- B.A. Wichmann , I.D. Hill . Building a random-number generator. BYTE , 3 , 127 - 128
-
12)
- K.K. Parhi , D.G. Messerschmitt . Pipeline interleaving and parallelism in recursive digital filters — Part II: Pipelined incremental block filtering. IEEE Trans. , 7 , 1117 - 1134
-
13)
- G.J. Janacek , K.V. Lever . Analysis and synthesis of ultra-uniform pseudorandom number generators. IMA J. Math. Cont. Inform. , 215 - 232
-
14)
- R. Taori , G.D. Cain , K.V. Lever . Correlation windowing and spectral biasing in the design of noise generators having specified probability densities and power spectra. Electr. Lett. , 14 , 1041 - 1043
-
15)
- P.A.W. Lewis , E.J. Orav . (1989) , Statistical methodology for statisticians, operations analysts, and engineers.
-
16)
- A. Vandermeulebroecke , E. Vanzieleghem , T. Denayer , P.G.A. Jespers . A new carry-free division algorithm and its application to a single-chip 1024-b RSA processor. IEEE J. , 748 - 755
-
17)
- Parhi, K.K., Messerschmitt, D.G.: `Look-ahead computation: improving iteration bound in linear recursions', Proc. IEEE Int. Conf. on Acoustics, Speech and Signal Processing, 1987, Dallas, p. 1855–1858.
-
18)
- B.A. Wichmann , I.D. Hill . An efficient and portable pseudo-random number generator. Appl. Stat. , 188 - 190
-
19)
- R.C. Coates , G.J. Janacek , K.V. Lever . Monte Carlo simulation and random number generation. IEEE J. , 1 , 58 - 66
-
20)
- M.M. Sondhi . Random processes with specified spectral density and first-order probability density. Bell Syst. Tech. J. , 679 - 700
-
21)
- Wichmann, B.A., Hill, I.D.: `A pseudo-random number generator', No. DITC 6/82, National Physical Laboratory Report, 1982.
-
22)
- D.K. Knuth . (1981) The art of computer programming, Vol. 2, Seminumerical algorithms.
-
23)
- U.G. Gujar , R.J. Kavanagh . Generation of random signals with specified probability density functions and power density spectra. IEEE Trans. Autom. Control , 716 - 719
-
1)
Related content
