This is the Matsumoto/Nishimura method. Anyone here uses it?

edit: irrelevant, sorry

QuoteOriginally posted by: CuchulainnThis is the Matsumoto/Nishimura method. Anyone here uses it?Intel does. Iirc setup is "slow". We prefer jump ahead, of course. Why?

QuoteOriginally posted by: quartzQuoteOriginally posted by: CuchulainnThis is the Matsumoto/Nishimura method. Anyone here uses it?Intel does. Iirc setup is "slow". We prefer jump ahead, of course. Why?I have no idea why you prefer jump ahead.

QuoteOriginally posted by: CuchulainnQuoteOriginally posted by: quartzQuoteOriginally posted by: CuchulainnThis is the Matsumoto/Nishimura method. Anyone here uses it?Intel does. Iirc setup is "slow". We prefer jump ahead, of course. Why?I have no idea why you prefer jump ahead.Try asking NAG. They also jump afaik, but with another algo. Short answer: flexibility (works for other generators too), speed (in shorter generators), code clarity, elegance, egocentrism. But you should have known, I haven't talked about much else here

QuoteOriginally posted by: quartzQuoteOriginally posted by: CuchulainnQuoteOriginally posted by: quartzQuoteOriginally posted by: CuchulainnThis is the Matsumoto/Nishimura method. Anyone here uses it?Intel does. Iirc setup is "slow". We prefer jump ahead, of course. Why?I have no idea why you prefer jump ahead.Try asking NAG. They also jump afaik, but with another algo. Short answer: flexibility (works for other generators too), speed (in shorter generators), code clarity, elegance, egocentrism. But you should have known, I haven't talked about much else here ;)I am looking for a black box implementation. Not the internals. Besides, Quinn 2004 claims that jump (aka? leapfrog) that correlations can become short-range in the parallel case. This rules them out.The specification/desired feature is: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? Quote code clarity, elegance, egocentrism.Can these be quantified? I don't even understand what they mean.Code clarity and RNG?

jump ahead is good, but does not work for mt, so I guess this is the best available alternative

QuoteI am looking for a black box implementation. Not the internals. Besides, Quinn 2004 claims that jump (aka? leapfrog) that correlations can become short-range in the parallel case. This rules them out.Afair Quinn was talking of LCGs, which do not even qualify as PRNGs nowadays. But correct me if I missed something here. Have not heard of issues with relatively modern generators. MT does indeed have some, but these are independent of parallelization.QuoteThe specification/desired feature is: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? There are some options around... Quote code clarity, elegance, egocentrism.Can these be quantified? I don't even understand what they mean.Code clarity and RNG?Easy to understand and maintain, at least for us, as we managed to factor "out" the complex part. I could explain more but would then have to kill you. But if you're ok with a black box then it's a non-issue.Maybe let's stop talking about our tech here, don't wanna misuse the forum. pm?

QuoteOriginally posted by: pcaspersjump ahead is good, but does not work for mt, so I guess this is the best available alternativeAny correlations detected with MT? Or what else is wrong?

QuoteOriginally posted by: outrunQuoteOriginally posted by: quartzQuoteOriginally posted by: pcaspersjump ahead is good, but does not work for mt, so I guess this is the best available alternativeAny correlations detected with MT? Or what else is wrong?Takes log(jump distance time) instead of O(1) to set it up?Not necessarily; but even in that case, since maximum distance is given by the generator, the corresponding constant would bound it down to O(1) anyway So it all reduces to comparing the two constants.

Why can't be jump ahead used for multi-threading? (I assume that's what MT stands for in quartz's post.) You could pre-generate a table of seeds from a master RNG upfront and feed them to RNGs in parallel threads. And going further that way, why not using the whole table of true random numbers? How much memory would it take? 64 (double) * 10^6 paths * 100 steps ~ 1 GB can be stored in RAM. Or is it still too slow to read, which could suggest why Intel uses the algorithm mentioned by OP on their processors' with large cache - they have RNG code in the cache? Then why couldn't one sequentially put my table of pregenerated/true random numbers into cache to make it even faster? If anyone can and has patience to answer my questions/stream of consciousness, I'll be grateful.

QuoteOriginally posted by: katastrofaWhy can't be jump ahead used for multi-threading? (I assume that's what MT stands for in quartz's post.) You could pre-generate a table of seeds from a master RNG upfront and feed them to RNGs in parallel threads. And going further that way, why not using the whole table of true random numbers? How much memory would it take? 64 (double) * 10^6 paths * 100 steps ~ 1 GB can be stored in RAM. Or is it still too slow to read, which could suggest why Intel uses the algorithm mentioned by OP on their processors' with large cache - they have RNG code in the cache? Then why couldn't one sequentially put my table of pregenerated/true random numbers into cache to make it even faster? If anyone can and has patience to answer my questions/stream of consciousness, I'll be grateful.I like this line of reasoning. The design or 'pattern' seems to prefetch/precompute all the random numbers and then use them by the individual threads. This approach will increase the serial fraction and probably kill speedup. And a lot of memory consumption.I think the above is a Geometric Decomposition patternWhat do you think of this? another 'in-between' solution is to have one (or a couple) thread to generate RNs and the other threads to use the generated rns on a need-be/just in time basis. This is the well-known Producer-Consumer pattern. The arrays of rns are put into a synchonising queue. Advantage: thread-safe, no correlation. Possible disadvantage: load balancing.An example from @MikeJuniperHill is CopulaIt shows exactly what I want to do. It's in C# but patterns are language-independent.This is the approach I will also take in the short term. Run it, measure speedup etc.Producer Consumer is supported in TBB, PPL etc.QuoteBecause 10^6 is not enough? Depends on the problem. Sometimes yes, sometimes no.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? Do parallel loops; each thread in loop is a consumer and gets rns from the synchronized queue. That should do it?