In the UNIX API, if I want rand() to return the same sequence of numbers each time I run the program, I use srand() with a known seed.
How do I do this concept in ANSI Common Lisp?
I read up on make-random-state, but it seems to either only copy the current state, or make a new one. In addition, *random-state* is ugly. That isn't that useful of an API for what I want to do (or I don't see how to use it effectively). How is this traditionally solved?
In article <ij5f38$c9...@news.eternal-september.org>, Peter Keller <psil...@cs.wisc.edu> wrote:
> Hello,
> In the UNIX API, if I want rand() to return the same sequence of numbers > each time I run the program, I use srand() with a known seed.
> How do I do this concept in ANSI Common Lisp?
> I read up on make-random-state, but it seems to either only copy > the current state, or make a new one. In addition, *random-state* > is ugly. That isn't that useful of an API for what I want to do (or I > don't see how to use it effectively). How is this traditionally solved?
Peter Keller <psil...@cs.wisc.edu> writes: > Hello,
> In the UNIX API, if I want rand() to return the same sequence of numbers > each time I run the program, I use srand() with a known seed.
> How do I do this concept in ANSI Common Lisp?
> I read up on make-random-state, but it seems to either only copy > the current state, or make a new one. In addition, *random-state* > is ugly. That isn't that useful of an API for what I want to do (or I > don't see how to use it effectively). How is this traditionally solved?
Now, I understand your confusion: there's no standard way to store and load a known random state to be used as a seed later. Sorry about that. You can always use your own pseudo number generator, such as: http://cybertiggyr.com/jmt/
Peter Keller <psil...@cs.wisc.edu> writes: > I read up on make-random-state, but it seems to either only copy > the current state, or make a new one.
That is because the pseudorandom generation algorithm is not specified in the CLHS. (And that is a Good Thing.) So its state is implementation dependent and could even change between releases of the same implementation (if the implementation decided to use a different algorithm). Some implementations might provide the *random-state* object in a readable form, so that you could save it to reuse in a later run (by using #. to make it a readable object, for example). Alternatively, you could just study your implementation and construct the initial state by implementation dependent means.
> In addition, *random-state* is ugly.
In what way?
> That isn't that useful of an API for what I want to do (or I don't see > how to use it effectively).
It might not be as *easy* to use as just setting an integer seed. But the previous implies either 1) a very trivial algorithm or 2) that you could not retrieve the current state of the RNG in a compatible way (and that only a small subspace of initial states is available to you). All in all, the use of small seeds is a serious security exploit waiting to happen.
-- A change in perspective is worth 80 IQ points. --- Alan Kay
RG <rNOSPA...@flownet.com> wrote: > In article <ij5f38$c9...@news.eternal-september.org>, > Peter Keller <psil...@cs.wisc.edu> wrote:
>> Hello,
>> In the UNIX API, if I want rand() to return the same sequence of numbers >> each time I run the program, I use srand() with a known seed.
>> How do I do this concept in ANSI Common Lisp?
>> I read up on make-random-state, but it seems to either only copy >> the current state, or make a new one. In addition, *random-state* >> is ugly. That isn't that useful of an API for what I want to do (or I >> don't see how to use it effectively). How is this traditionally solved?
That lets you dump and load random-state objects to files (obviously those functions are not protecting themselves very much against bad things). Then, to start, you dump whatever random-state you care about, then reload it in every image. Obviously within the life of a single image you just have a random-state object you use as a seed, just using (make-random-state <state>) to make copies of it.
You might want to check the quality of random numbers you get from the built-in generator, though I suspect most implementations are pretty good since they tend to be maintained by nerds who care about that sort of thing...
> Some implementations might provide the *random-state* object > in a readable form, so that you could save it to reuse in a later run > (by using #. to make it a readable object, for example).
Just to be clear: implementations *must* do this: see the entry for RANDOM-STATE.
Peter Keller <psil...@cs.wisc.edu> writes: > Edmunds Cers <edmu...@laivas.lv> wrote: >>> In addition, *random-state* is ugly.
>> In what way?
> It is anything other than a single integer. :)
>> All in all, the use of small seeds is a serious security exploit waiting to >> happen.
> And someone is going to hack my noise generated textures how? *grin*
> I just want repeatable pseudo-random numbers for repeatable noise > generation in making textures, terrain, etc, etc, etc in graphics > applications.
I've been a little too strong, random-states are specified to be printable readably and readable, by the same implementation. So while you cannot "invent" new seeds, and you cannot transfer a random-state from one implementation to another, you can still use them for repeatable noise generation in making textures, terrain, etc, etc, etc in graphics applications.
Tim Bradshaw <t...@tfeb.org> writes: > You might want to check the quality of random numbers you get from the > built-in generator, though I suspect most implementations are pretty > good since they tend to be maintained by nerds who care about that > sort of thing...
Indeed, you get more or less 'randomness':
% clall -r '(length (princ-to-string *random-state*))' Armed Bear Common Lisp --> 26 International Allegro CL Free Express Edition --> 6749 Clozure Common Lisp --> 89 CLISP --> 86 CMU Common Lisp --> 8180 ECL --> 32 SBCL --> 14798
On Sat, 12 Feb 2011 10:41:35 +0100, Pascal J. Bourguignon wrote: > Tim Bradshaw <t...@tfeb.org> writes:
>> You might want to check the quality of random numbers you get from the >> built-in generator, though I suspect most implementations are pretty >> good since they tend to be maintained by nerds who care about that sort >> of thing...
> Indeed, you get more or less 'randomness': > [snip]
AFAIK SBCL uses the MT19937 generator, which is very fast, reasonably good, has a cycle length of 2^19937-1 (surprise :-), generally OK for uniforms up to a few hundred dimensions.
There are certainly better RNGs that are not too difficult to implement (eg in the multicarry family), but MT19937 is enough for most simple applications. BTW, Gentle's Random Number Generation and Monte Carlo Methods is an excellent starting point into the quality and implementation of RNG's, with tons of useful references.
Tamas K Papp <tkp...@gmail.com> wrote: +--------------- | Pascal J. Bourguignon wrote: | > % clall -r '(length (princ-to-string *random-state*))' ... | > CMU Common Lisp --> 8180 | > SBCL --> 14798 | | AFAIK SBCL uses the MT19937 generator, which is very fast, reasonably | good, has a cycle length of 2^19937-1 (surprise :-), generally OK for | uniforms up to a few hundred dimensions. +---------------
So does CMUCL, which makes me wonder why the above numbers are so different. Then I remembered that in CMUCL/ABCL random states are printed as structures containing an embedded vector of numbers:
With the default *PRINT-BASE* of 10, printing causes leading zeros to be suppressed as usual, so no *wonder* the above results are "random"!! ;-} With MT19937 -- and with the wrapping/indenting shown above -- (LENGTH (PRINC-TO-STRING *RANDOM-STATE*)) could be anywhere between roughly 1280 and 8350 characters or so.
So why is SBCL's value so much higher? I'm guessing a difference in the default printing parameters when running under Pascal's "clall" script. As you can see above, in the CMU case a significant fraction of the output string is whitespace for indenting the multiple lines of the :STATE slot. If the SBCL printer is only *slightly* different, it might print the above something like this:
Pascal J. Bourguignon <p...@informatimago.com> wrote: +--------------- | r...@rpw3.org (Rob Warnock) writes: | > Note the significant increase in whitespace characters. ;-} ;-} | > Moral: As always -- but *especially* with RANDOM -- when comparing | > implementations be sure that you're measuring what you think you are. ;-} | | Correct. Without print pretty, I get the results I wanted to get: | $ clall -r '(let ((*print-pretty* nil)) (length (princ-to-string | *random-state*)))' | Armed Bear Common Lisp --> 26 | International Allegro CL Free Express Edition --> 6749 | Clozure Common Lisp --> 89 | CLISP --> 83 | CMU Common Lisp --> 6741 | ECL --> 32 | SBCL --> 6821 +---------------
Aha! And now that makes it appear quite likely that ACL is probably using MT19937 as well as CMUCL and SBCL.
-Rob
----- Rob Warnock <r...@rpw3.org> 627 26th Avenue <http://rpw3.org/> San Mateo, CA 94403
On Saturday, February 12, 2011 4:41:35 AM UTC-5, Pascal J. Bourguignon wrote: > Tim Bradshaw <t...@tfeb.org> writes:
> > You might want to check the quality of random numbers you get from the > > built-in generator, though I suspect most implementations are pretty > > good since they tend to be maintained by nerds who care about that > > sort of thing...
A more typical test for the quality of randomness would be running a chi-squared test on a large sample of output generated by the random function in question.
> > > You'll almost certainly get better quality results than whatever your > > > implementation has built in.
> > Why include this piece of FUD?
> Because it's true.
Let me expand on that a little. There are good RNGs and bad RNGs. There are lot more of the latter than the former. Designing an RNG is one of those things (like cryptography) that's very easy to get wrong. If you rely on an implementation's RNG you may or may not be getting a good RNG. If you use the code I referenced then you are certainly getting a good RNG (by currently known standards). Since the code is portable and open-source it is almost certainly less effort to just use it than to determine whether or not your particular implementation has a good RNG. Making such a determination is non-trivial. It requires either examining source code (and knowing what you're doing), contacting the vendor, or running statistical tests, any of which is almost certainly more effort than just downloading the single file containing the mrg32k3a code and using it.
But this is of course not *necessarily* true. In CCL for example:
>> > > You'll almost certainly get better quality results than whatever your >> > > implementation has built in.
>> > Why include this piece of FUD?
>> Because it's true.
> Let me expand on that a little. There are good RNGs and bad RNGs.
And there's your problem. RNGs are typically evaluated along three axes:
1) their performance; 2) the apparent randomness of a sequence of produced numbers; 3) the suitability of the RNG for cryptographic applications.
There is no single standard of goodness and the second and third goals are conflicting with the first. You can (or could at least) get a faster RNG of the same "randomness" if you ignore the third requirement, for example.
There can certainly be reasons for using a library RNG instead of the built in one, like when you need a certain performance / randomness / cryptographic profile or just need to be able to share the state of the RNG between implementations (as might actually be required by the OP). But there is no reason to use a library RNG on principle, since the generators provided by the implementation should be good and well optimized.
> There are lot more of the latter than the former. Designing an RNG is > one of those things (like cryptography) that's very easy to get wrong. > If you rely on an implementation's RNG you may or may not be getting a > good RNG.
Do you believe any implementation provides an in-house RNG? If what you meant was that there are many factors to consider when choosing a RNG, then you are right. I'd guess that most implementations would choose something that is good either along the performance or the randomness axis and ignore the cryptographic axis (unless it comes at a small penalty). And no better choice can be made by you either, until you actually know what you need.
> If you use the code I referenced then you are certainly getting a good > RNG (by currently known standards). Since the code is portable and > open-source it is almost certainly less effort to just use it than to > determine whether or not your particular implementation has a good > RNG.
How do I know that the code you provide correctly implements the RNG it purports to implement? Also, its RANDOM is about 8 times slower on my CCL then the built in RANDOM. Plus, this provides an additional dependency to manage. Finally, will this still be the "best" RNG in twenty years? I'd expect implementations to change their RNG's as breakthroughs are made, whereas no support is promised for your library.
> Making such a determination is non-trivial. It requires either > examining source code (and knowing what you're doing), contacting the > vendor, or running statistical tests, any of which is almost certainly > more effort than just downloading the single file containing the > mrg32k3a code and using it.
Yeah, but making this determination is also unnecessary for most tasks. And your library is *not* universally better than the provided RNGs (see above). I think your whole line of argumentation is based on FUD. In fact, you should first show that the RNGs used by the implementations *are* bad, for your argument to have any validity.
> But this is of course not *necessarily* true. In CCL for example:
So CCL apparently uses some variant of the multiple recursive generator (same family as your library), while ACL, CMUCL, SBCL and ABCL use the Mersenne twister which is very good on the performance and randomness fronts. What are those bad implementations using broken RNGs? CLISP? That's 64 bits of state you posted above, not nearly small enough to assume some problem.
All in all, I think your initial statement was _really_ FUD-ish. There are too many misconceptions about Lisp floating around as is, for lispers themselves to make new ones up from thin air.
-- A change in perspective is worth 80 IQ points. --- Alan Kay
Wait, this comparison is not fair. For instance CLISP prints the random state in binary format in a readable form, while ECL prints in non-readable form and uses a 5000 character array for the random state, more or less (depends on word size among other things)
> Wait, this comparison is not fair. For instance CLISP prints the random > state in binary format in a readable form, while ECL prints in > non-readable form and uses a 5000 character array for the random state, > more or less (depends on word size among other things)
It's also just silly. You know how good a PRNG is by either understanding/recognising the algorithm or by testing it, or both, not my measuring how big the seed is in some uncontrolled printed form.
> >> > > You'll almost certainly get better quality results than whatever your > >> > > implementation has built in.
> >> > Why include this piece of FUD?
> >> Because it's true.
> > Let me expand on that a little. There are good RNGs and bad RNGs.
> And there's your problem. RNGs are typically evaluated along three axes:
> 1) their performance; > 2) the apparent randomness of a sequence of produced numbers; > 3) the suitability of the RNG for cryptographic applications.
> There is no single standard of goodness and the second and third goals > are conflicting with the first. You can (or could at least) get a faster > RNG of the same "randomness" if you ignore the third requirement, for > example.
> There can certainly be reasons for using a library RNG instead of the > built in one, like when you need a certain performance / randomness / > cryptographic profile or just need to be able to share the state of the > RNG between implementations (as might actually be required by the > OP). But there is no reason to use a library RNG on principle, since the > generators provided by the implementation should be good and well > optimized.
> > There are lot more of the latter than the former. Designing an RNG is > > one of those things (like cryptography) that's very easy to get wrong. > > If you rely on an implementation's RNG you may or may not be getting a > > good RNG.
> Do you believe any implementation provides an in-house RNG? If what you > meant was that there are many factors to consider when choosing a RNG, > then you are right. I'd guess that most implementations would choose > something that is good either along the performance or the randomness > axis and ignore the cryptographic axis (unless it comes at a small > penalty). And no better choice can be made by you either, until you > actually know what you need.
> > If you use the code I referenced then you are certainly getting a good > > RNG (by currently known standards). Since the code is portable and > > open-source it is almost certainly less effort to just use it than to > > determine whether or not your particular implementation has a good > > RNG.
> How do I know that the code you provide correctly implements the RNG it > purports to implement? Also, its RANDOM is about 8 times slower on my > CCL then the built in RANDOM. Plus, this provides an additional > dependency to manage. Finally, will this still be the "best" RNG in twenty > years? I'd expect implementations to change their RNG's as breakthroughs > are made, whereas no support is promised for your library.
> > Making such a determination is non-trivial. It requires either > > examining source code (and knowing what you're doing), contacting the > > vendor, or running statistical tests, any of which is almost certainly > > more effort than just downloading the single file containing the > > mrg32k3a code and using it.
> Yeah, but making this determination is also unnecessary for most > tasks. And your library is *not* universally better than the provided > RNGs (see above). I think your whole line of argumentation is based on > FUD. In fact, you should first show that the RNGs used by the > implementations *are* bad, for your argument to have any validity.
> > But this is of course not *necessarily* true. In CCL for example:
> So CCL apparently uses some variant of the multiple recursive generator > (same family as your library), while ACL, CMUCL, SBCL and ABCL use the > Mersenne twister which is very good on the performance and randomness > fronts. What are those bad implementations using broken RNGs? CLISP? > That's 64 bits of state you posted above, not nearly small enough to > assume some problem.
> All in all, I think your initial statement was _really_ FUD-ish. There are > too many misconceptions about Lisp floating around as is, for lispers > themselves to make new ones up from thin air.
