10.3 Distributed Random Generators

The techniques described here for constructing distributed random   number generators are based on an adaptation of the linear congruential algorithm called the random tree method. We first show how this method can be applied to a single generator to construct a tree of generators in a deterministic and reproducible fashion. This facility is particularly valuable in computations that create and destroy tasks dynamically during program execution.

10.3.1 The Random Tree Method

The random tree method employs two linear congruential generators,   L and R , that differ only in the values used for   a .

 
Figure 10.1: The random tree method. Two generators are used to construct a tree of random numbers. The right generator is applied to elements of the sequence L generated by the left generator to generate new sequences R , R' , R'' , etc. 

  Application of the left generator L to a seed generates one random sequence; application of the right generator R to the same seed generates a different sequence. By applying the right generator to elements of the left generator's sequence (or vice versa), a tree of random numbers can be generated. By convention, the right generator R is used to generate random values for use in computation, while the left generator L is applied to values computed by R to obtain the starting points , , etc., for new right sequences (Figure 10.1).

The strength of the random tree method is that it can be used to   generate new random sequences in a reproducible and noncentralized fashion. This is valuable, for example, in applications in which new tasks and hence new random generators must be created dynamically. Before creating a new task, a parent task uses the left generator to construct a new right generator, which it passes to its new offspring. The new task uses this right generator to generate the random numbers required for its computation. If it in turn must generate a new task, it can apply the left generator to its latest random value to obtain a new random seed.

A deficiency of the random tree method as described here is that there is no guarantee that different right sequences will not overlap. The period of R is usually chosen to be near to m , because this maximizes the quality of the random numbers obtained by using the generator. Hence, the starting points returned by the left generator are likely to be different points in the same sequence, in which case we can think of L as selecting random starting points in the sequence constructed by R . If two starting points happen to be close to each other, the two right sequences that are generated will be highly correlated.

10.3.2 The Leapfrog Method

In some circumstances, we may know that a program requires a fixed number of generators. (For example, we may require one generator for   each task in a domain decomposition algorithm.) In this case, a   variant of the random tree method called the leapfrog method can be used to generate sequences that can be guaranteed not to overlap for a certain period.

Let n be the number of sequences required. Then we define and as a and , respectively, so that we have

Then, we create n different right generators .. by taking the first n elements of L as their starting values. The name ``leapfrog method'' refers to the fact that the i th sequence consists of and every n th subsequent element of the sequence generated by L (Figure 10.2). As this method partitions the elements of L , each subsequence has a period of at least P/n , where P is the period of L . (If n divides P , then the period of a subsequence is exactly P/n .) In addition, the n subsequences are disjoint for their first P/n elements.

 
Figure 10.2: The leapfrog method with n=3 . Each of the three right generators selects a disjoint subsequence of the sequence constructed by the left generator's sequence. 

The generator for the r th subsequence, , is defined by and . We can compute these values as follows. We first compute and ; these computations can be performed in time by taking advantage of the identity

We then compute members of the sequence as follows, to obtain n generators, each defined by a triple , for .

The leapfrog method can be applied recursively: the subsequence corresponding to a generator can be further subdivided by a second application of the leapfrog method. Doing this can be useful when random numbers are required at several levels in a task hierarchy. However, the periods of the resulting sequences become shorter, and their statistical properties are less certain.

10.3.3 Modified Leapfrog

In other situations, we may know the maximum number, n , of   random values needed in a subsequence but not the number of   subsequences required. In this case, a variant of the leapfrog method can be used in which the role of L and R are reversed so that the elements of subsequence i are the contiguous elements .. (Figure 10.3), as follows:

It is not a good idea to choose n as a power of two, as this can lead to serious long-term correlations.

 
Figure 10.3: Modified leapfrog with n=3 . Each subsequence contains three contiguous numbers from the main sequence.