Serving the Quantitative Finance Community

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

sitmo C++ normal distribution

October 21st, 2014, 1:31 pm

QuoteOriginally posted by: outrunQuoteOriginally posted by: Traden4AlphaQuoteOriginally posted by: outrunZiggurat: non-constant but bounded time, fast, needs multiple independent random uniform samplesAre you sure it's bounded? The code and pseudocode that's I've seen seems to be unbounded.I thought so too, but then I was surprised yesterday that it was bounded, ..until I double checked just now which shows that it's not bounded! Ziggurat -> unbounded.Btw, it's interesting to know that the C++11 standard dictates "a complexity of amortized constant number of invocations of the rng"i.e. unbounded time methods like rejection sampling are probably illegal! (depending on the meaning of amortized) The polar BM has a rejection rate of (1-pi/4) = 0.21, which is *very* highInteresting!Ziggurat is a rejection sampling method with a clever design to the rejection zone so that rejection is limited to the discrepancy between the actual distribution and a stair-step approximation of the distribution.
 
User avatar
Cuchulainn
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

sitmo C++ normal distribution

October 21st, 2014, 5:28 pm

It's an art at this moment.
 
User avatar
Cuchulainn
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

sitmo C++ normal distribution

October 24th, 2014, 11:24 am

Benchmark the Normal Quantile, William Shaw Included is cpp code with multi precision data type.
Last edited by Cuchulainn on October 23rd, 2014, 10:00 pm, edited 1 time in total.
 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

sitmo C++ normal distribution

October 25th, 2014, 12:18 pm

QuoteOriginally posted by: CuchulainnBenchmark the Normal Quantile, William Shaw Included is cpp code with multi precision data type.Thanks! These are some interesting inverse transform methods.
 
User avatar
Cuchulainn
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

sitmo C++ normal distribution

October 25th, 2014, 2:41 pm

I have also done some ODE stuff in Boost odeint based on Prof Shaw's "Quantile Mechanics" paper and I get what looks like accurate results by cross-checking with the cdf. How this compares to Ziggurat and how to compare them is a good question.
 
User avatar
MiloRambaldi
Posts: 1
Joined: July 26th, 2010, 12:27 am

sitmo C++ normal distribution

October 27th, 2014, 1:21 pm

QuoteOriginally posted by: CuchulainnQuoteOriginally posted by: MiloRambaldiQuoteOriginally posted by: outrunQuoteOriginally posted by: MiloRambaldiI was looking at QuantLib's implementation and it is closely tied to the MT19937 (Mersenne Twister) generator. That's a design flaw, they should have used orthogonal concepts and reuse standard concepts, abstract away specifics as much as possible. Now they can only eat their own spaghetti food. It's an old project, it's alway easy to judge in retrospect but e.g. Efficient C++ by Scott Meyers has been around for ages. QuoteIt only uses 24-bits of the MT output to avoid some correlation issue.Do you know if these issues have been resolved in boost? I cannot find the post you once made here about ziggurat quality issues.The issue seems to be with MT, not with ziggarat. MT is standardised algorithm (with some constants) which should be *identical* across implementations, so boost can't 'fix' MT, nor ziggurat, the combination is apparently invalid? It would be interesting if you have some more info about that issue?To be fair, QuantLib's polar Box-Muller appears to be well-designed with appropriate orthogonality and abstraction. Perhaps there is some reason that their Ziggurat hard-codes MT. I plan to look into this further very soon.Several possible reasons for putting BM into history:1. slow: it uses log, sqrt, sin, cos2. Peter Jaeckel in his book discusses nasty side-effects with this method; it goes haywire with pseudo-random algorithms.3. It is claimed that BM is mucho slower than Ziggurat, especially for large numbers of random numbers.Are these good reason for not using BM?QuoteThat's a design flaw, they should have used orthogonal concepts and reuse standard concepts, abstract away specifics as much as possible.In fairness, the QL code is shipping now.I all but stopped open source coding more than year ago due to (severe) financial distress. But I did add some speed comparison tests for various methods of normal univariate psuedo-random number generation, including QL Ziggurat and QL Polar Box-Muller and Boost and C++11 Box-Muller (using the basic method IIRC). I will try to dig it up this week since there is some interest here. outrun seems to have a point about the "design flaw" of QL hard-coding the MT engine for the Ziggurat generator. I looked at the code and the paper on Ziggurat that it was based on, and could not see any reason why other engines could not be used. On the other hand, IIRC QL's Ziggurat was the fastest. Also, the Ziggurat code was in the experimental folder of Quantlib-1.3 (I haven't checked the status in the new version 1.4).
 
User avatar
Cuchulainn
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

sitmo C++ normal distribution

October 27th, 2014, 3:15 pm

"Design flaw" is the wrong description. What he probably wants to say is that it can be made more customizable ("generic") by using a conforming interface. In a s/w project with budget the maintenance team would develop and ship the next version. The world is full of hard-coded stuff.Is a car on gas/petrol a design flaw or a feature? Let's not forget that QL is ~ 15 years old and C++11 is here. How time flies.
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, 3:18 pm

QuoteOriginally posted by: Cuchulainn"Design flaw" is the wrong description. What he probably wants to say is that it can be made more customizable ("generic") by using a conforming interface. In a s/w project with budget the maintenance team would develop and ship the next version.Is a car on gas/petrol a design flaw or a feature?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?
 
User avatar
Cuchulainn
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

sitmo C++ normal distribution

October 27th, 2014, 3:21 pm

QuoteOriginally posted by: Traden4AlphaQuoteOriginally posted by: Cuchulainn"Design flaw" is the wrong description. What he probably wants to say is that it can be made more customizable ("generic") by using a conforming interface. In a s/w project with budget the maintenance team would develop and ship the next version.Is a car on gas/petrol a design flaw or a feature?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?Of course, the maintenance team should have addressed this contingency in the next version. This can come as a customer bug report, or a formal feature in the next release.Another option is to leave the old stuff it is and develop a new one (not always optimal, copy and paste) but it you are in a hurry it works, otherwise the elegant solution remains on the drawing board.How long will it take before an actual solution is found? How many millions of developers out there on RNG? The problem is budget.
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, 3:28 pm

QuoteOriginally 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?
 
User avatar
Cuchulainn
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

sitmo C++ normal distribution

October 27th, 2014, 3:38 pm

QuoteOriginally 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?Depends; it is a show-stopper and a patch should be found asap. If not, stop paying maintenance fee.
 
User avatar
MiloRambaldi
Posts: 1
Joined: July 26th, 2010, 12:27 am

sitmo C++ normal distribution

October 27th, 2014, 3:45 pm

QuoteOriginally posted by: CuchulainnQuoteOriginally 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 a 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?Depends; it is a show-stopper and a patch should be found asap. If not, stop paying maintenance fee.Maintenance fee? patch? We must be discussing different topics. I meant that in T4A's scenario, he would probably have an uncovered a fatal flaw in the PRNG algorithm. There has been discussion here about some major "debacle" with faulty pseudo-random number generation. It more of a danger than a certain show-stopper.
 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

sitmo C++ normal distribution

October 27th, 2014, 3:50 pm

QuoteOriginally 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.A 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.
 
User avatar
Cuchulainn
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

sitmo C++ normal distribution

October 27th, 2014, 3:52 pm

QuoteOriginally posted by: MiloRambaldiQuoteOriginally posted by: CuchulainnQuoteOriginally 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 a 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?Depends; it is a show-stopper and a patch should be found asap. If not, stop paying maintenance fee.Maintenance fee? patch? We must be discussing different topics. I meant that in T4A's scenario, he would probably have an uncovered a fatal flaw in the PRNG algorithm. There has been discussion here about some major "debacle" with faulty pseudo-random number generation. It more of a danger than a certain show-stopper.I don't think we are, just different aspects of the same issue.It's a bit of software by someone to be used by someone else? In this case you are talking about code that does not meet specifications? Am I missing the point?Toyota's ciutches broke down! Dangerous, show-stopper or both? What happened?
Last edited by Cuchulainn on October 26th, 2014, 11:00 pm, edited 1 time in total.