126 RANDOM NUMBERS 3.4.1 Fig. 13. Region of
126 RANDOM NUMBERS 3.4.1 Fig. 13. Region of acceptance in the ratio -of -uniforms method for normal deviates. Lengths of lines with coor- dinate ratio x have the normal distribu- tion. - (0, - 42/e) Exercises 20 and 21 work out the timing analysis; four different algorithms are analyzed, since steps R2 and R3 can be included or omitted depending on one s preference. The following table shows how many times each step will be performed, on the average, depending on which of the optional tests is applied: Step Neither R2 only R3 only Both Rl 1.369 1.369 1.369 1.369 R2 0 1.369 0 1.369 (25) R3 0 0 1.369 0.467 R4 1.369 0.467 1.134 0.232 Thus it pays to omit the optional tests if there is a very fast logarithm operation, but if the log routine is rather slow it pays to include them. But why does it work? One reason is that we can calculate the probability that X < Z, and it turns out to be the correct value (10). But such a calculation isn t very easy unless one happens to hit on the right trick, and anyway it is better to understand how the algorithm might have been discovered in the first place. Kinderman and Monahan derived it by working out the following theory that can be used with any well-behaved density function f(x) [cf. ACM Trans. Math. Software 3 (1977), 257-2601. In general, suppose that a point (U, V) has been generated uniformly over the region of the (u, v)-plane defined by