7.7 Quasi-(that is,Sub-)Random Sequences 311 Degree Primitive Polynomials Modulo 2* 0(i.e.,x+1) 2 1(i.e,x2+x+1) 3 l,2(.e,x3+x+1andx3+x2+1) 1,4(i.e,x4+x+1andx4+x3+1) 2,4,711,13,14 6 1,13,16.19,22,25 1,4.7,8.14,19,21,28.31,32,37,41,42,50,55,56.59,62 8 14,21,22,38,47,49,50,52,56,67,70,84,97,103,115,122 (including this one) 9 8,13.16,22,25,44,47,52,55,59,62,67,7481,82,87,91,94,103,104,109,122 124.137,138,143,145,152,157,167,173,176,181,182.,185,191,194.199,218,220 11-800872 227,229,230,234,236,241,244,253 from NUMERICAL RECIPES IN 公 4,13,19.22,50,55,64,69,98.107,115.121,127,134.140,145,152,158.161,171 (North 181,194,199,203,208,227,242,251,253,265,266,274,283,289,295,301,316 319,324,346.352,361,367,382,395,398,400,412,419,422,426,428.433.446 America computer, 1988-1992 by Cambridge University Press. THE 454,457,472,493.505,508 ART *Expressed as a decimal integer representing the interior bits (that is,omitting the Programs high-order bit and the unit bit). The Sobol'sequence generates numbers between zero and one directly as binary fractions of length w bits,from a set of w special binary fractions,V.i=1.2.....w,called direction numbers.In Sobol's original method,the ith number X;is generated by XORing (bitwise exclusive or)together the set ofVi's satisfying the criterion on i,"the ith bit ofj is nonzero." As j increments,in other words,different ones of the Vi's flash in and out of X;on different time scales.Vi alternates between being present and absent most quickly,while V goes from present to absent(or vice versa)only every 2-1 steps. Antonov and Saleev's contribution was to show that instead of using the bits of the 10-521 integer j to select direction numbers,one could just as well use the bits of the Gray code of j,G(j).(For a quick review of Gray codes,look at $20.2.) Fuurggoglrion 43108 Now G(j)and G(j+1)differ in exactly one bit position,namely in the position of the Numerical Recipes rightmost zero bit in the binary representation ofj(adding a leading zero to j if necessary).A consequence is that thej+1st Sobol'-Antonov-Saleev number can be obtained from the jth (outside by XORing it with a single Vi,namely with i the position of the rightmost zero bit in j.This North Software. makes the calculation of the sequence very efficient,as we shall see. Figure 7.7.1 plots the first 1024 points generated by a two-dimensional Sobol'sequence. One sees that successive points do"know"about the gaps left previously,and keep filling them in,hierarchically. We have deferred to this point a discussion ofhow the direction numbers Vi are generated. Some nontrivial mathematics is involved in that,so we will content ourself with a cookbook summary only:Each different Sobol'sequence(or component of an n-dimensional sequence) is based on a different primitive polynomial over the integers modulo 2,that is,a polynomial whose coefficients are either 0 or 1,and which generates a maximal length shift register sequence.(Primitive polynomials modulo 2 were used in 87.4,and are further discussed in $20.3.)Suppose P is such a polynomial,of degree g, P=x9+a1x9-1+a2x9-2+…+ag-1x+1 (7.7.1)7.7 Quasi- (that is, Sub-) Random Sequences 311 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). Degree Primitive Polynomials Modulo 2* 1 0 (i.e., x + 1) 2 1 (i.e., x2 + x + 1) 3 1, 2 (i.e., x3 + x + 1 and x3 + x2 + 1) 4 1, 4 (i.e., x4 + x + 1 and x4 + x3 + 1) 5 2, 4, 7, 11, 13, 14 6 1, 13, 16, 19, 22, 25 7 1, 4, 7, 8, 14, 19, 21, 28, 31, 32, 37, 41, 42, 50, 55, 56, 59, 62 8 14, 21, 22, 38, 47, 49, 50, 52, 56, 67, 70, 84, 97, 103, 115, 122 9 8, 13, 16, 22, 25, 44, 47, 52, 55, 59, 62, 67, 74, 81, 82, 87, 91, 94, 103, 104, 109, 122, 124, 137, 138, 143, 145, 152, 157, 167, 173, 176, 181, 182, 185, 191, 194, 199, 218, 220, 227, 229, 230, 234, 236, 241, 244, 253 10 4, 13, 19, 22, 50, 55, 64, 69, 98, 107, 115, 121, 127, 134, 140, 145, 152, 158, 161, 171, 181, 194, 199, 203, 208, 227, 242, 251, 253, 265, 266, 274, 283, 289, 295, 301, 316, 319, 324, 346, 352, 361, 367, 382, 395, 398, 400, 412, 419, 422, 426, 428, 433, 446, 454, 457, 472, 493, 505, 508 *Expressed as a decimal integer representing the interior bits (that is, omitting the high-order bit and the unit bit). The Sobol’sequence generates numbers between zero and one directly as binary fractions of length w bits, from a set of w special binary fractions, Vi, i = 1, 2,...,w, called direction numbers. In Sobol’s original method, the jth number Xj is generated by XORing (bitwise exclusive or) together the set of Vi’s satisfying the criterion on i, “the ith bit of j is nonzero.” As j increments, in other words, different ones of the Vi’s flash in and out of Xj on different time scales. V1 alternates between being present and absent most quickly, while Vk goes from present to absent (or vice versa) only every 2k−1 steps. Antonov and Saleev’s contribution was to show that instead of using the bits of the integer j to select direction numbers, one could just as well use the bits of the Gray code of j, G(j). (For a quick review of Gray codes, look at §20.2.) Now G(j) and G(j + 1) differ in exactly one bit position, namely in the position of the rightmost zero bit in the binary representation of j (adding a leading zero to j if necessary). A consequence is that the j + 1st Sobol’-Antonov-Saleev number can be obtained from the jth by XORing it with a single Vi, namely with i the position of the rightmost zero bit in j. This makes the calculation of the sequence very efficient, as we shall see. Figure 7.7.1 plots the first 1024 points generated by a two-dimensional Sobol’ sequence. One sees that successive points do “know” about the gaps left previously, and keep filling them in, hierarchically. We have deferred to this point a discussion of how the direction numbers Vi are generated. Some nontrivial mathematics is involved in that, so we will content ourself with a cookbook summary only: Each different Sobol’ sequence (or component of an n-dimensional sequence) is based on a different primitive polynomial over the integers modulo 2, that is, a polynomial whose coefficients are either 0 or 1, and which generates a maximal length shift register sequence. (Primitive polynomials modulo 2 were used in §7.4, and are further discussed in §20.3.) Suppose P is such a polynomial, of degree q, P = xq + a1xq−1 + a2xq−2 + ··· + aq−1x +1 (7.7.1)