From: Nathan F. <fr...@cs...> - 2004-04-14 15:49:10
Attachments:
random-stats.txt
random.diff
|
Attached is a patch which removes the x86 VOP/assembly support for the Mersenne Twister RNG. In place of this, the core functions of the algorithm have been beefed up with modular arithmetic. The speed penalty for doing this change is minor. Also included is a timing test (very ad hoc) and disassemblies for the old (VOP) and new (CL) implementations. The speed tests were done on an 800MHz Pentium III with 256MB RAM. smoke.impure.lisp seems to fail with this change in place, but I'm not sure why (compiler is cmucl 18e). Insight would be appreciated. -- Nathan | http://www.cs.rose-hulman.edu/~froydnj/ | Credo ut intelligam From Man's effeminate slackness it begins. --Paradise Lost |
From: Perry E. M. <pe...@pi...> - 2004-04-14 17:04:04
|
Nathan Froyd <fr...@cs...> writes: > Attached is a patch which removes the x86 VOP/assembly support for the > Mersenne Twister RNG. In place of this, the core functions of the > algorithm have been beefed up with modular arithmetic. The speed > penalty for doing this change is minor. Also included is a timing test > (very ad hoc) and disassemblies for the old (VOP) and new (CL) > implementations. The speed tests were done on an 800MHz Pentium III > with 256MB RAM. BTW, you tried seeing what the speed of RC4 is in a machine language implementation? I suspect it is astoundingly fast, and probably quite good as a PRNG. (Never say RNG, since none of these produce real random numbers, only pseudo-random.) Perry |
From: Alexey D. <ade...@co...> - 2004-04-14 17:34:44
|
Hello, > - (setf y (logior (logand (aref state kk) mt19937-upper-mask) > - (logand (aref state (1+ kk)) mt19937-lower-mask))) > - (setf (aref state kk) (logxor (aref state (+ kk mt19937-m)) > - (ash y -1) (aref state (logand y 1))))) > + (setf y (ldb (byte 32 0) (logior (logand (aref state kk) mt19937-upper-mask) > + (logand (aref state (1+ kk)) mt19937-lower-mask)))) > + (setf (aref state kk) (ldb (byte 32 0) (logxor (aref state (+ kk mt19937-m)) > + (ash y -1) (aref state (logand y 1)))))) Is this change really necessary? AFAIS MT19937-UPPER-MASK and MT19937-LOWER-MASK are of type (UNSIGNED-BYTE 32), so LOGAND and LOGIOR return objects of the same type, and LDB seems superfluous. -- Regards, Alexey Dejneka "Alas, the spheres of truth are less transparent than those of illusion." -- L.E.J. Brouwer |
From: Nathan F. <fr...@cs...> - 2004-04-14 17:43:50
|
On Wed, Apr 14, 2004 at 09:28:44PM +0400, Alexey Dejneka wrote: > > - (setf y (logior (logand (aref state kk) mt19937-upper-mask) > > - (logand (aref state (1+ kk)) mt19937-lower-mask))) > > - (setf (aref state kk) (logxor (aref state (+ kk mt19937-m)) > > - (ash y -1) (aref state (logand y 1))))) > > + (setf y (ldb (byte 32 0) (logior (logand (aref state kk) mt19937-upper-mask) > > + (logand (aref state (1+ kk)) mt19937-lower-mask)))) > > + (setf (aref state kk) (ldb (byte 32 0) (logxor (aref state (+ kk mt19937-m)) > > + (ash y -1) (aref state (logand y 1)))))) > > Is this change really necessary? AFAIS MT19937-UPPER-MASK and > MT19937-LOWER-MASK are of type (UNSIGNED-BYTE 32), so LOGAND and > LOGIOR return objects of the same type, and LDB seems superfluous. Would appear that all the LDBs in RANDOM-MT19937-UPDATE are indeed superfluous. Thanks for pointing this out. -- Nathan | http://www.cs.rose-hulman.edu/~froydnj/ | Credo ut intelligam From Man's effeminate slackness it begins. --Paradise Lost |
From: Raymond T. <eu...@rt...> - 2004-04-15 15:56:05
|
>>>>> "Nathan" == Nathan Froyd <fr...@cs...> writes: Nathan> Would appear that all the LDBs in RANDOM-MT19937-UPDATE are indeed Nathan> superfluous. Thanks for pointing this out. That's because that's what is used for all platforms besides x86 and was written so that it wouldn't cons to death. Otherwise, I doubt the other platforms would have used this generator at all. :-) Ray |
From: Nathan F. <fr...@cs...> - 2004-04-14 17:45:07
|
On Wed, Apr 14, 2004 at 01:03:57PM -0400, Perry E. Metzger wrote: > BTW, you tried seeing what the speed of RC4 is in a machine language > implementation? I suspect it is astoundingly fast, and probably quite > good as a PRNG. (Never say RNG, since none of these produce real > random numbers, only pseudo-random.) Last I heard, RC4 was somewhat slow and not a very good PRNG: http://burtleburtle.net/bob/rand/isaacafa.html Doubt it's much better than the Mersenne Twister. -- Nathan | http://www.cs.rose-hulman.edu/~froydnj/ | Credo ut intelligam From Man's effeminate slackness it begins. --Paradise Lost |
From: Perry E. M. <pe...@pi...> - 2004-04-14 18:54:02
|
Nathan Froyd <fr...@cs...> writes: > On Wed, Apr 14, 2004 at 01:03:57PM -0400, Perry E. Metzger wrote: >> BTW, you tried seeing what the speed of RC4 is in a machine language >> implementation? I suspect it is astoundingly fast, and probably quite >> good as a PRNG. (Never say RNG, since none of these produce real >> random numbers, only pseudo-random.) > > Last I heard, RC4 was somewhat slow and not a very good PRNG: > > http://burtleburtle.net/bob/rand/isaacafa.html I see no evidence for your claim on that page. It only claims that ISAAC, the author's pet algorithm, is faster -- it makes no claims about RC4 producing bad output. > Doubt it's much better than the Mersenne Twister. Oh yah? A modestly well done RC4 in machine language is something like 10 to 20 x86 instructions/byte of output depending on what tricks you use and how many bytes of output you are trying for. A totally naive implementation compiled from C shows 19 instructions output by cc -S for the core of the algorithm. The instructions in question are also dead simple -- moves and xors, all of which translates to RISC very well. I get a large multiple of that number of instructions for Mersenne Twister -- the function that produces a quad of output is itself something over 100 instructions long, and it has loops in it that I didn't bother to count the cycles on because it was already obvious who the winner was. My apologies for using cc -O2 -S as my spot check method, but I find it is easier to look at the bare bones that way. For Mersenne Twister, I used the fastest C version linked off of http://www.math.keio.ac.jp/~matumoto/emt.html. For RC4, I wrote the algorithm from memory in about three minutes, without attempting any sort of optimization. (RC4 is so dead simple it is trivial to remember.) BTW, if you can create an algorithm that will distinguish the output of RC4 (once you pass the first k or two of output) from random noise with more than 50% probability, there is fame and fortune awaiting you. It is true that there are faster algorithms than RC4 -- including SEAL, which is patented, but will do something like 5 instructions/byte of output. However, if you're looking for something quick and easy, it is hard to beat RC4 for speed and quality of the output -- even if it isn't cryptographically strong (which it likely is), it is far more than good enough for the purposes to which random number generators are generally put. Perry |
From: Raymond T. <eu...@rt...> - 2004-04-15 15:55:13
|
>>>>> "Perry" == Perry E Metzger <pe...@pi...> writes: Perry> I get a large multiple of that number of instructions for Mersenne Perry> Twister -- the function that produces a quad of output is itself Perry> something over 100 instructions long, and it has loops in it that I Perry> didn't bother to count the cycles on because it was already obvious Perry> who the winner was. If I remember correctly, that cost only happens once every 623 calls. The random number is read from the state vector until it's used up, and then a new state is computed. So the cost is somewhat bursty in nature. Perry> It is true that there are faster algorithms than RC4 -- including Perry> SEAL, which is patented, but will do something like 5 Perry> instructions/byte of output. However, if you're looking for something Perry> quick and easy, it is hard to beat RC4 for speed and quality of the Perry> output -- even if it isn't cryptographically strong (which it likely Perry> is), it is far more than good enough for the purposes to which random Perry> number generators are generally put. Maybe. Has anyone actually tested RC4? I pretty sure Peter Van Enyde did some extensive tests with mt19937, and it passed Marsaglia's DieHard tests and also passed the Ising physical model test. Ray |
From: Perry E. M. <pe...@pi...> - 2004-04-15 18:10:06
|
Raymond Toy <eu...@rt...> writes: > Maybe. Has anyone actually tested RC4? I pretty sure Peter Van Enyde > did some extensive tests with mt19937, and it passed Marsaglia's > DieHard tests and also passed the Ising physical model test. RC4 passes every random test you can throw at it. It is, after all, a cryptographic algorithm. Cryptographic generators have to produce output that is computationally indistinguishable from noise with less computation than is required to brute force the key -- by definition. There is one slight exception -- there are some patterns visible in the output of the first couple hundred output bytes if you really strain to see them. The usual solution used in the crypto community for that is to throw them away. :) In a non-cryptographic context, though, the generator is pretty much perfect. Anyway, for monte carlo simulations, I can't see anything that would be better than RC4 from the point of view of the quality of the output. There are other algorithms that are somewhat faster, but they are patented to my knowledge. Perry |