Random and whrandom

[Alex Martelli]

"Ross Lazarus" <rerla at channing.harvard.edu> wrote in message
news:3A79A9EB.701D1E96 at channing.harvard.edu...
> Nice - and I found the documentation at
> http://www.stecf.org/~npirzkal/python/rv/rv-ref.html
>
> Also of potential interest to fellow prng consumers who need real speed
> - http://www.sbc.su.se/~per/crng/ - gives about 6 million/sec from the
> mersenne twister cf 7600/sec from rv twister (rv running on a slower
> pentium).

Mersenne Twister looks like just the ticket when what you're
doing is "shuffling a sequence" (or "stirring" it, in crng
terms -- or, also, using 'choose' or 'sample' to get subsets
or subsequences, with or without repetition/permutation),
the point being that its huge period gives you a _chance_ of
selecting subsets/permutations/samples in a way that makes
all possible ones roughly equally-likely (but I don't think
this has ever been *proved* -- it's just that MT has some
*chance*, when RNG's with shorter periods clearly don't).

Speed can also become quite relevant here.

Say you're shuffling a deck of 52 cards -- there are about
8.0e+67 permutations (52!), and getting one permutation
requires about 50 random numbers (with the normal Knuth
approach).  A typical task in bridge studies is to deal
out a huge variety of deals and throw away all except those
meeting certain specified criteria -- and it's not unusual
for those criteria to have an a priori chance of, say, one
in a million, so one needs about 50 million random numbers
per each significant deal produced for study (at least
when such safe brute-force Montecarlo approaches are
used; clever accelerations are possible but run serious
risks of double-counting or subtle distortions if one is
not incredibly careful in setting conditions up).

This translates to about 8 seconds per significant deal
with crng, versus about 2 hours per deal with rv, with
the numbers you quote (actually, it WILL take, even in
the best case, a couple of milliseconds at least to study
and discard each deal produced, so the ratio is not all
that dramatic: 2000+ seconds per produced deal with
crng, vs almost 9000 with rv -- which is why one stays
motivated to produce the 'clever accelerations' above
mentioned, but that's another issue -- still, a 4:1
ratio *is* achievable for a brute force approach here).


Alex