KISS4691, a potentially top-ranked RNG.
in [Math]
|
From: Harald Anlauf on 26 Jul 2010 15:36 On Jul 24, 3:02 pm, geo <gmarsag...(a)gmail.com> wrote: > 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. Does this mean that using different seeds will lead to streams that are always statistically independent (as long as one does not exhaust the RNG's period)? Or are there restrictions on the possible combinations of seeds? I am currently using D.E.Knuth's generator from TAOCP, which IIRC allows for 2^30-2 independent streams, and which are asserted to be independent, but being able to extend the "limit" would be nice. Harald
From: Gib Bogle on 26 Jul 2010 16:06 robin wrote: > "Gib Bogle" <g.bogle(a)auckland.no.spam.ac.nz> wrote in message news:i2ij74$kd6$1(a)speranza.aioe.org... > | geo wrote: > | > Thanks very much for the Fortran version. > | > I made a mistake in the comment on versions > | > for signed integers. This: > | > > | > Languages requiring signed integers should use equivalents > | > of the same operations, except that the C statement: > | > c=(t<x)+(x>>19); > | > can be replaced by that language's version of > | > if sign(x<<13+c)=sign(x) then c=sign(x)+(x>>19) > | > else c=1-sign(x<<13+c)+(x>>19) > | > > | > Sorry for that error. > | > | That produces different c values from those generated by the method based on the > | value of (t<x), therefore it deviates from the C code. This is what I used: > | > | m = shiftl(x,13) + c > | if (sign(1,m) == sign(1,x)) then > | c = sign(1,x) + shiftr(x,19) > | else > | c = 1 - sign(1,m) + shiftr(x,19) > | endif > > Maybe I missed something, > but isn't this exactly equivalent to what George wrote? > Just substitute x<<13+c for m in your last two assignments ... I hope so. Maybe I didn't express myself clearly enough. I'll try again. Using my implementation of George's corrected code, I get results from the Fortran code that differ from those generated by his C code.
From: Gib Bogle on 26 Jul 2010 16:07 Geoff wrote: > I am no FORTRAN hacker but I think there's a difference between > sign(x) and sign(1,x). sign(1,x) returns the sign of x.
From: nmm1 on 26 Jul 2010 16:09 In article <fa9dd141-823a-4179-a80b-18d214a3e846(a)t2g2000yqe.googlegroups.com>, Harald Anlauf <anlauf.2008(a)arcor.de> wrote: >On Jul 24, 3:02=A0pm, geo <gmarsag...(a)gmail.com> wrote: >> 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. > >Does this mean that using different seeds will lead to >streams that are always statistically independent >(as long as one does not exhaust the RNG's period)? >Or are there restrictions on the possible combinations >of seeds? No. Without checking it more carefully, I can't say definitely, but it looks as if you would be very unlikely to notice a PRACTICAL association with two different seeds, provided that you throw away the first 10,000 or so numbers - and even that qualification may be unnecessary. But, unless I have some missed some subtlety, the sequences cannot be guaranteed to be pseudo-independent. The only two methods I know of of guaranteeing pseudo-independence are using coprime sequences and by choosing them using the spectral test or equivalent. Even then, there are some qualifications on what is meant by pseudo-independence. However, in practice, it's rare to have trouble with high-quality generators. >I am currently using D.E.Knuth's generator from TAOCP, >which IIRC allows for 2^30-2 independent streams, and >which are asserted to be independent, but being able to >extend the "limit" would be nice. Eh? Which version? There was assuredly nothing with those properties in edition 2. The first papers on the topic were later. You need to be very careful to distinguish separate (i.e. disjoint) sequences from pseudo-independent ones, and FAR too many papers written by people who ought to know better confuse the two. Doing that is a common cause of seriously wrong answers in some types of calculation. Regards, Nick Maclaren.
From: Harald Anlauf on 26 Jul 2010 16:32
On Jul 26, 10:09 pm, n...(a)cam.ac.uk wrote: > In article <fa9dd141-823a-4179-a80b-18d214a3e...(a)t2g2000yqe.googlegroups.com>, > Harald Anlauf <anlauf.2...(a)arcor.de> wrote: > > >Does this mean that using different seeds will lead to > >streams that are always statistically independent > >(as long as one does not exhaust the RNG's period)? > >Or are there restrictions on the possible combinations > >of seeds? > > No. Without checking it more carefully, I can't say definitely, > but it looks as if you would be very unlikely to notice a PRACTICAL > association with two different seeds, provided that you throw > away the first 10,000 or so numbers - and even that qualification > may be unnecessary. But, unless I have some missed some subtlety, > the sequences cannot be guaranteed to be pseudo-independent. > > The only two methods I know of of guaranteeing pseudo-independence > are using coprime sequences and by choosing them using the spectral > test or equivalent. Even then, there are some qualifications on > what is meant by pseudo-independence. However, in practice, it's > rare to have trouble with high-quality generators. I was shown funny experiences with simple generators... =:-o > >I am currently using D.E.Knuth's generator from TAOCP, > >which IIRC allows for 2^30-2 independent streams, and > >which are asserted to be independent, but being able to > >extend the "limit" would be nice. > > Eh? Which version? There was assuredly nothing with those > properties in edition 2. The first papers on the topic were later. http://www-cs-faculty.stanford.edu/~uno/news02.html#rng > You need to be very careful to distinguish separate (i.e. disjoint) > sequences from pseudo-independent ones, and FAR too many papers > written by people who ought to know better confuse the two. Doing > that is a common cause of seriously wrong answers in some types of > calculation. For an application which needs to distribute a large problem over many processors it is very useful to have many (pseudo-)independent streams, at least they should be practically indistinguishable from independent ones. An accidental correlation is likely worse than a short period. Harald |