[Numpy-discussion] PRNGs and multi-threading

[Xavier Saint-Mleux]

Robert Kern wrote:
> On Fri, Aug 21, 2009 at 20:50, Sturla Molden<sturla at molden.no> wrote:
>   
>> Sturla Molden skrev:
>>     
>>> It seems there is a special version of the Mersenne Twister for this.
>>> The code is LGPL (annoying for SciPy but ok for me).
>>>       
>> http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/DC/dgene.pdf
>> <http://www.math.sci.hiroshima-u.ac.jp/%7Em-mat/MT/DC/dgene.pdf>
>>
>> Basically it encodes the thread-ids in the characteristic polynomial of
>> the MT, producing multiple small-period, independent MTs. That solves it
>> then. Too bad this is LGPL. It would be a very useful enhancement to
>> RandomState.
>>     
>
> I agree. It might be possible to re-implement it from the original
> papers, but it's a chunk of work.
>
>   
I use the following PRNG class, derived from RandomState, which allows a
PRNG to create multiple different sub-PRNGs in a deterministic way:

http://bazaar.launchpad.net/~piaget-dev/piaget/dev/annotate/head%3A/piaget/math/prng.py

It is written in Python and has an Apache license (BSD-like).  There is
no mathematical proof that different PRNGs will have states "far enough"
from each other, but it works well in practice (I've had bad surprises
using Python's random.jumpahead, which is not a real jumpahead).

Of course, the mathematically correct way would be to use a correct
jumpahead function, but all the implementations that I know of are GPL. 
A recent article about this is:

www.iro.umontreal.ca/~lecuyer/myftp/papers/jumpmt.pdf


Xavier Saint-Mleux