numpy performance and random numbers

[Robert Kern]

On 2009-12-21 16:57 PM, r0g wrote:
> sturlamolden wrote:
>> On 19 Des, 16:20, Carl Johan Rehn<car... at gmail.com>  wrote:
>>
>>> How about mulit-core or (perhaps more exciting) GPU and CUDA? I must
>>> admit that I am extremely interested in trying the CUDA-alternative.
>>>
>>> Obviously, cuBLAS is not an option here, so what is the safest route
>>> for a novice parallel-programmer?
>>
>> The problem with PRNG is that they are iterative in nature, and
>> maintain global states. They are therefore very hard to vectorize. A
>> GPU will not help. The GPU has hundreds of computational cores that
>> can run kernels, but you only get to utilize one.
>>
>> Parallel PRNGs are an unsolved problem in computer science.
>
> Surely you could have as many totally independent cores as you like
> independently spitting out random bits whenever they feel like it to
> make an equally random bitstream?  would have thought the only issue
> would be ensuring high quality bitstream was used to seed each thread no?

No. For most quality PRNGs, all seeds are equal (with a few minor exceptions. 
E.g. for the Mersenne Twister, a state vector of all zeros will yield only 
zeros, but any nontrivial state vector puts the PRNG into the same orbit, just 
at different places). There is no notion of a "high quality seed". The problem 
is that during the run, the separate PRNGs may overlap, which will reduce the 
independence of the samples.

That said, the enormous length of the Mersenne Twister's period helps a lot. You 
can use an ungodly number of streams and run length without having a physically 
realizable chance of overlap. The chance of having a bug in your simulation code 
is overwhelmingly greater.

There are also algorithms that can initialize a given number of PRNGs with 
different parameters (*not* seeds) that are guaranteed not to overlap. No one 
has implemented this for numpy, yet.

-- 
Robert Kern

"I have come to believe that the whole world is an enigma, a harmless enigma
  that is made terrible by our own mad attempt to interpret it as though it had
  an underlying truth."
   -- Umberto Eco