Can someone suggest a method of seeding the random number generator?
Say with the system clock? Or even with a user-supplied seed?
(I am using clisp, but a generic solution would be preferable.)
Thanks!
·······@grendel.csc.smith.edu (Joseph O'Rourke) writes:
> Can someone suggest a method of seeding the random number generator?
> Say with the system clock? Or even with a user-supplied seed?
> (I am using clisp, but a generic solution would be preferable.)
> Thanks!
See the documentation for *RANDOM-STATE* and MAKE-RANDOM-STATE in
the HyperSpec or in CLTL2.
-matt
R. Matthew Emerson schrieb:
> > Can someone suggest a method of seeding the random number generator?
> See the documentation for *RANDOM-STATE* and MAKE-RANDOM-STATE in
> the HyperSpec or in CLTL2.
CLtL2 just says "by some means (such as by a time-of-day-clock)".
The problem is that the random state type is opaque, so there
is probably no portable solution.
For a nonportable solution, it should be possible to fill
in some stuff (e.g. from /dev/random) directly.
There is a RFC (IIRC 1715) about getting real random information
in the first place.
I'd probably not rely on (make-random-state t) unless I know
exactly how it works.
Ralf
In article <··············@nightfly.apk.net>,
R. Matthew Emerson <···@nightfly.apk.net> wrote:
>·······@grendel.csc.smith.edu (Joseph O'Rourke) writes:
>
>> Can someone suggest a method of seeding the random number generator?
>
>See the documentation for *RANDOM-STATE* and MAKE-RANDOM-STATE in
>the HyperSpec or in CLTL2.
I know this will reveal my cluelessness, but I don't know what either
HyperSpec or CLTL2 is, so this advice is of little help to me.
What I am looking for is the equivalent of this C code:
srandom( (int) time((long *) 0 ) )
Is there not a standard Lisp equivalent?
Joseph O'Rourke wrote:
> I know this will reveal my cluelessness, but I don't know what either
> HyperSpec or CLTL2 is, so this advice is of little help to me.
It reveals that you are afraid of search engines:
http://www.altavista.com/cgi-bin/query?kl=XX&pg=q&text=yes&q=HyperSpec+or+CLTL2&search=Search
Click on the first entry that comes up.
Robert
·······@grendel.csc.smith.edu (Joseph O'Rourke) writes:
> In article <··············@nightfly.apk.net>,
> R. Matthew Emerson <···@nightfly.apk.net> wrote:
> >·······@grendel.csc.smith.edu (Joseph O'Rourke) writes:
> >
> >> Can someone suggest a method of seeding the random number generator?
> >
> >See the documentation for *RANDOM-STATE* and MAKE-RANDOM-STATE in
> >the HyperSpec or in CLTL2.
>
> I know this will reveal my cluelessness, but I don't know what either
> HyperSpec or CLTL2 is, so this advice is of little help to me.
The HyperSpec (see http://www.harlequin.com/books/HyperSpec/ ) can be
considered to be the electronic "equivalent" of the ANSI Common Lisp
standard (except for legal purposes). This will be very useful in
locating standard Lisp functionality...
> What I am looking for is the equivalent of this C code:
>
> srandom( (int) time((long *) 0 ) )
>
> Is there not a standard Lisp equivalent?
Well, this very heavily depends on what you would consider to be
"equivalent". Consider this excerpt from the HyperSpec:
---
Function MAKE-RANDOM-STATE
Syntax:
make-random-state &optional state => new-state
Arguments and Values:
state---a random state, or nil, or t. The default is nil.
new-state---a random state object.
Description:
Creates a fresh object of type random-state suitable for use as the value of
*random-state*.
If state is a random state object, the new-state is a copy[5] of that
object. If state is nil, the new-state is a copy[5] of the current random
state. If state is t, the new-state is a fresh random state object that has
been randomly initialized by some means.
---
Depending on your intended use of the RNG, this might be sufficient
(and if you initialize an RNG based on the system time, your
requirements for randomness can't be very strong, so the guarantee of
the standard seems equivalent to me):
(setf *random-state* (make-random-state t))
OTOH, your needs might be different, in which case some other solution
would be more appropriate. In this case I'd suggest you describe your
problem in more detail, since more information will be needed to offer
you sound advice (RNG use is plastered with pitfalls).
Hope this helps,
Regs, Pierre.
--
Pierre Mai <····@acm.org> PGP and GPG keys at your nearest Keyserver
"One smaller motivation which, in part, stems from altruism is Microsoft-
bashing." [Microsoft memo, see http://www.opensource.org/halloween1.html]
·······@grendel.csc.smith.edu (Joseph O'Rourke) writes:
> I know this will reveal my cluelessness, but I don't know what either
> HyperSpec or CLTL2 is, so this advice is of little help to me.
> What I am looking for is the equivalent of this C code:
>
> srandom( (int) time((long *) 0 ) )
>
> Is there not a standard Lisp equivalent?
Hyperspec: http://www.harlequin.com/education/books/HyperSpec/
Others pointed out (setf *random-state* (make-random-state t))
but I will point out a bit of background for this decision, quoting from
CLtL2 (Common Lisp: The Language, 2nd edition by Guy Steele), p. 367:
Rationale: Common Lisp purposely provides no way to initialize a
random-state object from a user-specified "seed." The reason for this is
that the number of bits of state information in a random-state object
may vary widely from one implementation to another, andd there is no
simple way to guarantee that any user-specified seed value will be
"random enough." Instead, the initialization of random-state objects is
left to the implementor in the case where the argument t is given to
make-random-state.
Tom speaking: There are really only two main reasons why one wants to
specify a seed to a random number generator. One is to make sure
different random sequences are produced and the other is to make sure
the same random sequences are produced (generally for testing and
debugging).
(make-random-state t) satisfies the first case, and the requirement that
random states be printable and readable means that one can save a random
state for a particular implementation and then reuse it to generate the
same sequence.
I should note parenthetically that the C-way of doing things limits the
type of random number generator since it must be completely controlled
from a single seed. In the unix version of ACL, the random-state object
is quite a bit more complex:
(make-random-state) =>
#S(RANDOM-STATE :SEED 45915826886865
:FIXSEED
#(292838224 300453347 347475097 373382476 158918294
252263726 276612119 251077989 245221432 142837729
186049712 217069510 241830490 231239439 340958910
79064728 187226669 261594818 268690954 159654018
157393673 255038057 129734822 233799131 198915715
206544584 239441641 316490271 85056615 180222754
194202340 117068541 210815334 137301708 76213387
125931783 193691770 193600957 228493387 65086363
250294545 383633659 412695004 330007712 304360146
22528118 202734409 354181197 357206213 400280516
348238659 359923114 318040546 206716114 331620676 8
39))
--
Thomas A. Russ, USC/Information Sciences Institute ···@isi.edu
>>>>> "Thomas" == Thomas A Russ <···@sevak.isi.edu> writes:
Thomas> I should note parenthetically that the C-way of doing
Thomas> things limits the type of random number generator since it
Thomas> must be completely controlled from a single seed. In the
Thomas> unix version of ACL, the random-state object is quite a
Thomas> bit more complex:
Note that the MT19937 random number generator in CMUCL can be
controlled via a single seed. It uses a simple linear-congruential
generator to generate the values used to initialize the state of the
mt19937 generator. (make-random-state) just basically uses the
current time to seed the LCG which then seeds the mt19937 generator.
Ray
In article <··············@rtp.ericsson.se>,
Raymond Toy <···@rtp.ericsson.se> wrote:
>>>>>> "Thomas" == Thomas A Russ <···@sevak.isi.edu> writes:
>
> Thomas> I should note parenthetically that the C-way of doing
> Thomas> things limits the type of random number generator since it
> Thomas> must be completely controlled from a single seed. In the
> Thomas> unix version of ACL, the random-state object is quite a
> Thomas> bit more complex:
>
>Note that the MT19937 random number generator in CMUCL can be
>controlled via a single seed. It uses a simple linear-congruential
>generator to generate the values used to initialize the state of the
>mt19937 generator. (make-random-state) just basically uses the
>current time to seed the LCG which then seeds the mt19937 generator.
But the difference is that the C specification limits implementors to
providing such a simple RNG, while the CL specification allows implementors
the lattitude to implement RNGs with many more bits of state than the word
size.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
>>>>> "Barry" == Barry Margolin <······@bbnplanet.com> writes:
Barry> In article <··············@rtp.ericsson.se>,
Barry> Raymond Toy <···@rtp.ericsson.se> wrote:
>>>>>>> "Thomas" == Thomas A Russ <···@sevak.isi.edu> writes:
>>
Thomas> I should note parenthetically that the C-way of doing
Thomas> things limits the type of random number generator since it
Thomas> must be completely controlled from a single seed. In the
Thomas> unix version of ACL, the random-state object is quite a
Thomas> bit more complex:
>>
>> Note that the MT19937 random number generator in CMUCL can be
>> controlled via a single seed. It uses a simple linear-congruential
>> generator to generate the values used to initialize the state of the
>> mt19937 generator. (make-random-state) just basically uses the
>> current time to seed the LCG which then seeds the mt19937 generator.
Barry> But the difference is that the C specification limits implementors to
Barry> providing such a simple RNG, while the CL specification allows implementors
Barry> the lattitude to implement RNGs with many more bits of state than the word
Barry> size.
Are we talking about the plain old rand in ANSI C? If so, then I
agree. If not, what about drand48 with 48 bits of state and the old
BSD random with 31 words of state? And, of course, mt19937 was given
by the authors as a C implementation.
Ray
Barry Margolin <······@bbnplanet.com> writes:
> In article <··············@rtp.ericsson.se>,
> Raymond Toy <···@rtp.ericsson.se> wrote:
> >>>>>> "Thomas" == Thomas A Russ <···@sevak.isi.edu> writes:
> >
> > Thomas> I should note parenthetically that the C-way of doing
> > Thomas> things limits the type of random number generator since it
> > Thomas> must be completely controlled from a single seed. In the
> > Thomas> unix version of ACL, the random-state object is quite a
> > Thomas> bit more complex:
> >
> >Note that the MT19937 random number generator in CMUCL can be
> >controlled via a single seed. It uses a simple linear-congruential
> >generator to generate the values used to initialize the state of the
> >mt19937 generator. (make-random-state) just basically uses the
> >current time to seed the LCG which then seeds the mt19937 generator.
>
> But the difference is that the C specification limits implementors to
> providing such a simple RNG, while the CL specification allows implementors
> the lattitude to implement RNGs with many more bits of state than the word
> size.
Note that CMUCL's MT19937[1] RNG _has_ many more bits of state than the
word size (which is how it achieves it's 2^19937 - 1 period size,
which would be fairly impossible to achieve with only 2^32 or 2^64
bits of state information ;). It just also provides a nice way to
seed the RNG based on less bits of information (if you use this way to
seed the RNG, you will of course only get <= 2^32 different RNG
streams, but each of those will still exhibit a period of 2^19937 -
1). Seed state space and RNG state space don't have to be identical.
OTOH your point is well taken. IMHO initializing RNGs based on system
time is only seldomly a wise choice, and C is forcing implementations
to do this, whereas ANSI CL gives implementations more lattitute, as
you say.
Regs, Pierre.
Footnotes:
[1] CMUCL's RNG implementation is based on the MT-19937 algorithm by
Matsumoto and Nishimura as published in ACM TOMACS 1/1999, p. 3-30.
--
Pierre Mai <····@acm.org> PGP and GPG keys at your nearest Keyserver
"One smaller motivation which, in part, stems from altruism is Microsoft-
bashing." [Microsoft memo, see http://www.opensource.org/halloween1.html]
Raymond Toy <···@rtp.ericsson.se> writes:
> >>>>> "Thomas" == Thomas A Russ <···@sevak.isi.edu> writes:
>
> Thomas> I should note parenthetically that the C-way of doing
> Thomas> things limits the type of random number generator since it
> Thomas> must be completely controlled from a single seed. In the
> Thomas> unix version of ACL, the random-state object is quite a
> Thomas> bit more complex:
>
> Note that the MT19937 random number generator in CMUCL can be
> controlled via a single seed. It uses a simple linear-congruential
> generator to generate the values used to initialize the state of the
> mt19937 generator. (make-random-state) just basically uses the
======================^^^^^^^^^^^^^^^^^^^
> current time to seed the LCG which then seeds the mt19937 generator.
I presume (and hope) that the flagged line was just a typo, and that
you meant (make-random-state t) instead.
There is a patch for each of Allegro CL versions 5.0 and 5.0.1
which implement the Mersenne Twister (M19937); it is an excellent
rng and I recommend it.
With or without the patch, the rng can be seeded by way of a single
time-based seed, using (make-random-state t). However, I would
suggest caution when programming for such randomness; time is not
always as random as you might expect:
USER(20): (compile (defun foo ()
(let (res)
(dotimes (i 10)
(push (make-random-state t) res))
res)))
FOO
NIL
NIL
USER(21): (foo)
(#S(RANDOM-STATE :MTI 624
:FIXSEED
#(1046521489 2188099357 2820244281 1800468901 103434785
1606551917 2454263113 4024680565 1788612273 1516748989
...))
#S(RANDOM-STATE :MTI 624
:FIXSEED
#(1046521489 2188099357 2820244281 1800468901 103434785
1606551917 2454263113 4024680565 1788612273 1516748989
...))
#S(RANDOM-STATE :MTI 624
:FIXSEED
#(1046521489 2188099357 2820244281 1800468901 103434785
1606551917 2454263113 4024680565 1788612273 1516748989
...))
#S(...) ...)
USER(22):
Note that because of the speed of compiled lisp code :-) :-) the
time value causes excactly the same seed array to be generated. One
way to at least make these random states different (though predictably
pseudorandom, and not truly random) is to sleep some amount of time
between iterations.
--
Duane Rettig Franz Inc. http://www.franz.com/ (www)
1995 University Ave Suite 275 Berkeley, CA 94704
Phone: (510) 548-3600; FAX: (510) 548-8253 ·····@Franz.COM (internet)
On 07 Dec 1999 10:36:36 -0800, Duane Rettig <·····@franz.com> wrote:
> Note that because of the speed of compiled lisp code :-) :-) the
> time value causes excactly the same seed array to be generated. One
> way to at least make these random states different (though predictably
> pseudorandom, and not truly random) is to sleep some amount of time
> between iterations.
Perhaps the code could sleep "a random" amount of time between iterations.
:-)
Seriously, though, couldn't you use the first random seed as a index to how
long to sleep between the generation of subsequent random seeds?
-- Don
_____________________________________________________________________________
Don Geddis ······@cadabra.com Phone 650-403-2220
Cadabra Inc. http://cadabra.com Fax 650-403-2201
1820 Gateway Drive, Suite 300, San Mateo, CA 94404 Main 650-403-2200
On 7 Dec 1999 22:52:18 GMT, Don Geddis <······@Cadabra.Com> wrote:
>On 07 Dec 1999 10:36:36 -0800, Duane Rettig <·····@franz.com> wrote:
>> Note that because of the speed of compiled lisp code :-) :-) the
>> time value causes excactly the same seed array to be generated. One
>> way to at least make these random states different (though predictably
>> pseudorandom, and not truly random) is to sleep some amount of time
>> between iterations.
>
>Perhaps the code could sleep "a random" amount of time between iterations.
>:-)
>
>Seriously, though, couldn't you use the first random seed as a index to how
>long to sleep between the generation of subsequent random seeds?
That would probably work, although it would probably be more effective
to pull some extra "source of randomness" in that doesn't require
waiting for a random amount of time...
--
A Linux machine! because a 486 is a terrible thing to waste!
-- <···@wintermute.ucr.edu> Joe Sloan
········@ntlug.org- <http://www.ntlug.org/~cbbrowne/crypto.html>
On 07 Dec 1999 10:36:36 -0800, Duane Rettig <·····@franz.com> wrote:
>With or without the patch, the rng can be seeded by way of a single
>time-based seed, using (make-random-state t). However, I would
>suggest caution when programming for such randomness; time is not
>always as random as you might expect...
... Example elided ...
>Note that because of the speed of compiled lisp code :-) :-) the
>time value causes excactly the same seed array to be generated. One
>way to at least make these random states different (though predictably
>pseudorandom, and not truly random) is to sleep some amount of time
>between iterations.
If that turned out to be an issue, I'd try to stir some other
"source of randomness" into the "seed pool."
Consider that Linux has a device, /dev/random, also implemented on
some other OSes (see: <http://www.openpgp.net/random/>,
<http://www.linuxdoc.org/LDP/khg/HyperNews/get/khg/234/1.html>, and
<http://www.geocities.com/SiliconValley/Code/4704/devr.html> for other
presentations) which collects into an "entropy pool" various sets of
"likely-to-be-truly-random" inputs such as clock intervals between
interrupts, orderings of network connections, and such, and stirs
using a secure hashing function.
Throwing in the time *combined with a few bits/bytes of /dev/random*
should be more satisfactory than merely tossing in the time...
--
:FATAL ERROR -- VECTOR OUT OF HILBERT SPACE
········@ntlug.org- <http://www.hex.net/~cbbrowne/lsf.html>
In article <··········@news.smith.edu>,
·······@grendel.csc.smith.edu (Joseph O'Rourke) wrote:
> Can someone suggest a method of seeding the random number generator?
> Say with the system clock? Or even with a user-supplied seed?
> (I am using clisp, but a generic solution would be preferable.)
> Thanks!
Hi,
This is a general reply - it's not connected with Lisp, but it is based
on some (fairly limited) experience of writing crypto code.
First, you need to know how much state you need to provide. This will
be (at least) the number of independet bits the generator can provide
(ie the number of bits after which, if you know the generator and know
the last output, you can predict the next value). You shouldn't use a
random number generator to generate a key with more bits than the size
of its state, for example.
Second, unless you know the platform you are deploying on well, and know
that you have a reliable random number source in hardware (/dev/random
or the LSB of a soundcard input *maybe*), you need data from outside the
program. The easiest approach is to use a file (although PGP has quite
a neat solution of asking the suer to type keys or move the mouse - my
bank's online service also uses the mouse, but for such a short time
that I am worried their security is a joke!).
The file should be of variable content (eg a mail file), and must
contain much more data than the size of the state you want to seed (even
if the format is irregular - and most files are not - text has a high
rate of redundancy; a rough guide is a factor of 8). Then, to generate
the random state, make a hash (or hashes, depending on the amount of
state you need) of the file.
For example, if you need 40 bytes of state, split the file in half and
hash each half with SHA1. Each hash is 20 bytes of state.
To give a little safety against the user providing the same file each
time the program is run, include the system time in the data hashed. If
you can control system shutdwn then you may be able to save the current
state at shutdown to use next time.
I realise this may be completely irrelevant if you're just seeding a
game - on the other hand, if I post this and someone corrects me, then I
can learn something too ;-)
Cheers,
Andrew
http://www.andrewcooke.free-online.co.uk/index.html
Sent via Deja.com http://www.deja.com/
Before you buy.
In article <············@nnrp1.deja.com>,
Andrew Cooke <······@andrewcooke.free-online.co.uk> wrote:
>In article <··········@news.smith.edu>,
> ·······@grendel.csc.smith.edu (Joseph O'Rourke) wrote:
>> Can someone suggest a method of seeding the random number generator? [...]
>if you're just seeding a
>game -
Close -- seeding the creation of a random environment for testing
motion planning algorithms. (setf *random-state* (make-random-state t))
is just fine for me.
Thanks again to all for so many knowledgeable replies!