Help understanding random_integer lisp code

Matthew, %RANDOM-INTEGER consumes the stream of chunks generated
by RANDOM-CHUNK, which is where all the MT algorithmic stuff is located.
The bit-mungeing in %RANDOM-INTEGER is just to construct a return
value which has a different number of bits than a chunk.

HTH

Robert Dodier

On 5/18/11, Matthew Gwynne <mathew.gwynne at gmail.com> wrote:
> Hi,
>
> I was wondering if anyone could help me understand what is going on in
> the function below:
>
> (defun %random-integer (arg state)
>   "Generates an integer greater than or equal to zero and less than Arg.
>   Successive chunks are concatenated without overlap to construct integers
>   larger than a single chunk. The return value has this property:
>   If two integers are generated from the same state with Arg equal to
> 2^m and 2^n,
>   respectively, then bit k is the same in both integers for 0 <= k <
> min(m,n).
>   Each call to %RANDOM-INTEGER consumes at least one chunk; bits left over
>   from previous chunks are not re-used."
>   (declare (type (integer 1) arg) (type random-state state))
>     (do*
>       ((nchunks (ceiling (integer-length (1- arg))
> random-chunk-length) (1- nchunks))
>         (new-bits 0 (random-chunk state))
>         (bits 0 (logior bits (ash new-bits shift)))
>         (shift 0 (+ shift random-chunk-length)))
>       ((= 0 nchunks)
>         (rem bits arg))))
>
> I've been looking at the lisp code for the random_integer function at
> maxima-5.21.1/src/rand-mt19937.lisp (above), trying to understand
> exactly what it is doing and how it matches up to the MT19937
> specification.
>
> Specifically, I'm having trouble deciphering how the shifts and xors
> and so on relate to the tempering function defined in the original
> paper (http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/mt.pdf
> - page 6):
>
> y := x + (x >> u)
> y := y + ((y << s) AND b)
> y := y + ((y << t) AND c)
> z := y + (y >> l);
>
> If anyone could point me towards the relevant definitions, or perhaps
> provide the equivalent Maxima/pseudo-code for random-integer, that
> would be fantastic!
>
> I'd like to compare this random number generator to that implemented
> in the boost system (for reproducibility), and so need to get a
> thorough understanding of both.
>
> Thanks in advance!
>
> Matthew Gwynne
> http://cs.swan.ac.uk/~csmg/
> _______________________________________________
> Maxima mailing list
> Maxima at math.utexas.edu
> http://www.math.utexas.edu/mailman/listinfo/maxima
>