Serving the Quantitative Finance Community

 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

Parallel RNG and distributed MC

February 6th, 2015, 10:50 pm

f(i,k) != f(i,k2) and f(i,k) != f(j,k) are good, but don't address the issue of WHERE in the cycle of 2^256 numbers that any given initialization starts at (if I've understood things correctly). Asked another way, how far apart are f(i,k) and f(i,k+1) in the cycle of 2^256 numbers?Is it ever possible that, for example, RN(RN(f(i,k))) = RN(f(j,l)), i≠j and k≠l, and that RN(RN(RN(f(i,k))) = RN(RN(f(j,l)) and so on because one cycle is following in the other cycle's footsteps with some lag.Or are you saying that the 2^256 cycle created by one initialization is random permutation (not a rotation) of every other possible cycle created by any other possible initialization?
 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

Parallel RNG and distributed MC

February 7th, 2015, 12:34 pm

Cool!So (f(i,j) and f(k,l) initialize completely independent RN streams as long as abs(i-k)+abs(j-l)>0?What about statistical comparisons of f(i,j), f(i+1,j), f(i,j+1)? Do changes in the first input have a different effect compared to changes in the second input?
 
User avatar
Cuchulainn
Posts: 20253
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Parallel RNG and distributed MC

February 7th, 2015, 6:41 pm

I am more interested in your new parallel one.Locks and mutexes suck. What I need is each thread on its own data stream. For this code, lock/mutex is ~ 8 times slower than OpenMP reduction clause.
Last edited by Cuchulainn on February 6th, 2015, 11:00 pm, edited 1 time in total.
 
User avatar
Cuchulainn
Posts: 20253
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Parallel RNG and distributed MC

February 7th, 2015, 6:42 pm

Let's say we want to generate a (large) matrix of random numbers. It's got to be done in parallel somehow. So, how to do it with a good speedup and no race conditions?
 
User avatar
Cuchulainn
Posts: 20253
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Parallel RNG and distributed MC

February 8th, 2015, 10:25 am

QuoteOriginally posted by: outrunAre you saying that openMP sums 128mln random number 8x faster than the code below? How many thread did you use? How many samples per thread?I think that's not possible, there is nearly zero overhead.I'm not saying that, exactly.What I hope to do is to get some time to test the two parallel RNGS (yours, pcaspers'), the latter documented by Matsumoto/Nishimura and QL. test caseLet's say we want to generate a (large) matrix of random numbers. It's got to be done in parallel somehow. So, how to do it with a good speedup and no race conditions?
Last edited by Cuchulainn on February 7th, 2015, 11:00 pm, edited 1 time in total.
 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

Parallel RNG and distributed MC

February 8th, 2015, 11:28 am

QuoteOriginally posted by: outrunQuoteOriginally posted by: Traden4AlphaCool!So (f(i,j) and f(k,l) initialize completely independent RN streams as long as abs(i-k)+abs(j-l)>0?What about statistical comparisons of f(i,j), f(i+1,j), f(i,j+1)? Do changes in the first input have a different effect compared to changes in the second input?I don't understand the abs? Maybe there is still a bit of misunderstanding?It's just a way of saying that at least one of the input variables is different between the two initializations.QuoteOriginally posted by: outrunSuppose you have the 256 bit counter 0, 1, 2, ..., 2^256-1Next you encrypt each counter number with an encryption key "k", and some encryption function f(). f() can be RSA, EAS,.. etcthis give f(0,k), f(1,k), f(2,k), ..., f(2^256-1,k)and it's a permutations of all the counter value 0 ... 2^256-1. now if you use a different value of k then you'll get a complete different sequence, a different permutation of all legal counter values.Interesting. So, if one created a 512 bit counter and split it into two halves, i and k, one would have an RNG that produces 2^512 RNs drawn from the space of 0 ... 2^256-1. I assume three fish passes all the tests for RNs.
 
User avatar
Cuchulainn
Posts: 20253
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Parallel RNG and distributed MC

February 8th, 2015, 4:39 pm

No skin off my nose, but has this become a discussion on the 'internals' of the method even there seems to be no extended published results on how to use the method and what the consequences are?Just sayin' This is a good starthttp://www.sitmo.com/article/parallel-random-n ... ator-in-c/
Last edited by Cuchulainn on February 7th, 2015, 11:00 pm, edited 1 time in total.