From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-0.9 required=5.0 tests=BAYES_00,FORGED_GMAIL_RCVD, FREEMAIL_FROM autolearn=no autolearn_force=no version=3.4.4 X-Google-Thread: 109d8a,ea40acba15d5d078 X-Google-NewGroupId: yes X-Google-Thread: 1094ba,ea40acba15d5d078 X-Google-NewGroupId: yes X-Google-Thread: 103376,c5d0be666830517,start X-Google-NewGroupId: yes X-Google-Attributes: gid9ef9b79ae9,gid8d3408f8c3,gida07f3367d7,domainid0,public,usenet X-Google-Language: ENGLISH,ASCII Path: g2news1.google.com!postnews.google.com!y11g2000yqm.googlegroups.com!not-for-mail From: Gene Newsgroups: sci.math,comp.lang.fortran,comp.lang.ada Subject: Re: KISS4691, a potentially top-ranked RNG. Date: Sat, 24 Jul 2010 17:49:59 -0700 (PDT) Organization: http://groups.google.com Message-ID: <9ea9185a-23e7-4265-acde-097c5c14ca14@y11g2000yqm.googlegroups.com> References: NNTP-Posting-Host: 184.12.83.13 Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable X-Trace: posting.google.com 1280019000 4025 127.0.0.1 (25 Jul 2010 00:50:00 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: Sun, 25 Jul 2010 00:50:00 +0000 (UTC) Complaints-To: groups-abuse@google.com Injection-Info: y11g2000yqm.googlegroups.com; posting-host=184.12.83.13; posting-account=-BkjswoAAACC3NU8b6V8c50JQ2JBOs04 User-Agent: G2/1.0 X-HTTP-UserAgent: Mozilla/4.0 (compatible; MSIE 7.0; Windows NT 5.1; Trident/4.0; GTB6.5; .NET CLR 1.1.4322; .NET CLR 2.0.50727; .NET CLR 3.0.04506.30; .NET CLR 3.0.04506.648; .NET CLR 3.0.4506.2152; .NET CLR 3.5.30729),gzip(gfe) Xref: g2news1.google.com sci.math:174654 comp.lang.fortran:25978 comp.lang.ada:12536 Date: 2010-07-24T17:49:59-07:00 List-Id: On Jul 24, 9:02=A0am, geo wrote: > I have been asked to recommend an RNG > (Random Number Generator) that ranks > at or near the top in all of the categories: > performance on tests of randomness, > length of period, simplicity and speed. > The most important measure, of course, is > performance on extensive tests of randomness, and for > those that perform well, selection may well depend > on those other measures. > > The following KISS version, perhaps call it KISS4691, > seems to rank at the top in all of those categories. > It is my latest, and perhaps my last, as, at age 86, > I =A0 =A0am =A0 =A0 =A0 =A0slowing =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0down. > > Compiling and running the following commented > C listing should produce, within about four seconds, > 10^9 calls to the principal component MWC(), then > 10^9 calls to the KISS combination in another ~7 seconds. > > Try it; you may like it. > > George Marsaglia > > /* > The KISS4691 RNG, a Keep-It-Simple-Stupid combination of > MWC (Multiply-With-Carry), Congruential and Xorshift sequences. > Expressed as a simple MWC() function and C macros > =A0#define CNG ( xcng=3D69069*xcng+123 ) > =A0#define XS ( xs^=3D(xs<<13), xs^=3D(xs>>17), xs^=3D(xs<<5) ) > =A0#define KISS ( MWC()+CNG+XS ) > but easily expressed in other languages, with a slight > complication for signed integers. > > With its immense period, >10^45000, and speed: MWC()s at > around 238 million/sec or full KISSes at around 138 million, > there are few RNGs that do as well as this one > on tests of randomness and are comparable in even one > of the categories: period, speed, simplicity---not to > mention comparable in all of them. > > The MWC4691 sequence x[n]=3D8193*x[n-4691]+carry mod b=3D2^32 > is based on p=3D8193*b^4691-1, period ~ 2^150124 =A0or 10^45192 > For the MWC (Multiply-With-Carry) process, given a current > x and c, the new x is =A0 =A0(8193*x+c) mod b, > =A0 =A0 =A0 =A0 =A0the new c is =A0 =A0the integer part of (8193*x+c)/b. > > The routine MWC() produces, in reverse order, =A0the base-b=3D2^32 > expansion of some j/p with 0 determined by the 64 bits of seeds xcng and xs, or more > generally, by 150112 random bits in the Q[] array. > */ > > static unsigned long xs=3D521288629,xcng=3D362436069,Q[4691]; > > unsigned long MWC(void) =A0/*takes about 4.2 nanosecs or 238 million/ > second*/ > {unsigned long t,x,i; static c=3D0,j=3D4691; > =A0 j=3D(j<4690)? j+1:0; > =A0 x=3DQ[j]; > =A0 t=3D(x<<13)+c+x; c=3D(t>19); > =A0 return (Q[j]=3Dt); > > } > > #define CNG ( xcng=3D69069*xcng+123 ) > #define XS ( xs^=3D(xs<<13), xs^=3D(xs>>17), xs^=3D(xs<<5) ) > #define KISS ( MWC()+CNG+XS ) /*138 million/sec*/ > > #include > int main() > {unsigned long i,x; > =A0for(i=3D0;i<4691;i++) Q[i]=3DCNG+XS; > =A0for(i=3D0;i<1000000000;i++) x=3DMWC(); > =A0printf(" MWC result=3D3740121002 ?\n%22u\n",x); > =A0for(i=3D0;i<1000000000;i++) x=3DKISS; > =A0printf("KISS result=3D2224631993 ?\n%22u\n",x); > > } > > /* > This RNG uses two seeds to fill the Q[4691] array by > means of CNG+XS mod 2^32. Users requiring more than two > seeds will need to randomly seed Q[] in main(). > By itself, the MWC() routine passes all tests in the > Diehard Battery of Tests, but it is probably a good > idea to include it in the KISS combination. > > Languages requiring signed integers should use equivalents > of the same operations, except that the C statement: > =A0 =A0 =A0 =A0c=3D(t>19); > can be replaced by that language's version of > =A0 if sign(x<<13+c)=3Dsign(x) then c=3Dsign(x)+(x>>19) > =A0 =A0 =A0 =A0 =A0 =A0else c=3D1-sign(t)+(x>>19) > */ Here's an implementation in Ada, verified to produce the same answers as the C code. The Ada version of gcc compiles this to nearly the same code as produced for the C. Function call overhead adds about 40% to the run time. What's a good way to take an arbitrary, single 32-bit seed value to a complete state initialization? Accept that lots of people will pick very small numbers. -- kiss_random_numbers.ads -- Specification for George Marsaglia's KISS random number generator. package KISS_Random_Numbers is type Result_Type is mod 2 ** 32; type State_Type is private; function Next_Random_Value(State : access State_Type) return Result_Type; private type State_Index_Type is mod 4691; type State_Vector_Type is array (State_Index_Type) of Result_Type; Initial_Q : State_Vector_Type; -- set in package body type Substate_Type is record Xs : Result_Type :=3D 521288629; Xcng : Result_Type :=3D 362436069; end record; type State_Type is record Sub : aliased Substate_Type; C : Result_Type :=3D 0; Q : State_Vector_Type :=3D Initial_Q; J : State_Index_Type :=3D State_Index_Type'Last; end record; end KISS_Random_Numbers; -- kiss_random_numbers.adb -- Implementation of George Marsaglia's KISS random number generator. package body KISS_Random_Numbers is function Mwc (State : access State_Type) return Result_Type is T, X : Result_Type; begin State.J :=3D State.J + 1; X :=3D State.Q(State.J); T :=3D X * 2**13 + State.C + X; if T < X then State.C :=3D X / 2**19 + 1; else State.C :=3D X / 2**19; end if; State.Q(State.J) :=3D T; return T; end Mwc; pragma Inline(Mwc); function Cng (State : access Substate_Type) return Result_Type is begin State.Xcng :=3D 69069 * State.Xcng + 123; return State.Xcng; end Cng; pragma Inline(Cng); function Xs (State : access Substate_Type) return Result_Type is Xs : Result_Type; begin Xs :=3D State.Xs; Xs :=3D Xs xor (Xs * 2**13); Xs :=3D Xs xor (Xs / 2**17); Xs :=3D Xs xor (Xs * 2**5); State.Xs :=3D Xs; return Xs; end Xs; pragma Inline(Xs); function Next_Random_Value(State : access State_Type) return Result_Type is begin return Mwc(State) + Cng(State.Sub'Access) + Xs(State.Sub'Access); end Next_Random_Value; begin declare S : aliased Substate_Type; begin for I in Initial_Q'Range loop Initial_Q(I) :=3D Cng(S'access) + Xs(S'Access); end loop; end; end KISS_Random_Numbers; -- test_kiss.adb -- Simple test of George Marsaglia's KISS random number generator. with Ada.Text_IO; use Ada.Text_IO; with KISS_Random_Numbers; use KISS_Random_Numbers; procedure Test_Kiss is X : Result_Type; S : aliased State_Type; begin for I in 1 .. 1000000000 loop X :=3D Next_Random_Value(S'Access); end loop; Put(Result_Type'Image(X)); New_Line; end;