7.4 Generation of Random Bits 297 suffice it to say that there are special polynomials among those whose coefficients are zero or one.An example is x18+x5+x2+x1+x0 (7.4.1) which we can abbreviate by just writing the nonzero powers of z,e.g., (18.5.2.1.0) Every primitive polynomial modulo 2 oforder n(=18 above)defines a recurrence relation for obtaining a new random bit from the n preceding ones.The recurrence relation is guaranteed to produce a sequence of maximal length,i.e.,cycle through all possible sequences of n bits (except all zeros)before it repeats.Therefore one can seed the sequence with any initial bit pattern (except all zeros),and get 2-1 random bits before the sequence repeats. Let the bits be numbered from I (most recently generated)through n(generated RECIPES I n steps ago),and denoted a1,a2,...,an.We want to give a formula for a new bit 令 ao.After generating ao we will shift all the bits by one,so that the old an is finally lost,and the new ao becomes a1.We then apply the formula again,and so on. "Method I"is the easiest to implement in hardware,requiring only a single shift register n bits long and a few XOR ("exclusive or"or bit addition mod 2) gates,the operation denoted in C by"A".For the primitive polynomial given above, the recurrence formula is R是。 a0=a18Aa5Aa2八a1 (7.4.2) The terms that are A'd together can be thought of as "taps"on the shift register, A'd into the register's input.More generally,there is precisely one term for each nonzero coefficient in the primitive polynomial except the constant(zero bit)term. So the first term will always be an for a primitive polynomial of degree n,while the last term might or might not be a1,depending on whether the primitive polynomial has a term in xI Numerica 10621 While it is simple in hardware,Method I is somewhat cumbersome in C,because 431 the individual bits must be collected by a sequence of full-word masks: Recipes int irbit1(unsigned long *iseed) Returns as an integer a random bit,based on the 18 low-significance bits in iseed (which is Software. 首 modified for the next call). f unsigned long newbit; The accumulated XOR's. newbit =(*iseed >17)&1 Get bit 18. ·(*iseed>>4)&1 XOR with bit 5. (*1seed>>1)21 XOR with bit 2. ·(*iseed&1); XOR with bit 1. *iseed-(*iseed <1)I newbit; Leftshift the seed and put the result of the return (int)newbit; XOR's in its bit 1.7.4 Generation of Random Bits 297 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). suffice it to say that there are special polynomials among those whose coefficients are zero or one. An example is x18 + x5 + x2 + x1 + x0 (7.4.1) which we can abbreviate by just writing the nonzero powers of x, e.g., (18, 5, 2, 1, 0) Every primitive polynomial modulo 2 of ordern (=18 above) defines a recurrence relation for obtaining a new random bit from the n preceding ones. The recurrence relation is guaranteed to produce a sequence of maximal length, i.e., cycle through all possible sequences of n bits (except all zeros) before it repeats. Therefore one can seed the sequence with any initial bit pattern (except all zeros), and get 2 n − 1 random bits before the sequence repeats. Let the bits be numbered from 1 (most recently generated) through n (generated n steps ago), and denoted a1, a2,...,an. We want to give a formula for a new bit a0. After generating a0 we will shift all the bits by one, so that the old an is finally lost, and the new a0 becomes a1. We then apply the formula again, and so on. “Method I” is the easiest to implement in hardware, requiring only a single shift register n bits long and a few XOR (“exclusive or” or bit addition mod 2) gates, the operation denoted in C by “∧”. For the primitive polynomial given above, the recurrence formula is a0 = a18 ∧ a5 ∧ a2 ∧ a1 (7.4.2) The terms that are ∧’d together can be thought of as “taps” on the shift register, ∧’d into the register’s input. More generally, there is precisely one term for each nonzero coefficient in the primitive polynomial except the constant (zero bit) term. So the first term will always be an for a primitive polynomial of degree n, while the last term might or might not be a1, depending on whether the primitive polynomial has a term in x1. While it is simple in hardware, Method I is somewhat cumbersome in C, because the individual bits must be collected by a sequence of full-word masks: int irbit1(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). { unsigned long newbit; The accumulated XOR’s. newbit = (*iseed >> 17) & 1 Get bit 18. ^ (*iseed >> 4) & 1 XOR with bit 5. ^ (*iseed >> 1) & 1 XOR with bit 2. ^ (*iseed & 1); XOR with bit 1. *iseed=(*iseed << 1) | newbit; Leftshift the seed and put the result of the return (int) newbit; XOR’s in its bit 1. }