A FAST VECTORISED IMPLEMENTATION OF WALLACE’S NORMAL RANDOM NUMBER GENERATOR

RICHARD P. BRENT

Abstract

Wallace has proposed a new class of pseudo-random generators for normal variates. These generators do not require a stream of uniform pseudo-random numbers, except for initialisation. The inner loops are essentially matrix-vector multiplications and are very suitable for implementation on vector processors or vector/parallel processors such as the Fujitsu VPP300. In this report we outline Wallace’s idea, consider some variations on it, and describe a vectorised implementation RANN4 which is more than three times faster than its best competitors (the Polar and Box-Muller methods) on the Fujitsu VP2200 and VPP300.

Comments

Only the Abstract is given here. The full report appeared as [3] and a preliminary version as [2]. The idea is to vectorize Wallace’s method [5]. For earlier (and slower) methods, see [1, 4].

References

[1] R. P. Brent, Fast Normal Random Number Generators for Vector Processors, Technical Report TR-CS-93-04, Computer Sciences Laboratory, Australian National University, March 1993. Also Area 4 working note #4.

   ftp://nimbus.anu.edu.au/pub/Brent/rpb141tr.dvi.Z

[2] R. P. Brent, Wallace’s fast normal random number generators: preliminary report, Fujitsu Area 4 Project Report, October 1994, 6 pp.

[3] R. P. Brent, A fast vectorised implementation of Wallace’s normal random number generator, Technical Report TR-CS-97-07, Computer Sciences Laboratory, Australian National University, April 1997, 9 pp. Also Area 4

   Working Note # 21. ftp://nimbus.anu.edu.au/pub/Brent/rpb170tr.dvi.Z

[4] W. P. Petersen, Some vectorized random number generators for uniform, normal, and Poisson distributions for CRAY X-MP, J. Supercomputing, 1:327–335, 1988.

[5] C. S. Wallace, Fast Pseudo-Random Generators for Normal and Exponential Variates, ACM Trans. on Mathematical Software 22 (1996), 119–127.

Computer Sciences Laboratory, Australian National University, Canberra, ACT 0200

   E-mail address: Richard.Brent@anu.edu.au

Date: 14 April 1997.

1991 Mathematics Subject Classification. Primary 65C10, Secondary 54C70, 60G15, 65Y10, 68U20.

Key words and phrases. Gaussian random numbers, maximum entropy, normal distribution, normal random numbers, pseudo-random numbers, random number generators, random numbers, simulation, vector processors, Wallace’s method.

Copyright \begin{matrix}c \\ ◯ \end{matrix} 1997, R. P. Brent. rpb170a typeset using AMS-L^{A}TEX.