next up previous

5 Vectorization and Access via Multiple Processors: LCGs     continued...

Suppose we know in advance that we will have N independent processes and that we will need N independent streams of random numbers. Then the best strategy for using an LCG is to split its period into nonoverlapping segments, each of which will be accessed by a different process. This amounts to finding N seeds which are known to be far apart on the cycle produced by the LCG. To find such seeds, first consider (for c = 0), the LCG rule successively applied:

Thus we can ``leap ahead'' k places of the period by multiplying the current seed value by mod m. For our purposes, we would like N starting seeds, spaced at roughly steps apart. Since k is likely to be quite large, it is not practical to compute one step at a time. Instead we compute an -long array, , the power-of-two powers of a:

where is the largest power-of-two power of a that is still smaller than k. I.e. L is the integer part of the log (base 2) of a. For example, assume that (very small, but big enough to show how it works). Then

and since 91 = 64 + 16 + 8 + 2 + 1, then