KISS4691, a potentially top-ranked RNG.
in [Math]
|
From: Gib Bogle on 29 Jul 2010 22:14 Uno wrote: > Gib, can you post your entire fortran version? OK, here's the Fortran. I've removed almost all the comments to save space. If you uncomment the line in MWC(): c = c_this_works you'll see how to reproduce the C code results. Gib module kiss_mod implicit none integer :: xs = 521288629 integer :: xcng = 362436069 integer :: Q(0:4690) contains integer function MWC() integer :: m, x, i integer, save :: c = 0, j = 4691 integer :: t, tLTx, c_this_works if (j < 4690) then j = j + 1 else j = 0 endif x = Q(j) m = SHIFTL(x,13) + c Q(j) = m + x t = Q(j) ! This is the laborious determination of c if ((t >= 0 .and. x >= 0) .or. (t < 0 .and. x < 0)) then if (t < x) then tLTx = 1 else tLTx = 0 endif elseif (x < 0) then tLTx = 1 elseif (t < 0) then tLTx = 0 endif c_this_works = tLTx + SHIFTR(x,19) ! This c gives results inconsistent with the C code 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 ! c = c_this_works MWC = Q(j) end function subroutine test_RNG4691 integer :: i, x, unsigned_result integer :: n = 1000000000 do i = 0, 4690 xcng = 69069 * xcng + 123 xs = XOR(xs,SHIFTL(xs,13)) xs = XOR(xs,SHIFTR(xs,17)) xs = XOR(xs,SHIFTL(xs,5)) Q(i) = xcng + xs enddo do i = 1, n x = MWC() enddo unsigned_result = 3740121002 write(*,*) "MWC result=3740121002 ?: ",unsigned_result,x do i = 1,n xcng = 69069 * xcng + 123 xs = XOR(xs,SHIFTL(xs,13)) xs = XOR(xs,SHIFTR(xs,17)) xs = XOR(xs,SHIFTL(xs,5)) x = MWC() + xcng + xs enddo unsigned_result = 2224631993 write(*,*) "KISS result=2224631993 ?: ",unsigned_result,x end subroutine end module program main use kiss_mod call test_RNG4691 end program
From: Uno on 29 Jul 2010 22:43 Gib Bogle wrote: > OK, here's the Fortran. I've removed almost all the comments to save > space. > If you uncomment the line in MWC(): > c = c_this_works > you'll see how to reproduce the C code results. Alright, thx, gib, looks like there's a couple rough corners: $ gfortran geo1.f90 -o out geo1.f90:63.32: unsigned_result = 3740121002 1 Error: Integer too big for its kind at (1). This check can be disabled with the option -fno-range-check So, do I ask for something bigger than the default integer, use the iso_c_binding, or disable the warning? I think of 3.5 billion as a value that busts types in C. I would have thought that was going on except for the second error: geo1.f90:72.32: unsigned_result = 2224631993 1 Error: Integer too big for its kind at (1). This check can be disabled with the option -fno-range-check Then there's this. It looks like the bitshifting capabilities that fortran and C have, but neither MR&C nor my slightly-inappropriate C reference have a SHIFTL. Do you have a definition for it? geo1.f90:55.16: xs = XOR(xs,SHIFTL(xs,13)) 1 Error: Function 'shiftl' at (1) has no IMPLICIT type Beautiful night with the cicadas humming. I don't know that I've ever seen one which makes them, aesthetically, my favorite bug. Cheers, -- Uno
From: Ron Shepard on 29 Jul 2010 23:13 In article <i2ssst$nfi$1(a)speranza.aioe.org>, glen herrmannsfeldt <gah(a)ugcs.caltech.edu> wrote: > In a large fraction of the cases, 2 billion different seeds > are enough, but one can still desire the appropriate randomness > from those different seeds. My understanding is that pseudorandom number generators return a sequence of values with some period. The numbers in that sequence eventually repeat with some, hopefully long, cycle. The put=array argument gives the starting point within that sequence, but it doesn't affect the cycle length or the "randomness" of the values, those things are determined by the underlying algorithm, not by the initial seed. The situation that needs to be avoided is to run the code once with one seed, and then run it again with another seed that results in an overlap of the sequences of values for the two runs. In some applications this is unimportant, but in other applications it would be bad for two supposedly independent runs to have a long sequence of identical values. It would be nice if there were some prescription to generate initial seeds that would avoid this situation. However, I don't really know how this could be specified in the fortran standard without specifying the algorithm itself (which is not done, apparently on purpose). Anyone have any ideas how this could be done? $.02 -Ron Shepard
From: glen herrmannsfeldt on 29 Jul 2010 23:33 In comp.lang.fortran Ron Shepard <ron-shepard(a)nospam.comcast.net> wrote: > In article <i2ssst$nfi$1(a)speranza.aioe.org>, > glen herrmannsfeldt <gah(a)ugcs.caltech.edu> wrote: >> In a large fraction of the cases, 2 billion different seeds >> are enough, but one can still desire the appropriate randomness >> from those different seeds. > My understanding is that pseudorandom number generators return a > sequence of values with some period. The numbers in that sequence > eventually repeat with some, hopefully long, cycle. The put=array > argument gives the starting point within that sequence, but it doesn't > affect the cycle length or the "randomness" of the values, those things > are determined by the underlying algorithm, not by the initial seed. > The situation that needs to be avoided is to run the code once with one > seed, and then run it again with another seed that results in an overlap > of the sequences of values for the two runs. In some applications this > is unimportant, but in other applications it would be bad for two > supposedly independent runs to have a long sequence of identical values. > It would be nice if there were some prescription to generate initial > seeds that would avoid this situation. However, I don't really know how > this could be specified in the fortran standard without specifying the > algorithm itself (which is not done, apparently on purpose). Anyone > have any ideas how this could be done? Here is the suggestion. Add to RANDOM_SEED a form that allows a single integer variable to be supplied as a seed source. As far as I know, there is no requirement on period or otherwise on the quality of the PRNG used, but the standard could suggest that good seeds be selected from that integer. For example, they could be chosen such that they have a fairly long sequence before they overlap the sequence generated by another input value. If the RNG only has 32 bits of state, or maybe less, then it likely takes it directly. I don't know the math of the newer PRNGs enough to say, but I think it is possible to do that. With the current standard there is no way to even suggest to RANDOM_SEED that you want a good seed. OK, here is another suggestion that could be implemented without any change in the standard. In the case where the supplied seed array has all except the first element zero, then select a good seed based on that first element. -- glen
From: orz on 30 Jul 2010 00:53
On Jul 29, 8:13 pm, Ron Shepard <ron-shep...(a)NOSPAM.comcast.net> wrote: > In article <i2ssst$nf...(a)speranza.aioe.org>, > glen herrmannsfeldt <g...(a)ugcs.caltech.edu> wrote: > > > In a large fraction of the cases, 2 billion different seeds > > are enough, but one can still desire the appropriate randomness > > from those different seeds. > > My understanding is that pseudorandom number generators return a > sequence of values with some period. The numbers in that sequence > eventually repeat with some, hopefully long, cycle. The put=array > argument gives the starting point within that sequence, but it doesn't > affect the cycle length or the "randomness" of the values, those things > are determined by the underlying algorithm, not by the initial seed. > > The situation that needs to be avoided is to run the code once with one > seed, and then run it again with another seed that results in an overlap > of the sequences of values for the two runs. In some applications this > is unimportant, but in other applications it would be bad for two > supposedly independent runs to have a long sequence of identical values. > It would be nice if there were some prescription to generate initial > seeds that would avoid this situation. However, I don't really know how > this could be specified in the fortran standard without specifying the > algorithm itself (which is not done, apparently on purpose). Anyone > have any ideas how this could be done? > > $.02 -Ron Shepard On Jul 29, 8:13 pm, Ron Shepard <ron-shep...(a)NOSPAM.comcast.net> wrote: > In article <i2ssst$nf...(a)speranza.aioe.org>, > glen herrmannsfeldt <g...(a)ugcs.caltech.edu> wrote: > > > In a large fraction of the cases, 2 billion different seeds > > are enough, but one can still desire the appropriate randomness > > from those different seeds. > > My understanding is that pseudorandom number generators return a > sequence of values with some period. The numbers in that sequence > eventually repeat with some, hopefully long, cycle. The put=array > argument gives the starting point within that sequence, but it doesn't > affect the cycle length or the "randomness" of the values, those things > are determined by the underlying algorithm, not by the initial seed. > > The situation that needs to be avoided is to run the code once with one > seed, and then run it again with another seed that results in an overlap > of the sequences of values for the two runs. In some applications this > is unimportant, but in other applications it would be bad for two > supposedly independent runs to have a long sequence of identical values. > It would be nice if there were some prescription to generate initial > seeds that would avoid this situation. However, I don't really know how > this could be specified in the fortran standard without specifying the > algorithm itself (which is not done, apparently on purpose). Anyone > have any ideas how this could be done? > > $.02 -Ron Shepard If an RNG has a large number of possible states (say, 2^192) then it's unlikely for any two runs to EVER reach identical states by any means other than starting from the same seed. This RNG has a period vastly in excess of "large", so for practical purposes it just won't happen. However, because this is a combination of multiple component RNGs there is the related issue of overlapping within the period of one or more component RNGs. MWC has essentially zero chance of being in an identical state for any reason other than identical seeding, but both XS and CNG will frequently have identical states in two different runs. There does not seem to be any detectable correlation however unless (either MWC or (both XS and CNG)) have identical states between two different runs. Which is rather uncommon, though it does happen often enough to see it in the real world on occasion. |