×

Random numbers and computers. (English) Zbl 1497.65002

Cham: Springer (ISBN 978-3-319-77696-5/hbk; 978-3-319-77697-2/ebook). xv, 259 p. (2018).
The generation of random and pseudorandom numbers, usually considered as sequences, is an important tool of Monte Carlo (MC) and quasi-Monte Carlo (QMC) methods. MC and QMC are an excellent technique for approximate solutions of many problems of numerical integration, finance, stochastic differential equations and others.
The present book is a book about random numbers and computers. This is a book about algorithms capable to generate sequences of numbers that, according to a series of statistical tests, are suitably indistinguishable from number sequences, generated by true random processes. The book is divided into 7 chapters and an index.
The randomness is a fuzzy and difficult concept. In Chapter 1 the philosophical issue and instead focus on random and pseudorandom sequences are considered. Many examples of processes that generate random sequences are given and discussed.
In Section 1.1 it is made an attempt to answer of the question “What is randomness?”. The idea of a random sequence is given: a sequence of numbers within some bounded range, where it is nit possible to predict \(n_{k+1}\) from any combination of preceding valus \(n_i\), \(i = 0,1, \ldots, k.\) Many examples of random processes and their distributions are given.
In Section 1.2 an interesting experiment is presented – how humans to when asked to generate a random number in the range.
In Section 1.3 the concept of pseudorandom sequence is considered – a pseudorandom sequence is a deterministically generated sequence of numbers that is indistinguishable from a true random sequence of numbers. This concept is discussed. An algorithm to generate a pseudorandom sequence, the so-called “middle square” method of von Neumann, is explained.
In Section 1.4 it is discussed the idea that pseudorandom numbers generators can be good or bad in relation to some purpose for which we desire a sequence of random numbers. A fun and attractive use for random numbers – the generation of fractal images via the iterated function systems or Barnsley is presented.
In Section 1.5 the Intel Digital Random Numbers Generator Software Implementation Guide is presented. A code which decides the Monty Hall Dilemma is given.
In Section 1.6 a small summary about random and pseudorandom sequences is developed. This chapter finishes with exercises, connected with the considered problems.
Chapter 2 is devoted to the generation of uniform random numbers. This chapter examines techniques for generation of pseudorandom integers: some historical, some useful for noncritical tasks such as games, and others.
In Section 2.1 the notion of a uniform pseudorandom number generator, as a process which produces a sequence of integers over some range, is developed. The random floating-point numbers to estimate the value of \(\pi\) is used. The code of this procedure is given.
In Section 2.2 the mixed linear congruent generators are considered. The basis of these generators is an algebraic method using modular arithmetic that produces sequences of numbers which, when carefully tuned, can pass enough random use tests to be useful. It is shown how to select the parameters \(a,c\) and \(m\) in the linear congruent generator \[ x_{n+1} = (a x_n + c) \mod m, \] to produce a usable sequence of integers. The problem that while good generators exists, we must be careful when using them and aware of the limited period they often, is discussed.
In Section 2.3 the concept of the Mersenne Twister (MT) as a standard for pseudorandom generators is developed. The mathematical basis of the MT is presented. The Python program is given. The faster variant of the MT, the so-called SFMT package, is presented. The runtime of the original twister with SFMT is compared.
In Section 2.4 the xorshift generator of Marsaglia is developed. The generator and several of its newer variants that are capable of passing the most stringent of statistical tests are described. The C code for xorshift generator is given.
In Section 2.5 the Complementary Multiple-with-Carry family of generators is considered. The codes of these generators are shown. The periods of the presented generators are discussed.
In Section 2.6 the counter-based pseudorandom numbers generators are introduced. The Threefry and Philox generators are also considered, and the corresponding codes are given.
In Section 2.7 the combined generators are considered. Two approaches, that of L’Ecuyer, where two are more linear congruent generators are combined to produce a single generator that has a period much longer that any one generator. The generator that combines three separate generators: a linear congruent generator, an xorshift generator and a multiply-with-carry generator, is presented. The corresponding codes are given.
In Section 2.8 the relative performance of the yet considered generators is studied. Performance here means how quickly they generate a certain numbers of samples.
In Section 2.9 the quasirandom generators are discussed. It is shown how to generate the Halton sequence in a base \(b,\) where \(b\) is usually a small prime. Two approaches – strong linear correlation and reduced linear correlation of the Halton sequence are proposed. This chapter finishes with exercises, connected with the considered problems.
In Chapter 3 it is shown how to transform uniform random numbers into samples from other distributions. The standard or commonly found distributions are considered and the cookbook of these transformations is developed. The code for the transformations is given. Also, the effects of different uniform generators on the output are investigated.
In Section 3.1 the concept of nonuniform random numbers is presented. The program that generates uniformly distributed doubles is given.
In Section 3.2 the concept of the normal or Gaussian distribution is developed. Here, two ways to transform uniform samples to normal one – the Box-Muller method and the polar method of Marsaglia, are considered. The code for the Box-Muller transform is given. An implementation of the polar method is presented. Histograms for 70 million normaly distributed samples generated by Box-Muller and the polar method are given.
In Section 3.3 the binomial distribution is considered. Various binomial distributions are graphically illustrated. Also, the code that generated sample with binomial distribution is given.
In Section 3.4 the gamma and beta distributions are considered. It is shown how to parametrize the gamma distribution. Two approaches to sampling from a gamma distribution – the Ahrens GS algorithm and the Marsaglia-Tsang method are considered and their codes are given. Also, the code that generate samples from beta distribution is given.
In Section 3.5 the exponential distribution is considered. The basic idea of this distribution is developed.
In Section 3.6 the Poisson distribution is considered. The relationships with the binomial distribution is shown. Some histograms of the Poisson distribution are presented. Chapter 3 finishes with examples devoted to different kinds of distributions.
Testing pseudorandom number generators is not quite as straighforward as it might seem. In Chapter 4 some classical tests of randomness are considered. Two popular test suites – dieharder and one quick test program are investigated.
Section 4.1 is devoted to the study of some classical randomness tests. There are many ways of assessing the quality of a pseudorandom generator or a fill of numbers created by a pseudorandom or random process. In this section eight hypothesis tests are implemented – the \(\chi^2\) test, Kolmogorov-Smirnov test, serial test, gap test, maximum-of-\(t\) test, serial correlation test, permutation test and random excursion test. These tests are theoretically explained, also codes for their practical realizations are given.
In Section 4.2 the classical randomness tests are applied to the generators, which was developed in Chapter 2 of the book along with data that known. Especially \(\chi^2\) and Kolmogorov-Smirnov tests are applied and the obtained results are compared.
In Section 4.3 the dieharded random number test is studied. Many codes are presented. It is shown how to instal and use, at a very basic level.
In Section 4.4 the C software library for testing pseudorandom generator, namely TestU01, is considered. These tests are separated into three groups – the Small Crush, the Crush and the Big Crush.
Sometime, we may have a file of bytes that is too small for the exhaustive tests of dieharded or TestU01. In this situation, we can make use of the simpler end program which is included with most common Linux distributions. This end program is presented in Section 4.5. This chapter finishes with exercises, connected with the considered problems.
In Chapter 5 the parallel random number generators are studied. Many separate threads or processes require independent streams of pseudorandom numbers. This chapter examines five methods for generating such streams: a pseudorandom number server process, separated per stream generators, partitioning a single stream into non-overlapping segments, random seeding that relies on the small likelihood of randomly picking overlapping streams and merging two randomly initialized generator outputs. Implementations of certain generators are developed.
The generators, introduced in Chapter 2, all generate a single stream of pseudorandom values from an initial seed or state. In Section 5.1 it is answered to the question: how do we use a single stream of pseudorandom numbers with multiple or process? Four answers to this question are presented – use a random number server process, use separate pseudorandom number generator types per stream, partitioning the pseudorandom stream into non-overlapping segments and random seeding of a single generator type per stream. In this section the last three approaches are examined.
An approach to parallel generators is to use a different generators for each stream. If the number of streams is small and the number of available generators is at least as large, then this approach might work well. An other approach is to use a common base generator for each stream but to vary the parameters of the generator, so that each stream will created a different sequences of random values. The last problem theoretically is solved in Section 5.2 and also the corresponding codes are given.
If we split the output of a single generator into \(n\) non-overlapping subsequences, each \(m\) samples long, we would then be assured of having truly independent streams of random numbers as long as our processes consumed less than \(m\) samples we seed the generator, call it \(m\) times strong the output somewhere, and call this output “stream1”. Then, without reseeding, we call the generator another \(m\) tomes, store that output, and call it “stream2”, and so on until we have output for \(n\) streams. This is highly inefficient because it requires \(n \cdot m\) calls to the generator to say nothing of the overhead of strong all those samoles and creating code to quickly use them when needed by the proper stream. What would be nice wold bo to advance the generator some number of samples, say \(m\), without generating all the samples in-between. In that case, we only need to advance the generator \( i m\) samples where \(m\) is the number of samples per stream and \(i\) is the current stream number starting with zero. The above problems are solved in Section 5.3. Also, many codes are presented.
In Section 5.4 an another approach to parallel pseudorandom number generation is developed. This approach use the same underlying generator each time but is not skipping ahead by any amound. Instead, we are simply hoping that we will land in sufficiently different parts of the space of sequences output by the generator to be immune to overlap or other spurious correlations between the streams.
In Section 5.5 a new method for producing parallel streams of random samples is implemented and tested. The steps to produce a stream of output are:
1.)
Select a seed \(s_1\) for generator \(G_1;\)
2.)
Select a seed \(s_2\) for generator \(G_2;\)
3.)
Each sample requested is \(G_1XOR G_2.\)
Also, the code of this method is presented.
In Section 5.6 the counter-based generators in parallel are discussed. In Sections 5.7 and 5.8, the investigated five approaches in Chapter 5, are applied to the problem of generating independent streams of pseudorandom values in parallel. This chapter finishes with exercises, connected with the considered problems.
Cryptographically secure pseudorandom generators are pseudorandom number generators that protect against attack while still providing high quality pseudorandom values.
In Chapter 6 four secure generators are considered. The first, Blum Blum Shub is of historic interest, it should not be used for any cryptography work. The second, ISAAC is currently believed to be secure but does not make use of external entropy sources. The third generator, the so-called Fortuna, makes use of external entropy sources and explicit acts against state know ledge. The fourth generator, the so-called ChaCha20 is similar to Fortuna and is used by Google for Transport Layer Security. These four generators are described in Sections 6.2–6.5. The corresponding codes are given.
In Section 6.6 the implementations of these generators are discussed. This chapter finished with exercises, connected with the considered problems.
In Chapter 7 four different kinds of sequences of numbers that exhibit randomness are considered.
In Section 7.2 the expansion of normal numbers in some base is considered. A code for obtaining of some digits of \(\pi\) is given. Several others examples are considered.
In Section 7.3 the factorials of different sizes are considered. Here, the next problem is solved: we would like to know how many zeros there will be at the end of \(n !\) by looking at \(n\) before the factorial is even computed. This problem is solved on algorithmic and program aspect.
In Section 7.4 the one-dimensional cellular automata is considered. Many codes are given and some examples are practically realized. The obtained results are graphically represented.
In Section 7.5 the one-dimensional chaotic maps to see how we might use them to generate a random sequence is investigated. In particular the logistic map is considered.
In Section 7.6 it is considered an experiment which answer to the question: can we use random numbers to evolve a random number generator? The basic algorithm that generates a random sequence but instead of a random sequence of numbers it is a random sequence of programs. The tenuous nature of this association and proceed nonetheless is freely admited. This chapter finishes with exercises, connected with the considered problems.

MSC:

65-02 Research exposition (monographs, survey articles) pertaining to numerical analysis
65C10 Random number generation in numerical analysis
60C05 Combinatorial probability
62F03 Parametric hypothesis testing
68-02 Research exposition (monographs, survey articles) pertaining to computer science
68W40 Analysis of algorithms
11K45 Pseudo-random numbers; Monte Carlo methods
94A60 Cryptography
PDFBibTeX XMLCite
Full Text: DOI