SERVING THE QUANTITATIVE FINANCE COMMUNITY

 
User avatar
PV
Topic Author
Posts: 3
Joined: January 8th, 2005, 12:23 pm

New Approximation to the Normal Distribution Quantile Function

February 3rd, 2010, 8:29 pm

hi,I hope this information is helpful, and even better useful, to people.For some recent work on a risk system, we needed a very fast way to approximate the inverse of the normal distribution CDF with "reasonable" accuracy. I found the following, which I couldn't find in the literature anywhere:http://arxiv.org/abs/1002.0567Definitely appreciate any comments.PV
 
User avatar
Costeanu
Posts: 189
Joined: December 29th, 2008, 5:33 pm

New Approximation to the Normal Distribution Quantile Function

February 4th, 2010, 6:39 pm

Very nice paper. Well explained too. I suppose if you want to increase the accuracy you only need to split the domain in more subdomains, and do the rational approximation on all of them. This wouldn't slow down the algorithm at all, it would only make it more difficult to implement. Taken to an extreme, this idea produces the fastest algorithm for the inverse of the normal CDF known to man: make a huge look-up table and interpolate between points. This idea has been implemented at some banks. Best,V.
 
User avatar
willsmith
Posts: 281
Joined: January 14th, 2008, 11:59 pm

New Approximation to the Normal Distribution Quantile Function

February 5th, 2010, 12:23 am

I am doing a course in Computational Finance with William Shaw of Kings College London. He's also into fast methods of approximating the normal (and student T) distribution and may well be interested in your paper. If you don't already know him I'm sure you'd get on well His Quantile approximation page is at http://www.mth.kcl.ac.uk/~shaww/web_pag ... ntiles.htm
Last edited by willsmith on February 4th, 2010, 11:00 pm, edited 1 time in total.
 
User avatar
spursfan
Posts: 893
Joined: October 7th, 2001, 3:43 pm

New Approximation to the Normal Distribution Quantile Function

February 5th, 2010, 8:05 am

I agree - my guess is that the Shaw & Brickman paper on branchless quantiles will be much better
 
User avatar
AVt
Posts: 1074
Joined: December 29th, 2001, 8:23 pm

New Approximation to the Normal Distribution Quantile Function

February 5th, 2010, 7:20 pm

Two comments (besides the other you received & the question why you are 'happy' with abs(error) ~ 1e-4):- It might be useful to append your Maple code (reporting on CPU time to find solutions) and say, that this error tolerance holds, if using double precision (since you initially compute with 60 Digits that is not clear).- You may save CPU time in Maple, if not using minimax, but a (rational) Chebyshev-Pade approximation (as you are experimenting anyway to find out ranges)
 
User avatar
PV
Topic Author
Posts: 3
Joined: January 8th, 2005, 12:23 pm

New Approximation to the Normal Distribution Quantile Function

February 7th, 2010, 9:07 pm

hi again guys,thanks for the good comments. It was encouraging and informative to receive them.Getting in touch with William Shaw is definitely on my to-do list. Interestingly, someone else (who knows both of us) also thinks that the two of us would get on.Quick reply to why we are happy with that level of accuracy is that it suffices for the accuracy of the results that are required (that's not meant to sound quite as tautological as I now fear it might): "reasonably" accurate but very fast is the objective.thanks again!PV
 
User avatar
PV
Topic Author
Posts: 3
Joined: January 8th, 2005, 12:23 pm

New Approximation to the Normal Distribution Quantile Function

February 10th, 2010, 10:01 am

oops,and that same person also berates me for underselling myself:there is also a branchless approximation in my paper (Section 3) which should compare well speed-wise with Shaw-Brickman on a GPU.And on a CPU, my branched approximation performs much better than theirs speed-wise.PV
 
User avatar
AVt
Posts: 1074
Joined: December 29th, 2001, 8:23 pm

New Approximation to the Normal Distribution Quantile Function

February 10th, 2010, 8:11 pm

Some remarks.These 'branchless' ('uniform' ? ) approximations for cdfN(x) = p usuallysuffer from p=0 (as in the A&S case or complementary p=1) or p = 1/2.In your case (where I think you need the negative and 0 < p < 1/2), i.e.for the rational approximation in t = sqrt(ln(1/p^2)) as in A&S, it canonly solve exactly cdfN(x) = 1/2 if your parameters are *not* chosenindependently.For example c0 in that case is an affine linear combination of the otherparams, c0 = sqrt(2*ln(2) + ... and having the other parameters fixedit will lead to absolute errors of ~ 0.00014 (for your choice).Thus you can not use minimax (as it you seemed you have done) that wayif you want small relative errors and invN(1/2) = 0 at the same time.The compromise in A&S is: a small absolute error on average leading toacceptable tails, but a relative mess in the very center.The other stuff I am aware of are the other way round: good in the center(including *exactness* for cdfN(x) = 1/2) and needing a tail-switch ifdesiring something better (well: why not ... that are the *rare* casesand if those are the main concern, then speedy computations are the veryleast problem).Some variant is: the error function erf and tanh 'look quite similar'(where arctan is very fast) and approximating their distinction (shouldcover -1 , 0 and +1 with some reasonable speed and moderate exactness),but never that did in deep as my interests are towards 'exactness'.I neither have Steinbrecher's article on recursion (which I would findinteresting from a mathematical point [having doubts about practicaluse, but it sounds aesthetical]) nor the other one.
 
rwang716
Posts: 12
Joined: July 18th, 2019, 6:18 am

Re: New Approximation to the Normal Distribution Quantile Function

July 30th, 2019, 12:44 pm

Does anyone have papers related to rational approximation of normal distribution?
I guess the uniform approximation would have to much error so the piecewise approximation is better?
 
User avatar
Cuchulainn
Posts: 59705
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

Re: New Approximation to the Normal Distribution Quantile Function

July 30th, 2019, 3:45 pm

Does anyone have papers related to rational approximation of normal distribution?
I guess the uniform approximation would have to much error so the piecewise approximation is better?
why do you think that?
 
rwang716
Posts: 12
Joined: July 18th, 2019, 6:18 am

Re: New Approximation to the Normal Distribution Quantile Function

July 30th, 2019, 11:02 pm

Have tried many uniform approximation formulas for normal distribution CDF function, none of them is accurate enough.
I guess by partition the x into different subintervals it would be much easier to approximate.
 
User avatar
Alan
Posts: 9785
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

Re: New Approximation to the Normal Distribution Quantile Function

July 30th, 2019, 11:24 pm

The late Graeme West, Wilmott mag, Fig. 2 quoting an alogorithm of Hart (accurate to machine double precision everywhere). 
 
rwang716
Posts: 12
Joined: July 18th, 2019, 6:18 am

Re: New Approximation to the Normal Distribution Quantile Function

July 30th, 2019, 11:46 pm

This paper looks like a piecewise rational approximation of cumulative normal distribution, isn’ it?
 
User avatar
Alan
Posts: 9785
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

Re: New Approximation to the Normal Distribution Quantile Function

July 31st, 2019, 3:14 am

You're welcome
 
User avatar
Cuchulainn
Posts: 59705
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

Re: New Approximation to the Normal Distribution Quantile Function

July 31st, 2019, 9:34 am

The late Graeme West, Wilmott mag, Fig. 2 quoting an alogorithm of Hart (accurate to machine double precision everywhere). 
Indeed. And it is implemented in Quantlib. I extensively compared Graeme's code with QL in my recent C++ book and I get exactly the same answers.
The original algorithm is due to Genz.

Done and dusted I would say.
ABOUT WILMOTT

PW by JB

Wilmott.com has been "Serving the Quantitative Finance Community" since 2001. Continued...


Twitter LinkedIn Instagram

JOBS BOARD

JOBS BOARD

Looking for a quant job, risk, algo trading,...? Browse jobs here...


GZIP: On