How to seed (random)? 
Author Message
 How to seed (random)?

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!


Tue, 21 May 2002 03:00:00 GMT  
 How to seed (random)?

Quote:

> 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



Tue, 21 May 2002 03:00:00 GMT  
 How to seed (random)?
R. Matthew Emerson schrieb:

Quote:
> > 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



Wed, 22 May 2002 03:00:00 GMT  
 How to seed (random)?


Quote:

>> 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?



Wed, 22 May 2002 03:00:00 GMT  
 How to seed (random)?

Quote:

> 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=HyperSpe...

Click on the first entry that comes up.

Robert



Wed, 22 May 2002 03:00:00 GMT  
 How to seed (random)?

Quote:




> >> 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...

Quote:
> 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.

--

  "One smaller motivation which, in part, stems from altruism is Microsoft-
   bashing." [Microsoft memo, see http://www.opensource.org/halloween1.html]



Wed, 22 May 2002 03:00:00 GMT  
 How to seed (random)?
Thanks to several for suggesting

        (setf *random-state* (make-random-state t))



Thu, 23 May 2002 03:00:00 GMT  
 How to seed (random)?


Quote:
> 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.



Thu, 23 May 2002 03:00:00 GMT  
 How to seed (random)?


Quote:


>> 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!


Fri, 24 May 2002 03:00:00 GMT  
 How to seed (random)?

Quote:

> 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))

--



Fri, 24 May 2002 03:00:00 GMT  
 How to seed (random)?

    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



Fri, 24 May 2002 03:00:00 GMT  
 How to seed (random)?


Quote:

>    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.

--

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.



Fri, 24 May 2002 03:00:00 GMT  
 How to seed (random)?




    >>
    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



Sat, 25 May 2002 03:00:00 GMT  
 How to seed (random)?

Quote:




> >    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.

--

  "One smaller motivation which, in part, stems from altruism is Microsoft-
   bashing." [Microsoft memo, see http://www.opensource.org/halloween1.html]



Sat, 25 May 2002 03:00:00 GMT  
 How to seed (random)?

Quote:


>     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

======================^^^^^^^^^^^^^^^^^^^

Quote:
> 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



Sat, 25 May 2002 03:00:00 GMT  
 
 [ 18 post ]  Go to page: [1] [2]

 Relevant Pages 

1. Best way to seed random numbers?

2. on seeding random number generators

3. Seeding the Random Number generator

4. Random Number with Seed value

5. Seeds for Random functions in SML

6. RANDOM seed ...

7. seeding slib's random number generator

8. random number seed?

9. random seed

10. module random: delay in "seeding"

11. seeds in gaussian random number generator

12. Seeds and one random number

 

 
Powered by phpBB® Forum Software