make-random-state
Peter Keller
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?
Thank you.
-pete
RG
Peter Keller <psi...@cs.wisc.edu> wrote:
Try using this:
http://www.ccs.neu.edu/home/dorai/notes/mrg32k3a.lisp
You'll almost certainly get better quality results than whatever your
implementation has built in.
rg
Pascal J. Bourguignon
(setf *random-state* (make-random-state *known-random-state-used-as-seed*))
Ah, yes, so you want to know how to make a known seed?
(defparameter *known-random-state-used-as-seed* (make-random-state t))
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/
--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.
Edmunds Cers
> 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
Edmunds Cers
> You'll almost certainly get better quality results than whatever your
> implementation has built in.
Why include this piece of FUD?
Peter Keller
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.
However, your post does have good value for the large set of why
people use random numbers.
Later,
-pete
Peter Keller
Thanks Pascal and Ron for your answers. One of your two options should
serve me well enough.
-pete
Tim Bradshaw
> How do I do this concept in ANSI Common Lisp?
random-states are printable and readable. So you do something like this:
(defun save-random-state (file &optional (state *random-state*))
(with-open-file (o file :direction :output
:if-does-not-exist :create
:if-exists :supersede)
(with-standard-io-syntax
(format o "~&;;; dumped ~D~%~S~%" (get-universal-time) state)
(values state file))))
(defun load-random-state (file)
(with-open-file (i file :direction :input)
(with-standard-io-syntax
(values (read i) file))))
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...
Tim Bradshaw
> 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.
Well, there doesn't have to be: random states are printable & readable,
so general Lisp goodness solves the problem for you...
Tim Bradshaw
> 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.
Pascal J. Bourguignon
> Edmunds Cers <edm...@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.
--
Pascal J. Bourguignon
> 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
Tamas K Papp
> 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.
Best,
Tamas
Rob Warnock
+---------------
| Pascal J. Bourguignon wrote:
| > % clall -r '(length (princ-to-string *random-state*))'
| > CMU Common Lisp --> 8180
|
| 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:
cmu> (type-of (kernel::random-state-state *random-state*))
(SIMPLE-ARRAY (UNSIGNED-BYTE 32) (627))
cmu> (write-to-string *random-state* :length 17)
"#S(RANDOM-STATE
:STATE #(0 2567483615 346 2853056914 3121738758 1783061201 246531220
1057894035 3928001630 1725175406 3905371508 311548950
2446379812 1643047629 2343570339 291180588 627126928 ...))"
cmu>
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:
"#S(RANDOM-STATE :STATE #(0 2567483615 346 2853056914 3121738758
1783061201 246531220 1057894035 3928001630
1725175406 3905371508 311548950 2446379812
1643047629 2343570339 291180588 627126928 ...))"
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. ;-}
-Rob
-----
Rob Warnock <rp...@rpw3.org>
627 26th Avenue <http://rpw3.org/>
San Mateo, CA 94403
Pascal J. Bourguignon
> 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
Rob Warnock
+---------------
| rp...@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.
RG
Edmunds Cers <edm...@laivas.lv> wrote:
> RG <rNOS...@flownet.com> writes:
>
> > 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.
rg
vanekl
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.
RG
RG <rNOS...@flownet.com> wrote:
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:
? (make-random-state)
#.(CCL::INITIALIZE-MRG31K3P-STATE ...
That looks promising. On the other hand, in CLisp:
[1]> (make-random-state)
#S(RANDOM-STATE
#*0001000011110011000000010110011100111010001100111110000000001110)
That, not so much.
rg
Edmunds Cers
> In article <rNOSPAMon-9531B...@hello.network>,
> RG <rNOS...@flownet.com> wrote:
>
>> In article <4d564903$0$1076$afc3...@read01.usenet4all.se>,
>> Edmunds Cers <edm...@laivas.lv> wrote:
>>
>> > RG <rNOS...@flownet.com> writes:
>> >
>> > > 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:
>
> ? (make-random-state)
> #.(CCL::INITIALIZE-MRG31K3P-STATE ...
>
> That looks promising. On the other hand, in CLisp:
>
> [1]> (make-random-state)
> #S(RANDOM-STATE
> #*0001000011110011000000010110011100111010001100111110000000001110)
>
> That, not so much.
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.
Juanjo
$ ecl -eval '(let ((*print-readably* t)) (print *random-state*))' -eval '(quit)'
#$#A(BASE-CHAR (5000) (#\r #\4 #\O #\/ #\Nul #\Nul #\Nul #\Nul #\U0085 #\Sub #\: #\U00AD #\Nul #\Nul #\Nul #\Nul #\" #\< #\U00B1 #\L #\Nul #\Nul #\Nul #\Nul #\" #\$ #\U00B0 #\L #\Nul #\Nul #\Nul #\Nul #\o #\Bel #\k #\F #\Nul #\Nul #\Nul #\Nul #\! #\U00ED #\9 #\k #\Nul #\Nul #\Nul #\Nul #\r #\U00B0 #\U00F5 #\U00FA #\Nul #\Nul [... rest omitted ...]
Tim Bradshaw
> 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.
RG
Edmunds Cers <edm...@laivas.lv> wrote:
Very well, I concede the point.
rg
Marco Antoniotti
> Pascal J. Bourguignon <p...@informatimago.com> wrote:
> +---------------
> | > 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.
>
LW (at least up to 6.x) has the MT RG in lispworks:make-mt-random-
state and lispworks:mt-random-state
--
MA