310 Chapter 7. Random Numbers .8 6 .6 .4 .4 2 83 旦 granted for 19881992 0 0 0 .2 4 .6 8 0 .2 .4 .6 8 11800 points I to 128 points 129 to 512 1T, Cambridge University Press. users to make one paper from NUMERICAL RECIPES IN C: f 8 server computer, (North America THE 6 .4C Programs 2 2 email strictly prohibited. Copyright (C) 0 to dir 0 .2 .4 .6 .8 1 0 .6 ART OF SCIENTIFIC COMPUTING(ISBN points 513 to 1024 points 1 to 1024 1881992 Figure 7.7.1.First 1024 points of a two-dimensional Sobol'sequence.The sequence is generated number-theoretically,rather than randomly,so successive points at any stage "know"how to fill in the gaps in the previously generated distribution. Numerical Recipes 10-521 43108 the sequence.(In the example,we get 0.221 base 3.)The result is Hj.To get a sequence of n-tuples in n-space,you make each component a Halton sequence with a different prime base b.Typically,the first n primes are used. (outside It is not hard to see how Halton's sequence works:Every time the number of North Software. digits in j increases by one place,j's digit-reversed fraction becomes a factor of b finer-meshed.Thus the process is one of filling in all the points on a sequence of finer and finer Cartesian grids-and in a kind of maximally spread-out order visit website on each grid (since,e.g.,the most rapidly changing digit in i controls the most machine significant digit of the fraction). Other ways of generating quasi-random sequences have been suggested by Faure,Sobol',Niederreiter,and others.Bratley and Fox [2]provide a good review and references,and discuss a particularly efficient variant of the Sobol'[3]sequence suggested by Antonov and Saleev[41.It is this Antonov-Saleev variant whose implementation we now discuss.310 Chapter 7. Random Numbers Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machine￾readable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). . . . . . . . . .. . . . . . . . . . . . . . . . . .. . . . . .. . . . . . . . . . . . . . . . . .. . . . . . . . . . .. . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . 0 .2 .4 .6 .8 1 points 1 to 128 0 .2 .4 .6 .8 1 . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . ... .. . . .. . . . . .. . . . . . . . . . . . . . . . ... .. .. . . . . .. .. . . . .. . . . .. . . . . . .. . . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . .... .. .. .. .. .. ... ... ... . .. . .. .... . .. .. . .. . .. . . .. . . .. ... . . ..... . . . . . ... .. .. . ... .. .. ... . . . . .. .... . . . . . ... . . . . .. . . . . ... .. . . . .. .. .. .. .. .... .. . . . .. . .. .... .. . . ......... . .. . .... .. .. ... ....... ... . . .. .. ... . ... . . . ..... .. .. ... . . . .. .. .. . .... .. ... . . .. . . . .. . .. .. . . ... .. 0 .2 .4 .6 .8 1 points 129 to 512 0 .2 .4 .6 .8 1 ... .. . .. . ...... .. . . ....... ...... ....... ..... . . ... .. ...... ......... .. . ...... .. . . . . .. .. . . .. ... .... .. ....... ... . . ... .. .. . . .. . .. ... . .. .. ..... .. .... . .... .... ... .. ... ...... .. .. .. ... . . . .. .. ........ .. ..... .. .. .... .. .... .. ... ... . . .. .. ..... .. .. ....... . ... . . . .. .. . . .. ... .. .. .. ..... ... . ... .. . . . . . . . ....... . . .. ..... ... . .... . .... .. .... .. ... ... .. ... .. ..... .. ... .. ... ... .. ... . ... ... ..... ... .. . . .. .. .. .. . ... . .. . . ... ... . ........ ...... ...... .... ... . ... . ... ... . ...... .. . ..... .... .... ..... .. . . .... . . . . . . 0 .2 .4 .6 .8 1 points 513 to 1024 0 .2 .4 .6 .8 1 ........ ... . .... ... . .... ..... . .. .. ........ ... . .. .. . .. ..... .. . ... ........ ...... . ... .. .. .... . .... .... . . . . ... . ... ... .. .. .. ...... .. .. ... ....... ... .. . ... ..... . .. . ... . .. .... ........ ... . .. .. .. . .. .. ... ......... .. ... ... . . . . .... . . ... ... ..... .. .. . . ..... . .. .. . . .. . ..... .. .. ... .... ....... . . ... .... . ..... .. .. ... ...... .... .. ... . ... . . ................ ... . ..... . ... .. .. .. . . . ..... .. ... .... ... ..... . ...... .. .. ....... .... . ... . . .... . . .. . .. .. . .. .. . ... . ... ... . .. ... .. ... . ....... .. . .... .. ..... . ..... .. . .... .... ... .. .. .. .. .... . ..... ... ...... . ..... ..... . .. . ... ..... . ... ... . .. ... . .. . .... .. .. ... ... . . .... .. ... . .. ..... .. . ... ....... ... ... . ........ . .. .... . .. .. .. .. .. ... ... ..... . .. .... . .. ... .... . .. .... . .... .. .. .. .. . .. .. .. . ... .. ... .. .. .. .. ... . .. . . .. ... . .. ... . .. .. . ....... . .... .. ........... ... . .. ... ... ... .. .. ... . .. . .. ....... . ....... ....... . ... . ... . . ... ..... .. .... ...... .. ... .. .. . . . . ... .. . ..... .... . ... .... . ...... ..... ... ... .. . .. .. .. .. ... .. .. ... ... . . . . .. . .. .. . ... . . .. . . . . . . . ... . .. .. . .. .. ....... ..... .... .. .. ..... ... .. .. 0 .2 .4 .6 .8 1 points 1 to 1024 0 .2 .4 .6 .8 1 Figure 7.7.1. First 1024 points of a two-dimensional Sobol’ sequence. The sequence is generated number-theoretically, rather than randomly, so successive points at any stage “know” how to fill in the gaps in the previously generated distribution. the sequence. (In the example, we get 0.221 base 3.) The result is Hj . To get a sequence of n-tuples in n-space, you make each component a Halton sequence with a different prime base b. Typically, the first n primes are used. It is not hard to see how Halton’s sequence works: Every time the number of digits in j increases by one place, j’s digit-reversed fraction becomes a factor of b finer-meshed. Thus the process is one of filling in all the points on a sequence of finer and finer Cartesian grids — and in a kind of maximally spread-out order on each grid (since, e.g., the most rapidly changing digit in j controls the most significant digit of the fraction). Other ways of generating quasi-random sequences have been suggested by Faure, Sobol’, Niederreiter, and others. Bratley and Fox [2] provide a good review and references, and discuss a particularly efficient variant of the Sobol’ [3] sequence suggested by Antonov and Saleev [4]. It is this Antonov-Saleev variant whose implementation we now discuss