Skip to main content
Log in

An exact determination of serial correlations of pseudo-random numbers

  • Published:
Numerische Mathematik Aims and scope Submit manuscript

Summary

Exact expressions for serial correlations of sequences of pseudo-random numbers are derived. The reduction to generalized Dedekind sums is of optimum simplicity and covers all cases of the linear congruential method. The subsequent evaluation of the generalized Dedekind sums is based on a modified Euclidean algorithm whose quotients are recognized as the main contributors to the size of the serial correlations. This leads to the establishment of bounds as well as of fast computer programs. Moreover, some light is thrown upon the general question of quality in random number generation.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Ahrens, J., Dieter, U., Grube, A.: Pseudo-random numbers: A new proposal for the choice of multiplicators. Computing6, 121–138 (1970).

    Google Scholar 

  • Coveyou, R. R.: Serial correlation in the generation of pseudo-random numbers. J. Ass. Comp. Mach.7, 72–74 (1960).

    Google Scholar 

  • Dedekind, R.: Erläuterungen zu den Fragmenten XXVIII. In: B. Riemanns Gesammelten Werken, S. 466–478, 1892.

  • Dieter, U.: Das Verhalten der Kleinschen Funktion log σ g,h 1, ω2) gegenüber Modultransformationen und verallgemeinerte Dedekindsche Summen. Journal für die reine und angewandte Mathematik201, 37–70 (1959).

    Google Scholar 

  • — Autokorrelation multiplikativ-erzeugter Pseudo-Zufallszahlen. Operations-Research-Verfahren,VI, 69–85 (1968).

    Google Scholar 

  • Dieter, U.: Pseudo-Random numbers: The exact distribution of pairs. Mathematics of Computation 25, October 1971.

  • Dieter, U.: Pseudo-Random numbers: Permutation of triplets. To appear.

  • Greenberger, M.: An a priori determination of serial correlation in computer generated random numbers. Math. Comp.15, 383–389 (1961).

    Google Scholar 

  • Hull, E., Dobell, A. R.: Random number generators. SIAM Review4, 230–254 (1962).

    Google Scholar 

  • Jansson, B.: Autocorrelations between pseudo-random numbers. BIT4, 6–27 (1964).

    Google Scholar 

  • — Random number generators. Stockholm: Almqvist and Wiksell 1966.

    Google Scholar 

  • Knuth, D. E.: The art of computer programming. Vol. 2./Semi-numerical algorithms. Reading, Mass: Addison-Wesley Comp. 1969.

    Google Scholar 

  • Meyer, C.: Über einige Anwendungen Dedekindscher Summen. Journal für die reine und angewandte Mathematik198, 143–203 (1957).

    Google Scholar 

  • — Bemerkungen zu den allgemeinen Dedekindschen Summen. Journal für die reine und angewandte Mathematik205, 186–196 (1960/61).

    Google Scholar 

  • Rademacher, H.: Zur Theorie der Modulfunktionen. Journal für die reine und angewandte Mathematik167, 312–336 (1932).

    Google Scholar 

  • — Some remarks on certain generalized Dedekind sums. Acta Arithmetica 9, 97–105 (1964).

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Additional information

Dedicated to Prof. H. Schubert, Kiel on the occasion of his 50th birthday

Research supported by the DFG (Deutsche Forschungsgemeinschaft) and Nova Scotia Technical College, Halifax, N.S. Canada.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Dieter, U., Ahrens, J. An exact determination of serial correlations of pseudo-random numbers. Numer. Math. 17, 101–123 (1971). https://doi.org/10.1007/BF01406000

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01406000

Keywords

Navigation