298 Chapter 7.Random Numbers 1817 5 4 0 shift left (a) 1817 0 shift left http://www.nr. 83 granted for 11-800 from NUMERICAL RECIPES IN 19881992 9 (b) Figure 7.4.1.Two related methods for obtaining random bits from a shift register and a primitive polynomial modulo 2.(a)The contents of selected taps are combined by exclusive-or (addition modulo server 2),and the result is shifted in from the right.This method is easiest to implement in hardware.(b) (Nort to make Selected bits are modified by exclusive-or with the leftmost bit,which is then shifted in from the right This method is easiest to implement in software. America computer, THE ART "Method II"is less suited to direct hardware implementation (though still possible),but is beautifully suited to C.It modifies more than one bit among the 9 Program saved n bits as each new bit is generated(Figure 7.4.1).It generates the maximal length sequence,but not in the same order as Method I.The prescription for the primitive polynomial(7.4.1)is: a0=a18 a5a5 Aao OF SCIENTIFIC COMPUTING(ISBN (7.4.3) 1920 a2 a2 A ao a1=a1Λa0 In general there will be an exclusive-or for each nonzero term in the primitive idge.org Numerical Recipes 10.621 43106 polynomial except 0 and n.The nice feature about Method II is that all the exclusive-or's can usually be done as a single full-word exclusive-or operation: (outside Software. #define IB1 1 Powers of 2. #define IB2 2 #define IB5 16 #define IB18 131072 #define MASK (IB1+IB2+IB5) int irbit2(unsigned long *iseed) Returns as an integer a random bit,based on the 18 low-significance bits in iseed (which is modified for the next call). if(*iseed盘IB18){ Change all masked bits,shift,and put 1 into bit 1. *iseed=((*iseed MASK)<<1)I IB1; return 1; else Shift and put 0 into bit 1.298 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). 18 17 5 4 3 2 1 0 shift left (a) 18 17 5 4 3 2 1 0 shift left (b) Figure 7.4.1. Two related methods for obtaining random bits from a shift register and a primitive polynomial modulo 2. (a) The contents of selected taps are combined by exclusive-or (addition modulo 2), and the result is shifted in from the right. This method is easiest to implement in hardware. (b) Selected bits are modified by exclusive-or with the leftmost bit, which is then shifted in from the right. This method is easiest to implement in software. “Method II” is less suited to direct hardware implementation (though still possible), but is beautifully suited to C. It modifies more than one bit among the saved n bits as each new bit is generated (Figure 7.4.1). It generates the maximal length sequence, but not in the same order as Method I. The prescription for the primitive polynomial (7.4.1) is: a0 = a18 a5 = a5 ∧ a0 a2 = a2 ∧ a0 a1 = a1 ∧ a0 (7.4.3) In general there will be an exclusive-or for each nonzero term in the primitive polynomial except 0 and n. The nice feature about Method II is that all the exclusive-or’s can usually be done as a single full-word exclusive-or operation: #define IB1 1 Powers of 2. #define IB2 2 #define IB5 16 #define IB18 131072 #define MASK (IB1+IB2+IB5) int irbit2(unsigned long *iseed) Returns as an integer a random bit, based on the 18 low-significance bits in iseed (which is modified for the next call). { if (*iseed & IB18) { Change all masked bits, shift, and put 1 into bit 1. *iseed=((*iseed ^ MASK) << 1) | IB1; return 1; } else { Shift and put 0 into bit 1