Serving the Quantitative Finance Community

 
User avatar
MiloRambaldi
Posts: 1
Joined: July 26th, 2010, 12:27 am

sitmo C++ normal distribution

October 27th, 2014, 4:31 pm

QuoteOriginally posted by: Traden4AlphaQuoteOriginally posted by: MiloRambaldiQuoteOriginally posted by: Traden4Alpha[How do these systems encode more or less favorable combinations of the generic components? What if some RNGs interact badly with some distribution shaping algorithms so that they really are not suitable?If an RNG interacted badly with such an algorithm, wouldn't that be a serious enough flaw to warrant discontinuation of use of the random engine for anything?Maybe not. I'm thinking of the Neave effect interaction between LCG and BM. Ziggurat may also have an analog of this flaw but it's probably a lot lower in magnitude than in the case of BM. And I doubt the inverse-transform methods have Neave effect flaws.I'm not familiar with the Neave effect. However, LCG is one of the generators which is apparently no longer considered worth using by most. QuoteA flawless RNG is probably impossible and certainly not practical. In general, there seems be be a trade-off between speed and flaws. The nature of the application affects how the flaws affect end results and whether the flaws are acceptable or not. Maybe there's some combinations that are truly inferior on all possible performance dimensions but I'm not sure this is true.I guess all PRNGs are flawed by definition, since they are deterministic For serious applications though (e.g. like at CERN), from what I have heard they take unacceptable flaws in PRNG very seriously.
 
User avatar
Cuchulainn
Posts: 20250
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

sitmo C++ normal distribution

October 27th, 2014, 5:45 pm

QuoteI guess all PRNGs are flawed by definition, since they are deterministicWhy is this bad? QuoteFor serious applications though (e.g. like at CERN), from what I have heard they take unacceptable flaws in PRNG very seriously.What's the most 'serious' application at CERN? At CERN they have many sources for true randomness. BTW PRNG == pseudo rng, not parallel RNG, correct?
Last edited by Cuchulainn on October 26th, 2014, 11:00 pm, edited 1 time in total.
 
User avatar
Cuchulainn
Posts: 20250
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

sitmo C++ normal distribution

October 27th, 2014, 5:59 pm

Has anyone noticed performance of C++11 random_device?Does it use hardware?
Last edited by Cuchulainn on October 26th, 2014, 11:00 pm, edited 1 time in total.
 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

sitmo C++ normal distribution

October 27th, 2014, 7:27 pm

QuoteOriginally posted by: MiloRambaldiQuoteOriginally posted by: Traden4AlphaQuoteOriginally posted by: MiloRambaldiQuoteOriginally posted by: Traden4Alpha[How do these systems encode more or less favorable combinations of the generic components? What if some RNGs interact badly with some distribution shaping algorithms so that they really are not suitable?If an RNG interacted badly with such an algorithm, wouldn't that be a serious enough flaw to warrant discontinuation of use of the random engine for anything?Maybe not. I'm thinking of the Neave effect interaction between LCG and BM. Ziggurat may also have an analog of this flaw but it's probably a lot lower in magnitude than in the case of BM. And I doubt the inverse-transform methods have Neave effect flaws.I'm not familiar with the Neave effect. However, LCG is one of the generators which is apparently no longer considered worth using by most. Indeed! But LCG is much faster than anything else and has been the basis for rand() in a great many languages and systems. QuoteA flawless RNG is probably impossible and certainly not practical. In general, there seems be be a trade-off between speed and flaws. The nature of the application affects how the flaws affect end results and whether the flaws are acceptable or not. Maybe there's some combinations that are truly inferior on all possible performance dimensions but I'm not sure this is true.I guess all PRNGs are flawed by definition, since they are deterministic For serious applications though (e.g. like at CERN), from what I have heard they take unacceptable flaws in PRNG very seriously.As well they should although I'd be interested in how they define "unacceptable" and whether different users might have different definitions of "unacceptable". For example, Mersenne Twister is unacceptable for cryptographic applications but probably acceptable for many a numerical method.
 
User avatar
Cuchulainn
Posts: 20250
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

sitmo C++ normal distribution

October 27th, 2014, 7:54 pm

QuoteFor example, Mersenne Twister is unacceptable for cryptographic applications but probably acceptable for many a numerical method.Because if you get the seed and the algo you can reproduce the same numbers. Not with crypto algorithms.Depends on the requirements.Quote But LCG is much faster than anything else and has been the basis for rand() in a great many languages and systems. rand() js a horror show; they have a nice history lesson from IBM to PCs on the joys of rand().
Last edited by Cuchulainn on October 26th, 2014, 11:00 pm, edited 1 time in total.
 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

sitmo C++ normal distribution

October 27th, 2014, 8:04 pm

QuoteOriginally posted by: CuchulainnQuoteFor example, Mersenne Twister is unacceptable for cryptographic applications but probably acceptable for many a numerical method.Because if you get the seed and the algo you can reproduce the same numbers. Not with crypto algorithms.Depends on the requirements.It's worse than that. You don't need the seed. Some clever souls have determined that if you collect something like 624 consecutive values from the MT PRNG, you can derive the internal state of the RNG and determine the subsequent stream of values.QuoteQuote But LCG is much faster than anything else and has been the basis for rand() in a great many languages and systems. rand() js a horror show; they have a nice history lesson from IBM to PCs on the joys of rand().Indeed! But it is fast and convenient. I'm sure it's still useful as long as the application isn't susceptible to the hyperplane structure of LCG RNs.
 
User avatar
Cuchulainn
Posts: 20250
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

sitmo C++ normal distribution

October 27th, 2014, 8:14 pm

QuoteOriginally posted by: Traden4AlphaQuoteOriginally posted by: CuchulainnQuoteFor example, Mersenne Twister is unacceptable for cryptographic applications but probably acceptable for many a numerical method.Because if you get the seed and the algo you can reproduce the same numbers. Not with crypto algorithms.Depends on the requirements.It's worse than that. You don't need the seed. Some clever souls have determined that if you collect something like 624 consecutive values from the MT PRNG, you can derive the internal state of the RNG and determine the subsequent stream of values.QuoteQuote But LCG is much faster than anything else and has been the basis for rand() in a great many languages and systems. rand() js a horror show; they have a nice history lesson from IBM to PCs on the joys of rand().Indeed! But it is fast and convenient. I'm sure it's still useful as long as the application isn't susceptible to the hyperplane structure of LCG RNs.rand() is a load of junk according to many people. I am somewhat surprised by your statement.Do you remember the (best ever) discussion we had December 2008? rand() considered harmful
Last edited by Cuchulainn on October 26th, 2014, 11:00 pm, edited 1 time in total.
 
User avatar
Cuchulainn
Posts: 20250
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

sitmo C++ normal distribution

October 27th, 2014, 8:32 pm

QuoteOriginally posted by: outrunQuoteOriginally posted by: CuchulainnHas anyone noticed performance of C++11 random_device?Does it use hardware?from the standard:1. A random_device uniform random number generator produces non-deterministic random numbers.2. If implementation limitations prevent generating non-deterministic random numbers, the implementationmay employ a random number engine..i.e. you have no idea what it is! Most likely 2. on your windows machine and hence some unspecified algorithm. You can call the entropy() member function. If it returns 0 then it's using an algorithm (pseudo rng). If >0 then it's using entropy from your machine. It maintains a a pool or bits that it considers a random sources: things like the timing of your keyboard key presses, bytes moving in and out of your machine across your network interface.I know that, have read the two-line standard in the link. But the question is has anyone noticed it's kind of slow? I was thinking indeed that it might be keyboard etc. but it's not documented.Actually, point 2 above is missing some text"Note that std::random_device may be implemented in terms of a pseudo-random number engine if a non-deterministic source (e.g. a hardware device) is not available to the implementation. "In used it in a DE algorithm at each iteration and it slowed things down a lot. I think something is going on. VS2013. It's what is going on behind the scenes that is not documented!(?) Finally: how good are the numbers coming out of random_device?
Last edited by Cuchulainn on October 26th, 2014, 11:00 pm, edited 1 time in total.
 
User avatar
MiloRambaldi
Posts: 1
Joined: July 26th, 2010, 12:27 am

sitmo C++ normal distribution

October 27th, 2014, 9:51 pm

QuoteOriginally posted by: Traden4AlphaQuoteFor serious applications though (e.g. like at CERN), from what I have heard they take unacceptable flaws in PRNG very seriously.As well they should although I'd be interested in how they define "unacceptable" and whether different users might have different definitions of "unacceptable". For example, Mersenne Twister is unacceptable for cryptographic applications but probably acceptable for many a numerical method.I know next to nothing about CERN, but in general if you pretend that pseudo-random numbers are essentially random you may get nailed. From what I've read, the applied math literature is full of incorrect published results, where faulty random number generation led to false results and conclusions.
Last edited by MiloRambaldi on October 26th, 2014, 11:00 pm, edited 1 time in total.
 
User avatar
MiloRambaldi
Posts: 1
Joined: July 26th, 2010, 12:27 am

sitmo C++ normal distribution

October 27th, 2014, 9:54 pm

QuoteOriginally posted by: CuchulainnQuoteI guess all PRNGs are flawed by definition, since they are deterministicWhy is this bad? Seriously??QuoteQuoteFor serious applications though (e.g. like at CERN), from what I have heard they take unacceptable flaws in PRNG very seriously.What's the most 'serious' application at CERN? At CERN they have many sources for true randomness. BTW PRNG == pseudo rng, not parallel RNG, correct?Yes.
 
User avatar
Cuchulainn
Posts: 20250
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

sitmo C++ normal distribution

October 28th, 2014, 7:45 am

Boost has a bit more to say on random_device BoostQuoteClass random_device models a non-deterministic random number generator . It uses one or more implementation-defined stochastic processes to generate a sequence of uniformly distributed non-deterministic random numbers. For those environments where a non-deterministic random number generator is not available, class random_device must not be implemented. C++11QuoteNote that std::random_device may be implemented in terms of a pseudo-random number engine if a non-deterministic source (e.g. a hardware device) is not available to the implementation. Is there a problem here? From Boost RandomQuoteOn the Linux operating system, token is interpreted as a filesystem * path. It is assumed that this path denotes an operating system * pseudo-device which generates a stream of non-deterministic random * numbers. The pseudo-device should never signal an error or end-of-file. * Otherwise, @c std::ios_base::failure is thrown. By default, * \random_device uses the /dev/urandom pseudo-device to retrieve * the random numbers. Another option would be to specify the /dev/random * pseudo-device, which blocks on reads if the entropy pool has no more * random bits available. * * <b>Implementation Note for Windows</b> * * On the Windows operating system, token is interpreted as the name * of a cryptographic service provider. By default \random_device uses * MS_DEF_PROV. *Now I can understand a bit the slowness.
Last edited by Cuchulainn on October 27th, 2014, 11:00 pm, edited 1 time in total.