c7-4 (779518)
Текст из файла
296Chapter 7.Random Numbers}if (p != pp) bnl=n-bnl;return bnl;Remember to undo the symmetry transformation.}See Devroye [2] and Bratley [3] for many additional algorithms.CITED REFERENCES AND FURTHER READING:Knuth, D.E. 1981, Seminumerical Algorithms, 2nd ed., vol. 2 of The Art of Computer Programming(Reading, MA: Addison-Wesley), pp. 120ff.
[1]Devroye, L. 1986, Non-Uniform Random Variate Generation (New York: Springer-Verlag), §X.4.[2]Bratley, P., Fox, B.L., and Schrage, E.L. 1983, A Guide to Simulation (New York: SpringerVerlag). [3].7.4 Generation of Random BitsThe C language gives you useful access to some machine-level bitwise operationssuch as << (left shift). This section will show you how to put such abilities to good use.The problem is how to generate single random bits, with 0 and 1 equallyprobable. Of course you can just generate uniform random deviates between zeroand one and use their high-order bit (i.e., test if they are greater than or less than0.5).
However this takes a lot of arithmetic; there are special-purpose applications,such as real-time signal processing, where you want to generate bits very muchfaster than that.One method for generating random bits, with two variant implementations, isbased on “primitive polynomials modulo 2.” The theory of these polynomials isbeyond our scope (although §7.7 and §20.3 will give you small tastes of it). Here,Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.
Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).if (n != nold) {If n has changed, then compute useful quantien=n;ties.oldg=gammln(en+1.0);nold=n;} if (p != pold) {If p has changed, then compute useful quantipc=1.0-p;ties.plog=log(p);pclog=log(pc);pold=p;}sq=sqrt(2.0*am*pc);The following code should by now seem familiar:do {rejection method with a Lorentzian compardo {ison function.angle=PI*ran1(idum);y=tan(angle);em=sq*y+am;} while (em < 0.0 || em >= (en+1.0));Reject.em=floor(em);Trick for integer-valued distribution.t=1.2*sq*(1.0+y*y)*exp(oldg-gammln(em+1.0)-gammln(en-em+1.0)+em*plog+(en-em)*pclog);} while (ran1(idum) > t);Reject.
This happens about 1.5 times per devibnl=em;ate, on average.7.4 Generation of Random Bits297suffice it to say that there are special polynomials among those whose coefficientsare zero or one. An example isx18 + x5 + x2 + x1 + x0(7.4.1)(18, 5, 2, 1, 0)Every primitive polynomial modulo 2 of order n (=18 above) defines arecurrence relation for obtaining a new random bit from the n preceding ones. Therecurrence 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 2n − 1 random bits before the sequence repeats.Let the bits be numbered from 1 (most recently generated) through n (generatedn steps ago), and denoted a1 , a2 , .
. . , an . We want to give a formula for a new bita0 . After generating a0 we will shift all the bits by one, so that the old an is finallylost, 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 singleshift 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 isa0 = 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 eachnonzero 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 thelast term might or might not be a1 , depending on whether the primitive polynomialhas a term in x1 .While it is simple in hardware, Method I is somewhat cumbersome in C, becausethe 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 ismodified for the next call).{unsigned long newbit;The accumulated XOR’s.newbit = (*iseed >> 17) & 1^ (*iseed >> 4) & 1^ (*iseed >> 1) & 1^ (*iseed & 1);*iseed=(*iseed << 1) | newbit;return (int) newbit;}Get bit 18.XOR with bit 5.XOR with bit 2.XOR with bit 1.Leftshift the seed and put the result of theXOR’s in its bit 1.Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.
Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).which we can abbreviate by just writing the nonzero powers of x, e.g.,298Chapter 7.181754Random Numbers3210shift left1817543210shift left(b)Figure 7.4.1.Two related methods for obtaining random bits from a shift register and a primitivepolynomial modulo 2.
(a) The contents of selected taps are combined by exclusive-or (addition modulo2), 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 stillpossible), but is beautifully suited to C.
It modifies more than one bit among thesaved n bits as each new bit is generated (Figure 7.4.1). It generates the maximallength sequence, but not in the same order as Method I. The prescription for theprimitive polynomial (7.4.1) is:a0 = a18a5 = a5 ∧ a0a2 = a2 ∧ a0(7.4.3)a1 = a1 ∧ a0In general there will be an exclusive-or for each nonzero term in the primitivepolynomial except 0 and n.
The nice feature about Method II is that all theexclusive-or’s can usually be done as a single full-word exclusive-or operation:#define#define#define#define#defineIB1 1IB2 2IB5 16IB18 131072MASK (IB1+IB2+IB5)Powers of 2.int irbit2(unsigned long *iseed)Returns as an integer a random bit, based on the 18 low-significance bits in iseed (which ismodified 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.Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited.
To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).(a)2997.4 Generation of Random Bits*iseed <<= 1;return 0;}}Some Primitive Polynomials Modulo 2 (after Watson)0)1,1,1,2,1,1,4,4,3,2,6,4,5,1,5,3,5,5,3,2,1,5,4,3,6,5,3,2,6,3,7,6,7,2,6,5,6,4,5,3,5,6,6,4,8,5,7,6,4,0)0)0)0)0)0)3,0)0)0)4,3,3,0)3,0)2,2,0)0)0)0)3,0)2,2,0)0)4,0)5,4,6,0)5,4,5,0)40)4,4,5,3,5,0)5,5,3,2, 0)1, 0)1, 0)1, 0)2, 0)1, 0)1, 0)1, 0)1, 0)1, 0)1, 0)3, 2, 1, 0)1, 0)5, 2, 1, 0)4, 2, 1, 0)3, 2, 1, 0)1, 0)3, 0)3,3,2,1,3,2, 1, 0)0)0)0)2, 1, 0)4, 2, 1, 0)4, 0)2, 0)(51,(52,(53,(54,(55,(56,(57,(58,(59,(60,(61,(62,(63,(64,(65,(66,(67,(68,(69,(70,(71,(72,(73,(74,(75,(76,(77,(78,(79,(80,(81,(82,(83,(84,(85,(86,(87,(88,(89,(90,(91,(92,(93,(94,(95,(96,(97,(98,(99,(100,6, 3,3, 0)6, 2,6, 5,6, 2,7, 4,5, 3,6, 5,6, 5,1, 0)5, 2,6, 5,1, 0)4, 3,4, 3,8, 6,5, 2,7, 5,6, 5,5, 3,5, 3,6, 4,4, 3,7, 4,6, 3,5, 4,6, 5,7, 2,4, 3,7, 5,4 0)8, 7,7, 4,8, 7,8, 2,6, 5,7, 5,8, 5,6, 5,5, 3,7, 6,6, 5,2, 0)6, 5,6, 5,7, 6,6, 0)7, 4,7, 5,8, 7,1, 0)1,4,1,2,2,1,4,0)3, 2, 0)0)0)0)0)3, 1, 0)1, 0)3, 0)1,1,5,1,1,2,1,1,3,2,3,1,2,2,1,2,3,0)0)3, 2, 0)0)0)0)0)0)2, 1, 0)0)0)0)0)0)0)0)2, 1, 0)6,2,5,1,2,1,4,3,2,5,2,4,0)3,0)0)0)3,0)0)3,0)1, 0)1, 0)1, 0)2, 0)1, 0)4, 2, 1, 0)4, 3, 2, 0)3, 2, 1, 0)4, 0)2, 0)A word of caution is: Don’t use sequential bits from these routines as the bitsof a large, supposedly random, integer, or as the bits in the mantissa of a supposedlySample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.
Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).(1,(2,(3,(4,(5,(6,(7,(8,(9,(10,(11,(12,(13,(14,(15,(16,(17,(18,(19,(20,(21,(22,(23,(24,(25,(26,(27,(28,(29,(30,(31,(32,(33,(34,(35,(36,(37,(38,(39,(40,(41,(42,(43,(44,(45,(46,(47,(48,(49,(50,300Chapter 7.Random NumbersCITED REFERENCES AND FURTHER READING:Knuth, D.E.
1981, Seminumerical Algorithms, 2nd ed., vol. 2 of The Art of Computer Programming(Reading, MA: Addison-Wesley), pp. 29ff. [1]Horowitz, P., and Hill, W. 1989, The Art of Electronics, 2nd ed. (Cambridge: Cambridge UniversityPress), §§9.32–9.37.Tausworthe, R.C. 1965, Mathematics of Computation, vol. 19, pp. 201–209.Watson, E.J. 1962, Mathematics of Computation, vol. 16, pp. 368–369. [2]7.5 Random Sequences Based on DataEncryptionIn Numerical Recipes’ first edition,we described how to use the Data Encryption Standard(DES) [1-3] for the generation of random numbers. Unfortunately, when implemented insoftware in a high-level language like C, DES is very slow, so excruciatingly slow, in fact, thatour previous implementation can be viewed as more mischievous than useful.
Here we givea much faster and simpler algorithm which, though it may not be secure in the cryptographicsense, generates about equally good random numbers.DES, like its progenitor cryptographic system LUCIFER, is a so-called “block productcipher” [4]. It acts on 64 bits of input by iteratively applying (16 times, in fact) a kind of highlynonlinear bit-mixing function. Figure 7.5.1 shows the flow of information in DES duringthis mixing.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
