[prev in list] [next in list] [prev in thread] [next in thread] 

List:       openmcl-bug
Subject:    Re: [Bug-openmcl] Random generator
From:       Gary Byers <gb () clozure ! com>
Date:       2007-09-17 12:33:09
Message-ID: 20070917031128.M54799 () clozure ! com
[Download RAW message or body]



On Sat, 15 Sep 2007, Bernd Beuster wrote:

> A simple test for the choosen random implementation: the run length
> should be 2^31-2.

The sequence of values which CCL::%NEXT-RANDOM-SEED computes should
have that period.

The behavior of RANDOM depends on how RANDOM uses those values.
CCL::%NEXT-RANDOM-SEED should update a (MOD (1- (EXPT 2 31))) value to
the next item in that sequence, but CCL::%NEXT-RANDOM-SEED only
returns 16 of those 31 bits.  To obtain 60 random bits (in the (RANDOM
MOST-POSITIVE-FIXNUM) case), RANDOM has to call CCL::%NEXT-RANDOM-SEED
at least 4 times (It actually does so 5 times).  Depending on exactly
how those 4 or 5 16-bit values are used to compute a 60-bit value, the
period of (RANDOM MOST-POSITIVE-FIXNUM) may be more or less than the
period of the 31-bit seed; in general, we should get about half as
many 60-bit values before repetition as 31-bit values, since we have
to update the 31-bit seed at least twice per 60-bit value.

You were correct in noting that the seed wasn't being updated correctly
and therefore led to a much shorter sequence than it should have.  A
fix for that should be in CVS within the next hour.

I'd also agree that it's inefficient to be doing this 16 bits at
at a time on a 64 bit machine; that'll change in the next release.


>
>
> (defun random-run-length ( &optional (print t))
>   "Should be 2^31-2)"
>   (declare (optimize speed))
>   (loop with start fixnum = (random most-positive-fixnum)
>      for current fixnum = (random most-positive-fixnum)
>      for i fixnum from 1
>      until (= current start)
>      finally (return i)
>      do (when (and print (zerop (mod i 10000000))) (print i))))
>
>
> ? (random-run-length nil)
> 134217728
> ? (log * 2)
> 27.0
>
> Obviously not.
>
>
> -- 
> Bernd
>
>
>
>
> _______________________________________________
> Bug-openmcl mailing list
> Bug-openmcl@clozure.com
> http://clozure.com/mailman/listinfo/bug-openmcl
>
>

[prev in list] [next in list] [prev in thread] [next in thread]