📄 randomnumbersin c_bygeorgemarsaglia_etc.htm
字号:
<HTML><HEAD><TITLE>Random Numbers in C</TITLE><META NAME = "DESCRIPTION" CONTENT = "A whole set of tested 'one liner' randomnumber generators in C.A Ciphers By Ritter page."><META NAME = "KEYWORDS" CONTENT = "random,number,generator,pseuodorandom,software,C"></HEAD><BODY><H1 ALIGN=CENTER>Random Numbers in C</H1><BR><H2 ALIGN = CENTER>A<A HREF = "http://www.ciphersbyritter.com/"><I>Ciphers By Ritter</I></A> Page</H2><BR><P>Random number generators (<I>pseudo-</I>random, of course) in C;mostly fast one-liners for "inline" use (to eliminate call / returnoverhead). If you just want to <I>use</I> these RNG's, it might bea good idea to start at the last message.<P><HR><H3>Contents</H3><UL><LI><A HREF = "#369B5E30.65A55FD1@stat.fsu.edu">1999-01-12 George Marsaglia:</A> "This posting ends with 17 lines of C code that provide eight different in-line random number generators, six for random 32-bit integers and two for uniform reals in (0,1) and (-1,1)."<LI><A HREF = "#369B66AB.6CDED9F8@ix.netcom.com">1999-01-12 Charles Bond:</A> "Do you know if any theoretical work has been done since Knuth's book to justify SWB?"<LI><A HREF = "#369B9AE9.52C98810@stat.fsu.edu">1999-01-12 George Marsaglia:</A> "It hasn't been very many years since I invented the subtract-with-borrow method, and developed theory for establishing the periods."<LI><A HREF = "#369BE439.92E0E011@ix.netcom.com">1999-01-12 Charles Bond:</A> "I did not mean to imply that Knuth's subtractive generator was *the same* as your subtract with borrow, only that it was *similar* (high speed, no multiplications)."<LI><A HREF = "#369BE0A2.CA197F7B@math.ucla.edu">1999-01-12 Mike Oliver:</A> "Could you give us a pointer to information about why these RNGs [lagged Fibonacci generators using xor] are unsatisfactory and what sort of test they tend to fail?"<LI><A HREF = "#tun23mnctq.fsf@labejb.lsid.hp.com">1999-01-13 Eric Backus:</A> "I have a small problem with the definition of LFIB4 and SWB. In an attempt to make these a single line of C code, they both use "++c" in the same expression as they use "c". A C compiler is free to rearrange the order in which it calculates the intermediate terms of these expressions, so the expressions can produce different results depending on the compiler."<LI><A HREF = "#369F6FCA.74C7C041@stat.fsu.edu">1999-01-15 George Marsaglia:</A> "The generators MWC, KISS, LFIB4 and SWB seem to pass all tests. By themselves, CONG and SHR3 do not, but using CONG+SHR3 provides one of the fastest combinations that satisfy the DIEHARD battery of tests."<LI><A HREF = "#790f49x60.fsf@poole.statgen.ncsu.edu">1999-01-15 Dmitri Zaykin:</A> "Shouldn't these be...."<LI><A HREF = "#99Jan15.151547edt.785@neuron.ai.toronto.edu">1999-01-01 Radford Neal:</A> "This doesn't work either."<LI><A HREF = "#QfQn2.10695$bf6.2024@news1.giganews.com">1999-01-15 Jeff Stout:</A> "The preprocessor is just doing a stupid text substituation, its the C compiler that is ambigous about the interpretation."<LI><A HREF = "#99Jan15.233424edt.6005@cortex.ai.toronto.edu">1999-01-01 Radford Neal:</A> "...although one can indeed create lots of junk using the C pre-processor, one cannot, in general, use it to create in-line procedures."<LI><A HREF = "#7ogny6htm.fsf@poole.statgen.ncsu.edu">1999-01-16 Dmitri Zaykin:</A> "It is probably true that the posted random number generators are better implemented as regular functions."<LI><A HREF = "#7pv8f55tf.fsf@poole.statgen.ncsu.edu">1999-01-16 Dmitri Zaykin:</A> "These should work...."<LI><A HREF = "#36A21A2C.AD5145D1@concentric.net">1999-01-17 Ramin Sina:</A> "Could someone please post a short example code on how to use these in practice."<LI><A HREF = "#77vrbs$pmj$1@sun500.nas.nasa.gov">1999-01-18 Ed Hook:</A> "No -- 'SHR3' and 'LFIB4' are OK, but your version of 'SWB' still invokes the dreaded undefined behavior."<LI><A HREF = "#78207l$1l8$1@due.unit.no">1999-01-19 Orjan Johansen:</A> "Surely in an expression of the form y=..., the evaluation of ... is guaranteed to happen before the assignment."<LI><A HREF = "#36a4cb5e.39101741@news.snafu.de">1999-01-19 Horst Kraemer:</A> "Sorry. No sequence point is needed between reading an writing to an lvalue."<LI><A HREF = "#77t9ot$15ha@b.stat.purdue.edu">1999-01-17 Herman Rubin:</A> "I think it should be clarified, and probably written out in some more detail. But the procedure call overhead would be comparable to the computing cost...."<LI><A HREF = "#36a23371.10418803@newshost.uwo.ca">1999-01-17 Duncan Murdoch:</A> "I don't know if that's true or not, but I don't think it is really something to worry about."<LI><A HREF = "#77veih$11ts@b.stat.purdue.edu">1999-01-18 Herman Rubin:</A> "It certainly is. The cost of one procedure call could far exceed the cost of a uniform, or even many nonuniform, random variables."<LI><A HREF = "#99Jan18.133644edt.6004@cortex.ai.toronto.edu">1999-01-01 Radford Neal:</A> "Even on a CISC machine like a VAX, I doubt the C procedure call overhead would be more that twice the time for the actual work, and on modern RISC machines the ratio will tend to be less."<LI><A HREF = "#78284m$m0e@b.stat.purdue.edu">1999-01-19 Herman Rubin:</A> "The code discussed was not in making a call for an array, but for a single step in the generation procedure."<LI><A HREF = "#36a5f74f.11285673@newshost.uwo.ca">1999-01-19 Duncan Murdoch:</A> "I'm not sure what you have in mind."<LI><A HREF = "#782bon$qjg@b.stat.purdue.edu">1999-01-19 Herman Rubin:</A> "Can we afford range checking?" "Basic random tools should be as a bit stream, not as floating numbers, for many reasons."<LI><A HREF = "#36a63ccd.18681450@newshost.uwo.ca">1999-01-20 Duncan Murdoch:</A> "...all languages that I know (including C) provide ways of forcing the order of evaluation: just put the things that need to be done first in an earlier statement."<LI><A HREF = "#cUwZzZKf1ety-pn2-vB2YCWNn5fgR@mfs-pci-bqh-vty163.as.wcom.net">1999-01-17 David W. Noon:</A> "I don't mind translating all this stuff into assembler, but anybody not using an Intel 80486 or better running a 32-bit version of OS/2 will not be able to use my code."<LI><A HREF = "#5tFXN12Xwb3.7WA43126hM3916@statgen.ncsu.edu">1999-01-18 Dmitri Zaykin:</A> "Another option is to re-write macros as C++ member functions."<LI><A HREF = "#cUwZzZKf1ety-pn2-NxnsgFONxOGO@localhost">1999-01-18 David W. Noon:</A> "The problem with C++ is that VMT calling mechanisms are almost invariably slower than the calling mechanisms used by C, PL/I, FORTRAN, Pascal, etc."<LI><A HREF = "#7sod842aa.fsf@poole.statgen.ncsu.edu">1999-01-18 Dmitri Zaykin:</A> "Well, in this particular case all that does not apply, since there are no virtual functions in the code."<LI><A HREF = "#36a3fc77.12606540@newshost.uwo.ca">1999-01-19 Duncan Murdoch:</A> "...but just as with any other aspect of the program, speed isn't as important as correctness."<LI><A HREF = "#7sod5s6d4.fsf@poole.statgen.ncsu.edu">1999-01-20 Dmitri Zaykin:</A> "To check if C-macros for these random number generators do indeed always produce faster, and maybe 'less bloated' code than inlined C++ member functions, I did a little experiment...."<LI><A HREF = "#124123g26m11754.1356cjx442854@statgen.ncsu.edu">1999-01-21 Dmitri Zaykin:</A><LI><A HREF = "#slrn7aeqsa.bkc.davis@aluche.mit.edu">1999-01-21 John E. Davis:</A> "Using your code (t.cc and t.c), my conclusion is the opposite...."<LI><A HREF = "#7btjsuxvo.fsf@poole.statgen.ncsu.edu">1999-01-21 Dmitri Zaykin:</A> "I used egcs-1.1.1 compiler. It is is an improvement over gcc-2.8.1."<LI><A HREF = "#780843$ikj$1@relay1.dsccc.com">1999-01-18 Mike McCarty:</A><LI><A HREF = "#780jh1$11ii@odds.stat.purdue.edu">1999-01-18 Herman Rubin:</A> "Decent random number code cannot be portable."<LI><A HREF = "#cUwZzZKf1ety-pn2-deRYWonQPOXL@localhost">1999-01-19 David W. Noon:</A> "I meant portable across software platforms, not hardware."<LI><A HREF = "#783bio$12vk@odds.stat.purdue.edu">1999-01-19 Herman Rubin:</A> "It is by no means clear that HLL generated code will do this, as the machine instructions involved are different." "What was meant was the distance to the next one in a stream of random bits. In other words, generate a geometric (.5) random variable using only the number of bits required by information."<LI><A HREF = "#cUwZzZKf1ety-pn2-FJ7g8dchLbd1@localhost">1999-01-19 David W. Noon:</A> "C++ just isn't ideally suited to the task under current implementations of the language."<LI><A HREF = "#7841pn$1ha$1@uni00nw.unity.ncsu.edu">1999-01-20 Dmitri Zaykin:</A> "Templates can be an alternative to C-macros in terms of genericity, not inlining."<LI><A HREF = "#780824$ie4$1@relay1.dsccc.com">1999-01-18 Mike McCarty:</A> "There are no 'idiot-proof languages'."<LI><A HREF = "#780ip6$11h8@odds.stat.purdue.edu">1999-01-18 Herman Rubin:</A> "A language has a built in inefficiency in every situation in which the optimal use of machine instructions cannot be addressed in that language."<LI><A HREF = "#787tt7$gr$1@relay1.dsccc.com">1999-01-21 Mike McCarty:</A> "The checking I had in mind costs *nothing* during the execution of the program."<LI><A HREF = "#7k8ym6d4q.fsf@poole.statgen.ncsu.edu">1999-01-16 Dmitri Zaykin:</A> "I see one more problem with the code."<LI><A HREF = "#781p6l$lrv$1@nnrp1.dejanews.com">1999-01-19 qscgz@my-dejanews.com:</A> "DIEHARD-tests fail on...."<LI><A HREF = "#36A5FC62.17C9CC33@stat.fsu.edu">1999-01-20 George Marsaglia:</A> "My offer of RNG's for C was an invitation to dance; I did not expect the Tarantella." "Numerous responses have led to improvements; the result is the listing below...."</UL><PRE><HR><A NAME = "369B5E30.65A55FD1@stat.fsu.edu"></A>Subject: Random numbers in C: Some suggestions.Date: Tue, 12 Jan 1999 09:37:37 -0500From: George Marsaglia <geo@stat.fsu.edu>Message-ID: <369B5E30.65A55FD1@stat.fsu.edu>Newsgroups: sci.stat.math,sci.math,sci.math.num-analysis,sci.crypt,sci.physicsLines: 243This posting ends with 17 lines ofC code that provide eight differentin-line random number generators, six forrandom 32-bit integers and two for uniformreals in (0,1) and (-1,1).Comments are interspersed with thatcode. Various combinations of the six in-lineinteger generators may put in C expressions toprovide a wide variety of very fast, long period,well-tested RNG's. I invite comments, feedback,verifications and timings.First, there is narrative giving backgroundfor this posting; you may want to skip it.Narrative:Having had experience in producing andtesting for randomness in computers,I am frequently asked to suggest goodrandom number generators (RNG's), testRNG's, or comment on existing RNG's. Manyrecent queries have been in two areas:(1) requests for implementations in C and(2) comments on generators with immense periods,particularly the Mersenne Twister.This posting is mainly for category (1),for which I suggest a set of C implementationsof RNG's I have developed. C implementationsof my DIEHARD battery of tests will bediscussed elsewhere, and Narasimhan's GUIversion is expected to be released soon.For (2), I merely repeat what I have saidin response to various queries: the MersenneTwister looks good, but it seems to be essentiallya lagged Fibonacci RNG using the exclusive-or(xor) operation, and experience has shown thatlagged Fibonacci generators using xor provideunsatisfactory 'randomness' unless the lags arevery long, and even for those with very long lags,(and even for those using + or - rather than xor),many people (I among them) are inclined to becautious about sequences based on such a simpleoperation as: each new integer is the xor, (or sum,or difference), of two earlier ones. To be sure,the resulting integers can be "twisted", but not,I think, as simply or as safely as combining, sayby addition, with members of a sequence from a(shorter period) generator that has itself passedextensive tests of randomness.I also reply that it does not take an immenseprogram (as, for example, in posted listingsof Twister) to produce a more satisfactory RNGwith an immense period, and give this example,on which I will expand below: Inclusion of#define SWB ( t[c+237]=(x=t[c+15])-(y=t[++c]+(x<y)) )together with suitably initialized seeds instatic unsigned long x,y,t[256]; unsigned char c;will allow you to put the string SWB in any Cexpression and it will provide, in about 100 nanosecs,a 32-bit random integer with period 2^7578. (Hereand below, ^ means exponent, except in C expressions,where it means xor (exclusive-or).Now for the (2) part, in which I suggest a numberof C implementations and invite comment and feedback.Most of these were previously developed and testedvia Fortran versions. I list eight RNG's, each ofthem by means of C's powerful #define device. Thisprovides fast, compact implementation, allowsinsertion of the required random variable directlyinto an expression, and, finally, provides a goodselection of RNG's for use individually or incombination. The latter makes it possible tofurther confirm what empirical results suggest:combining two or more RNG's provides better,(or no worse) randomness, and for encryption enthusiasts:combination generators are harder to "crack".For those wishing to try these eight RNG's:At the top of your C program, include thesedefinitions and the static variables that follow.Everything past this line is either C code or comment.--------------------------------------------------#define UL unsigned long#define znew ((z=36969*(z&65535)+(z>>16))<<16)#define wnew ((w=18000*(w&65535)+(w>>16))&65535)#define MWC (znew+wnew)#define SHR3 (jsr=(jsr=(jsr=jsr^(jsr<<17))^(jsr>>13))^(jsr<<5))#define CONG (jcong=69069*jcong+1234567)#define KISS ((MWC^CONG)+SHR3)#define LFIB4 (t[c]=t[c]+t[c+58]+t[c+119]+t[++c+178])#define SWB (t[c+237]=(x=t[c+15])-(y=t[++c]+(x<y)))#define UNI (KISS*2.328306e-10)#define VNI ((long) KISS)*4.656613e-10/* Global static variables: */ static UL z=362436069, w=521288629, jsr=123456789, jcong=380116160; static UL t[256]; static UL x=0,y=0; static unsigned char c=0;/* Random seeds must be used to reset z,w,jsr,jcong andthe table t[256] Here is an example procedure, using KISS: */ void settable(UL i1,UL i2,UL i3,UL i4) { int i; z=i1;w=i2,jsr=i3; jcong=i4; for(i=0;i<256;i++) t[i]=KISS; }/* End of C code; Only comments follow. Stick the above 17 lines in your simulation programs, initialize the table, and have a variety of promising RNG's at your disposal. *//* You may want use more complicated names for the above simple 1-letter variable names: z,w,x,y,t,c, to avoid clashing with favorites in your code. *//* Any one of KISS, MWC, LFIB4, SWB, SHR3, or CONG can be used in an expression to provide a random 32-bit integer, and UNI in an expression will provide a random uniform in (01), or VNI in (-1,1). For example, for int i, float v; i=(MWC>>24); will provide a random byte, while v=4.+3.*UNI; will provide a uniform v in the interval 4. to 7.⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -