Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

Fast linear congruential pseudorandom number generators using the Messerschmitt pipelining transformation

Fast linear congruential pseudorandom number generators using the Messerschmitt pipelining transformation

For access to this article, please select a purchase option:

Buy article PDF
£12.50
(plus tax if applicable)
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)

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.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IEE Proceedings E (Computers and Digital Techniques) — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

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.

References

    1. 1)
      • D. Zuras , W. McAllister . Balanced delay trees and combinatorial division in VLSI. IEEE J. , 814 - 819
    2. 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. 3)
      • H.H. Lu , E.A. Lee , D.G. Messerschmitt . Fast recursive filtering with multiple slow processing elements. IEEE Trans. , 1119 - 1129
    4. 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. 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. 6)
      • Parhi, K.K., Hatamian, M.: `A high sample rate recursive digital filter chip', Proc. IEEE VLSI Signal Processing Workshop, November 1988, Monterey.
    7. 7)
      • D.K. Knuth . (1981) The art of computer programming, Seminumerical algorithms.
    8. 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. 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. 10)
      • K. Hwang . (1979) , Computer arithmetic.
    11. 11)
      • B.A. Wichmann , I.D. Hill . Building a random-number generator. BYTE , 3 , 127 - 128
    12. 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. 13)
      • G.J. Janacek , K.V. Lever . Analysis and synthesis of ultra-uniform pseudorandom number generators. IMA J. Math. Cont. Inform. , 215 - 232
    14. 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. 15)
      • P.A.W. Lewis , E.J. Orav . (1989) , Statistical methodology for statisticians, operations analysts, and engineers.
    16. 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. 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. 18)
      • B.A. Wichmann , I.D. Hill . An efficient and portable pseudo-random number generator. Appl. Stat. , 188 - 190
    19. 19)
      • R.C. Coates , G.J. Janacek , K.V. Lever . Monte Carlo simulation and random number generation. IEEE J. , 1 , 58 - 66
    20. 20)
      • M.M. Sondhi . Random processes with specified spectral density and first-order probability density. Bell Syst. Tech. J. , 679 - 700
    21. 21)
      • Wichmann, B.A., Hill, I.D.: `A pseudo-random number generator', No. DITC 6/82, National Physical Laboratory Report, 1982.
    22. 22)
      • D.K. Knuth . (1981) The art of computer programming, Vol. 2, Seminumerical algorithms.
    23. 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
http://iet.metastore.ingenta.com/content/journals/10.1049/ip-e.1992.0020
Loading

Related content

content/journals/10.1049/ip-e.1992.0020
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
This is a required field
Please enter a valid email address