Debian Codegraph @

third-party/boost-math/include/boost/math/special_functions/detail/t_distribution_inv.hpp

raw
1 // Copyright John Maddock 2007.
2 // Copyright Paul A. Bristow 2007
3 // Use, modification and distribution are subject to the
4 // Boost Software License, Version 1.0. (See accompanying file
5 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6
7 #ifndef BOOST_MATH_SF_DETAIL_INV_T_HPP
8 #define BOOST_MATH_SF_DETAIL_INV_T_HPP
9
10 #ifdef _MSC_VER
11 #pragma once
12 #endif
13
14 #include <boost/math/tools/config.hpp>
15 #include <boost/math/tools/type_traits.hpp>
16 #include <boost/math/tools/numeric_limits.hpp>
17 #include <boost/math/special_functions/cbrt.hpp>
18 #include <boost/math/special_functions/round.hpp>
19 #include <boost/math/special_functions/trunc.hpp>
20
21 namespace boost{ namespace math{ namespace detail{
22
23 //
24 // The main method used is due to Hill:
25 //
26 // G. W. Hill, Algorithm 396, Student's t-Quantiles,
27 // Communications of the ACM, 13(10): 619-620, Oct., 1970.
28 //
29 template <class T, class Policy>
30 BOOST_MATH_GPU_ENABLED T inverse_students_t_hill(T ndf, T u, const Policy& pol)
31 {
32 BOOST_MATH_STD_USING
33 BOOST_MATH_ASSERT(u <= 0.5);
34
35 T a, b, c, d, q, x, y;
36
37 if (ndf > 1e20f)
38 return -boost::math::erfc_inv(2 * u, pol) * constants::root_two<T>();
39
40 a = 1 / (ndf - 0.5f);
41 b = 48 / (a * a);
42 c = ((20700 * a / b - 98) * a - 16) * a + 96.36f;
43 d = ((94.5f / (b + c) - 3) / b + 1) * sqrt(a * constants::pi<T>() / 2) * ndf;
44 y = pow(d * 2 * u, 2 / ndf);
45
46 if (y > (0.05f + a))
47 {
48 //
49 // Asymptotic inverse expansion about normal:
50 //
51 x = -boost::math::erfc_inv(2 * u, pol) * constants::root_two<T>();
52 y = x * x;
53
54 if (ndf < 5)
55 c += 0.3f * (ndf - 4.5f) * (x + 0.6f);
56 c += (((0.05f * d * x - 5) * x - 7) * x - 2) * x + b;
57 y = (((((0.4f * y + 6.3f) * y + 36) * y + 94.5f) / c - y - 3) / b + 1) * x;
58 y = boost::math::expm1(a * y * y, pol);
59 }
60 else
61 {
62 y = static_cast<T>(((1 / (((ndf + 6) / (ndf * y) - 0.089f * d - 0.822f)
63 * (ndf + 2) * 3) + 0.5 / (ndf + 4)) * y - 1)
64 * (ndf + 1) / (ndf + 2) + 1 / y);
65 }
66 q = sqrt(ndf * y);
67
68 return -q;
69 }
70 //
71 // Tail and body series are due to Shaw:
72 //
73 // www.mth.kcl.ac.uk/~shaww/web_page/papers/Tdistribution06.pdf
74 //
75 // Shaw, W.T., 2006, "Sampling Student's T distribution - use of
76 // the inverse cumulative distribution function."
77 // Journal of Computational Finance, Vol 9 Issue 4, pp 37-73, Summer 2006
78 //
79 template <class T, class Policy>
80 BOOST_MATH_GPU_ENABLED T inverse_students_t_tail_series(T df, T v, const Policy& pol)
81 {
82 BOOST_MATH_STD_USING
83 // Tail series expansion, see section 6 of Shaw's paper.
84 // w is calculated using Eq 60:
85 T w = boost::math::tgamma_delta_ratio(df / 2, constants::half<T>(), pol)
86 * sqrt(df * constants::pi<T>()) * v;
87 // define some variables:
88 T np2 = df + 2;
89 T np4 = df + 4;
90 T np6 = df + 6;
91 //
92 // Calculate the coefficients d(k), these depend only on the
93 // number of degrees of freedom df, so at least in theory
94 // we could tabulate these for fixed df, see p15 of Shaw:
95 //
96 T d[7] = { 1, };
97 d[1] = -(df + 1) / (2 * np2);
98 np2 *= (df + 2);
99 d[2] = -df * (df + 1) * (df + 3) / (8 * np2 * np4);
100 np2 *= df + 2;
101 d[3] = -df * (df + 1) * (df + 5) * (((3 * df) + 7) * df -2) / (48 * np2 * np4 * np6);
102 np2 *= (df + 2);
103 np4 *= (df + 4);
104 d[4] = -df * (df + 1) * (df + 7) *
105 ( (((((15 * df) + 154) * df + 465) * df + 286) * df - 336) * df + 64 )
106 / (384 * np2 * np4 * np6 * (df + 8));
107 np2 *= (df + 2);
108 d[5] = -df * (df + 1) * (df + 3) * (df + 9)
109 * (((((((35 * df + 452) * df + 1573) * df + 600) * df - 2020) * df) + 928) * df -128)
110 / (1280 * np2 * np4 * np6 * (df + 8) * (df + 10));
111 np2 *= (df + 2);
112 np4 *= (df + 4);
113 np6 *= (df + 6);
114 d[6] = -df * (df + 1) * (df + 11)
115 * ((((((((((((945 * df) + 31506) * df + 425858) * df + 2980236) * df + 11266745) * df + 20675018) * df + 7747124) * df - 22574632) * df - 8565600) * df + 18108416) * df - 7099392) * df + 884736)
116 / (46080 * np2 * np4 * np6 * (df + 8) * (df + 10) * (df +12));
117 //
118 // Now bring everything together to provide the result,
119 // this is Eq 62 of Shaw:
120 //
121 T rn = sqrt(df);
122 T div = pow(rn * w, 1 / df);
123 T power = div * div;
124 T result = tools::evaluate_polynomial<7, T, T>(d, power);
125 result *= rn;
126 result /= div;
127 return -result;
128 }
129
130 template <class T, class Policy>
131 BOOST_MATH_GPU_ENABLED T inverse_students_t_body_series(T df, T u, const Policy& pol)
132 {
133 BOOST_MATH_STD_USING
134 //
135 // Body series for small N:
136 //
137 // Start with Eq 56 of Shaw:
138 //
139 T v = boost::math::tgamma_delta_ratio(df / 2, constants::half<T>(), pol)
140 * sqrt(df * constants::pi<T>()) * (u - constants::half<T>());
141 //
142 // Workspace for the polynomial coefficients:
143 //
144 T c[11] = { 0, 1, };
145 //
146 // Figure out what the coefficients are, note these depend
147 // only on the degrees of freedom (Eq 57 of Shaw):
148 //
149 T in = 1 / df;
150 c[2] = static_cast<T>(0.16666666666666666667 + 0.16666666666666666667 * in);
151 c[3] = static_cast<T>((0.0083333333333333333333 * in
152 + 0.066666666666666666667) * in
153 + 0.058333333333333333333);
154 c[4] = static_cast<T>(((0.00019841269841269841270 * in
155 + 0.0017857142857142857143) * in
156 + 0.026785714285714285714) * in
157 + 0.025198412698412698413);
158 c[5] = static_cast<T>((((2.7557319223985890653e-6 * in
159 + 0.00037477954144620811287) * in
160 - 0.0011078042328042328042) * in
161 + 0.010559964726631393298) * in
162 + 0.012039792768959435626);
163 c[6] = static_cast<T>(((((2.5052108385441718775e-8 * in
164 - 0.000062705427288760622094) * in
165 + 0.00059458674042007375341) * in
166 - 0.0016095979637646304313) * in
167 + 0.0061039211560044893378) * in
168 + 0.0038370059724226390893);
169 c[7] = static_cast<T>((((((1.6059043836821614599e-10 * in
170 + 0.000015401265401265401265) * in
171 - 0.00016376804137220803887) * in
172 + 0.00069084207973096861986) * in
173 - 0.0012579159844784844785) * in
174 + 0.0010898206731540064873) * in
175 + 0.0032177478835464946576);
176 c[8] = static_cast<T>(((((((7.6471637318198164759e-13 * in
177 - 3.9851014346715404916e-6) * in
178 + 0.000049255746366361445727) * in
179 - 0.00024947258047043099953) * in
180 + 0.00064513046951456342991) * in
181 - 0.00076245135440323932387) * in
182 + 0.000033530976880017885309) * in
183 + 0.0017438262298340009980);
184 c[9] = static_cast<T>((((((((2.8114572543455207632e-15 * in
185 + 1.0914179173496789432e-6) * in
186 - 0.000015303004486655377567) * in
187 + 0.000090867107935219902229) * in
188 - 0.00029133414466938067350) * in
189 + 0.00051406605788341121363) * in
190 - 0.00036307660358786885787) * in
191 - 0.00031101086326318780412) * in
192 + 0.00096472747321388644237);
193 c[10] = static_cast<T>(((((((((8.2206352466243297170e-18 * in
194 - 3.1239569599829868045e-7) * in
195 + 4.8903045291975346210e-6) * in
196 - 0.000033202652391372058698) * in
197 + 0.00012645437628698076975) * in
198 - 0.00028690924218514613987) * in
199 + 0.00035764655430568632777) * in
200 - 0.00010230378073700412687) * in
201 - 0.00036942667800009661203) * in
202 + 0.00054229262813129686486);
203 //
204 // The result is then a polynomial in v (see Eq 56 of Shaw):
205 //
206 return tools::evaluate_odd_polynomial<11, T, T>(c, v);
207 }
208
209 template <class T, class Policy>
210 BOOST_MATH_GPU_ENABLED T inverse_students_t(T df, T u, T v, const Policy& pol, bool* pexact = nullptr)
211 {
212 //
213 // df = number of degrees of freedom.
214 // u = probability.
215 // v = 1 - u.
216 // l = lanczos type to use.
217 //
218 BOOST_MATH_STD_USING
219 bool invert = false;
220 T result = 0;
221 if(pexact)
222 *pexact = false;
223 if(u > v)
224 {
225 // function is symmetric, invert it:
226 BOOST_MATH_GPU_SAFE_SWAP(u, v);
227 invert = true;
228 }
229 if((floor(df) == df) && (df < 20))
230 {
231 //
232 // we have integer degrees of freedom, try for the special
233 // cases first:
234 //
235 T tolerance = ldexp(1.0f, (2 * policies::digits<T, Policy>()) / 3);
236
237 switch(itrunc(df, Policy()))
238 {
239 case 1:
240 {
241 //
242 // df = 1 is the same as the Cauchy distribution, see
243 // Shaw Eq 35:
244 //
245 if(u == 0.5)
246 result = 0;
247 else
248 result = -cos(constants::pi<T>() * u) / sin(constants::pi<T>() * u);
249 if(pexact)
250 *pexact = true;
251 break;
252 }
253 case 2:
254 {
255 //
256 // df = 2 has an exact result, see Shaw Eq 36:
257 //
258 result =(2 * u - 1) / sqrt(2 * u * v);
259 if(pexact)
260 *pexact = true;
261 break;
262 }
263 case 4:
264 {
265 //
266 // df = 4 has an exact result, see Shaw Eq 38 & 39:
267 //
268 T alpha = 4 * u * v;
269 T root_alpha = sqrt(alpha);
270 T r = 4 * cos(acos(root_alpha) / 3) / root_alpha;
271 T x = sqrt(r - 4);
272 result = u - 0.5f < 0 ? (T)-x : x;
273 if(pexact)
274 *pexact = true;
275 break;
276 }
277 case 6:
278 {
279 //
280 // We get numeric overflow in this area:
281 //
282 if(u < 1e-150)
283 return (invert ? -1 : 1) * inverse_students_t_hill(df, u, pol);
284 //
285 // Newton-Raphson iteration of a polynomial case,
286 // choice of seed value is taken from Shaw's online
287 // supplement:
288 //
289 T a = 4 * (u - u * u);//1 - 4 * (u - 0.5f) * (u - 0.5f);
290 T b = boost::math::cbrt(a, pol);
291 static const T c = static_cast<T>(0.85498797333834849467655443627193);
292 T p = 6 * (1 + c * (1 / b - 1));
293 T p0;
294 do{
295 T p2 = p * p;
296 T p4 = p2 * p2;
297 T p5 = p * p4;
298 p0 = p;
299 // next term is given by Eq 41:
300 p = 2 * (8 * a * p5 - 270 * p2 + 2187) / (5 * (4 * a * p4 - 216 * p - 243));
301 }while(fabs((p - p0) / p) > tolerance);
302 //
303 // Use Eq 45 to extract the result:
304 //
305 p = sqrt(p - df);
306 result = (u - 0.5f) < 0 ? (T)-p : p;
307 break;
308 }
309 #if 0
310 //
311 // These are Shaw's "exact" but iterative solutions
312 // for even df, the numerical accuracy of these is
313 // rather less than Hill's method, so these are disabled
314 // for now, which is a shame because they are reasonably
315 // quick to evaluate...
316 //
317 case 8:
318 {
319 //
320 // Newton-Raphson iteration of a polynomial case,
321 // choice of seed value is taken from Shaw's online
322 // supplement:
323 //
324 static const T c8 = 0.85994765706259820318168359251872L;
325 T a = 4 * (u - u * u); //1 - 4 * (u - 0.5f) * (u - 0.5f);
326 T b = pow(a, T(1) / 4);
327 T p = 8 * (1 + c8 * (1 / b - 1));
328 T p0 = p;
329 do{
330 T p5 = p * p;
331 p5 *= p5 * p;
332 p0 = p;
333 // Next term is given by Eq 42:
334 p = 2 * (3 * p + (640 * (160 + p * (24 + p * (p + 4)))) / (-5120 + p * (-2048 - 960 * p + a * p5))) / 7;
335 }while(fabs((p - p0) / p) > tolerance);
336 //
337 // Use Eq 45 to extract the result:
338 //
339 p = sqrt(p - df);
340 result = (u - 0.5f) < 0 ? -p : p;
341 break;
342 }
343 case 10:
344 {
345 //
346 // Newton-Raphson iteration of a polynomial case,
347 // choice of seed value is taken from Shaw's online
348 // supplement:
349 //
350 static const T c10 = 0.86781292867813396759105692122285L;
351 T a = 4 * (u - u * u); //1 - 4 * (u - 0.5f) * (u - 0.5f);
352 T b = pow(a, T(1) / 5);
353 T p = 10 * (1 + c10 * (1 / b - 1));
354 T p0;
355 do{
356 T p6 = p * p;
357 p6 *= p6 * p6;
358 p0 = p;
359 // Next term given by Eq 43:
360 p = (8 * p) / 9 + (218750 * (21875 + 4 * p * (625 + p * (75 + 2 * p * (5 + p))))) /
361 (9 * (-68359375 + 8 * p * (-2343750 + p * (-546875 - 175000 * p + 8 * a * p6))));
362 }while(fabs((p - p0) / p) > tolerance);
363 //
364 // Use Eq 45 to extract the result:
365 //
366 p = sqrt(p - df);
367 result = (u - 0.5f) < 0 ? -p : p;
368 break;
369 }
370 #endif
371 default:
372 goto calculate_real;
373 }
374 }
375 else
376 {
377 calculate_real:
378 if(df > 0x10000000)
379 {
380 result = -boost::math::erfc_inv(2 * u, pol) * constants::root_two<T>();
381 if((pexact) && (df >= 1e20))
382 *pexact = true;
383 }
384 else if(df < 3)
385 {
386 //
387 // Use a roughly linear scheme to choose between Shaw's
388 // tail series and body series:
389 //
390 T crossover = 0.2742f - df * 0.0242143f;
391 if(u > crossover)
392 {
393 result = boost::math::detail::inverse_students_t_body_series(df, u, pol);
394 }
395 else
396 {
397 result = boost::math::detail::inverse_students_t_tail_series(df, u, pol);
398 }
399 }
400 else
401 {
402 //
403 // Use Hill's method except in the extreme tails
404 // where we use Shaw's tail series.
405 // The crossover point is roughly exponential in -df:
406 //
407 int u_exp;
408 T m_exp = frexp(u, &u_exp);
409 // The following is equivalent to: u > 2^df/-0.654
410 if(m_exp > 0 && u_exp < df / 0.654f)
411 {
412 result = boost::math::detail::inverse_students_t_hill(df, u, pol);
413 }
414 else
415 {
416 result = boost::math::detail::inverse_students_t_tail_series(df, u, pol);
417 }
418 }
419 }
420 return invert ? (T)-result : result;
421 }
422
423 template <class T, class Policy>
424 BOOST_MATH_GPU_ENABLED inline T find_ibeta_inv_from_t_dist(T a, T p, T /*q*/, T* py, const Policy& pol)
425 {
426 T u = p / 2;
427 T v = 1 - u;
428 T df = a * 2;
429 T t = boost::math::detail::inverse_students_t(df, u, v, pol);
430 *py = t * t / (df + t * t);
431 return df / (df + t * t);
432 }
433
434 // NVRTC requires this forward decl because there is a header cycle between here and ibeta_inverse.hpp
435 #ifdef BOOST_MATH_HAS_NVRTC
436
437 } // Namespace detail
438
439 template <class T1, class T2, class T3, class T4, class Policy>
440 BOOST_MATH_GPU_ENABLED inline typename tools::promote_args<T1, T2, T3, T4>::type
441 ibeta_inv(T1 a, T2 b, T3 p, T4* py, const Policy& pol);
442
443 namespace detail {
444
445 #endif
446
447 template <class T, class Policy>
448 BOOST_MATH_GPU_ENABLED inline T fast_students_t_quantile_imp(T df, T p, const Policy& pol, const boost::math::false_type*)
449 {
450 BOOST_MATH_STD_USING
451 //
452 // Need to use inverse incomplete beta to get
453 // required precision so not so fast:
454 //
455 T probability = (p > 0.5) ? 1 - p : p;
456 T t, x, y(0);
457 x = ibeta_inv(df / 2, T(0.5), 2 * probability, &y, pol);
458 if(df * y > tools::max_value<T>() * x)
459 t = policies::raise_overflow_error<T>("boost::math::students_t_quantile<%1%>(%1%,%1%)", nullptr, pol);
460 else
461 t = sqrt(df * y / x);
462 //
463 // Figure out sign based on the size of p:
464 //
465 if(p < 0.5)
466 t = -t;
467 return t;
468 }
469
470 template <class T, class Policy>
471 BOOST_MATH_GPU_ENABLED T fast_students_t_quantile_imp(T df, T p, const Policy& pol, const boost::math::true_type*)
472 {
473 BOOST_MATH_STD_USING
474 bool invert = false;
475 if((df < 2) && (floor(df) != df))
476 return boost::math::detail::fast_students_t_quantile_imp(df, p, pol, static_cast<boost::math::false_type*>(nullptr));
477 if(p > 0.5)
478 {
479 p = 1 - p;
480 invert = true;
481 }
482 //
483 // Get an estimate of the result:
484 //
485 bool exact;
486 T t = inverse_students_t(df, p, T(1-p), pol, &exact);
487 if((t == 0) || exact)
488 return invert ? -t : t; // can't do better!
489 //
490 // Change variables to inverse incomplete beta:
491 //
492 T t2 = t * t;
493 T xb = df / (df + t2);
494 T y = t2 / (df + t2);
495 T a = df / 2;
496 //
497 // t can be so large that x underflows,
498 // just return our estimate in that case:
499 //
500 if(xb == 0)
501 return t;
502 //
503 // Get incomplete beta and it's derivative:
504 //
505 T f1;
506 T f0 = xb < y ? ibeta_imp(a, constants::half<T>(), xb, pol, false, true, &f1)
507 : ibeta_imp(constants::half<T>(), a, y, pol, true, true, &f1);
508
509 // Get cdf from incomplete beta result:
510 T p0 = f0 / 2 - p;
511 // Get pdf from derivative:
512 T p1 = f1 * sqrt(y * xb * xb * xb / df);
513 //
514 // Second derivative divided by p1:
515 //
516 // yacas gives:
517 //
518 // In> PrettyForm(Simplify(D(t) (1 + t^2/v) ^ (-(v+1)/2)))
519 //
520 // | | v + 1 | |
521 // | -| ----- + 1 | |
522 // | | 2 | |
523 // -| | 2 | |
524 // | | t | |
525 // | | -- + 1 | |
526 // | ( v + 1 ) * | v | * t |
527 // ---------------------------------------------
528 // v
529 //
530 // Which after some manipulation is:
531 //
532 // -p1 * t * (df + 1) / (t^2 + df)
533 //
534 T p2 = t * (df + 1) / (t * t + df);
535 // Halley step:
536 t = fabs(t);
537 t += p0 / (p1 + p0 * p2 / 2);
538 return !invert ? -t : t;
539 }
540
541 template <class T, class Policy>
542 BOOST_MATH_GPU_ENABLED inline T fast_students_t_quantile(T df, T p, const Policy& pol)
543 {
544 typedef typename policies::evaluation<T, Policy>::type value_type;
545 typedef typename policies::normalise<
546 Policy,
547 policies::promote_float<false>,
548 policies::promote_double<false>,
549 policies::discrete_quantile<>,
550 policies::assert_undefined<> >::type forwarding_policy;
551
552 typedef boost::math::integral_constant<bool,
553 (boost::math::numeric_limits<T>::digits <= 53)
554 &&
555 (boost::math::numeric_limits<T>::is_specialized)
556 &&
557 (boost::math::numeric_limits<T>::radix == 2)
558 > tag_type;
559 return policies::checked_narrowing_cast<T, forwarding_policy>(fast_students_t_quantile_imp(static_cast<value_type>(df), static_cast<value_type>(p), pol, static_cast<tag_type*>(nullptr)), "boost::math::students_t_quantile<%1%>(%1%,%1%,%1%)");
560 }
561
562 }}} // namespaces
563
564 #endif // BOOST_MATH_SF_DETAIL_INV_T_HPP
565
566
567