boost/math/special_functions/detail/erf_inv.hpp

   1 //  (C) Copyright John Maddock 2006.
   2 //  Use, modification and distribution are subject to the
   3 //  Boost Software License, Version 1.0. (See accompanying file
   4 //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   5
   6 #ifndef BOOST_MATH_SF_ERF_INV_HPP
   7 #define BOOST_MATH_SF_ERF_INV_HPP
   8
   9 #ifdef _MSC_VER
  10 #pragma once
  11 #endif
  12
  13 namespace boost{ namespace math{
  14
  15 namespace detail{
  16 //
  17 // The inverse erf and erfc functions share a common implementation,
  18 // this version is for 80-bit long double's and smaller:
  19 //
  20 template <class T, class Policy>
  21 T erf_inv_imp(const T& p, const T& q, const Policy&, const boost::mpl::int_<64>*)
  22 {
  23    BOOST_MATH_STD_USING // for ADL of std names.
  24
  25    T result = 0;
  26
  27    if(p <= 0.5)
  28    {
  29       //
  30       // Evaluate inverse erf using the rational approximation:
  31       //
  32       // x = p(p+10)(Y+R(p))
  33       //
  34       // Where Y is a constant, and R(p) is optimised for a low
  35       // absolute error compared to |Y|.
  36       //
  37       // double: Max error found: 2.001849e-18
  38       // long double: Max error found: 1.017064e-20
  39       // Maximum Deviation Found (actual error term at infinite precision) 8.030e-21
  40       //
  41       static const float Y = 0.0891314744949340820313f;
  42       static const T P[] = {
  43          -0.000508781949658280665617L,
  44          -0.00836874819741736770379L,
  45          0.0334806625409744615033L,
  46          -0.0126926147662974029034L,
  47          -0.0365637971411762664006L,
  48          0.0219878681111168899165L,
  49          0.00822687874676915743155L,
  50          -0.00538772965071242932965L
  51       };
  52       static const T Q[] = {
  53          1,
  54          -0.970005043303290640362L,
  55          -1.56574558234175846809L,
  56          1.56221558398423026363L,
  57          0.662328840472002992063L,
  58          -0.71228902341542847553L,
  59          -0.0527396382340099713954L,
  60          0.0795283687341571680018L,
  61          -0.00233393759374190016776L,
  62          0.000886216390456424707504L
  63       };
  64       T g = p * (p + 10);
  65       T r = tools::evaluate_polynomial(P, p) / tools::evaluate_polynomial(Q, p);
  66       result = g * Y + g * r;
  67    }
  68    else if(q >= 0.25)
  69    {
  70       //
  71       // Rational approximation for 0.5 > q >= 0.25
  72       //
  73       // x = sqrt(-2*log(q)) / (Y + R(q))
  74       //
  75       // Where Y is a constant, and R(q) is optimised for a low
  76       // absolute error compared to Y.
  77       //
  78       // double : Max error found: 7.403372e-17
  79       // long double : Max error found: 6.084616e-20
  80       // Maximum Deviation Found (error term) 4.811e-20
  81       //
  82       static const float Y = 2.249481201171875f;
  83       static const T P[] = {
  84          -0.202433508355938759655L,
  85          0.105264680699391713268L,
  86          8.37050328343119927838L,
  87          17.6447298408374015486L,
  88          -18.8510648058714251895L,
  89          -44.6382324441786960818L,
  90          17.445385985570866523L,
  91          21.1294655448340526258L,
  92          -3.67192254707729348546L
  93       };
  94       static const T Q[] = {
  95          1L,
  96          6.24264124854247537712L,
  97          3.9713437953343869095L,
  98          -28.6608180499800029974L,
  99          -20.1432634680485188801L,
 100          48.5609213108739935468L,
 101          10.8268667355460159008L,
 102          -22.6436933413139721736L,
 103          1.72114765761200282724L
 104       };
 105       T g = sqrt(-2 * log(q));
 106       T xs = q - 0.25;
 107       T r = tools::evaluate_polynomial(P, xs) / tools::evaluate_polynomial(Q, xs);
 108       result = g / (Y + r);
 109    }
 110    else
 111    {
 112       //
 113       // For q < 0.25 we have a series of rational approximations all
 114       // of the general form:
 115       //
 116       // let: x = sqrt(-log(q))
 117       //
 118       // Then the result is given by:
 119       //
 120       // x(Y+R(x-B))
 121       //
 122       // where Y is a constant, B is the lowest value of x for which
 123       // the approximation is valid, and R(x-B) is optimised for a low
 124       // absolute error compared to Y.
 125       //
 126       // Note that almost all code will really go through the first
 127       // or maybe second approximation.  After than we're dealing with very
 128       // small input values indeed: 80 and 128 bit long double's go all the
 129       // way down to ~ 1e-5000 so the "tail" is rather long...
 130       //
 131       T x = sqrt(-log(q));
 132       if(x < 3)
 133       {
 134          // Max error found: 1.089051e-20
 135          static const float Y = 0.807220458984375f;
 136          static const T P[] = {
 137             -0.131102781679951906451L,
 138             -0.163794047193317060787L,
 139             0.117030156341995252019L,
 140             0.387079738972604337464L,
 141             0.337785538912035898924L,
 142             0.142869534408157156766L,
 143             0.0290157910005329060432L,
 144             0.00214558995388805277169L,
 145             -0.679465575181126350155e-6L,
 146             0.285225331782217055858e-7L,
 147             -0.681149956853776992068e-9L
 148          };
 149          static const T Q[] = {
 150             1,
 151             3.46625407242567245975L,
 152             5.38168345707006855425L,
 153             4.77846592945843778382L,
 154             2.59301921623620271374L,
 155             0.848854343457902036425L,
 156             0.152264338295331783612L,
 157             0.01105924229346489121L
 158          };
 159          T xs = x - 1.125;
 160          T R = tools::evaluate_polynomial(P, xs) / tools::evaluate_polynomial(Q, xs);
 161          result = Y * x + R * x;
 162       }
 163       else if(x < 6)
 164       {
 165          // Max error found: 8.389174e-21
 166          static const float Y = 0.93995571136474609375f;
 167          static const T P[] = {
 168             -0.0350353787183177984712L,
 169             -0.00222426529213447927281L,
 170             0.0185573306514231072324L,
 171             0.00950804701325919603619L,
 172             0.00187123492819559223345L,
 173             0.000157544617424960554631L,
 174             0.460469890584317994083e-5L,
 175             -0.230404776911882601748e-9L,
 176             0.266339227425782031962e-11L
 177          };
 178          static const T Q[] = {
 179             1L,
 180             1.3653349817554063097L,
 181             0.762059164553623404043L,
 182             0.220091105764131249824L,
 183             0.0341589143670947727934L,
 184             0.00263861676657015992959L,
 185             0.764675292302794483503e-4L
 186          };
 187          T xs = x - 3;
 188          T R = tools::evaluate_polynomial(P, xs) / tools::evaluate_polynomial(Q, xs);
 189          result = Y * x + R * x;
 190       }
 191       else if(x < 18)
 192       {
 193          // Max error found: 1.481312e-19
 194          static const float Y = 0.98362827301025390625f;
 195          static const T P[] = {
 196             -0.0167431005076633737133L,
 197             -0.00112951438745580278863L,
 198             0.00105628862152492910091L,
 199             0.000209386317487588078668L,
 200             0.149624783758342370182e-4L,
 201             0.449696789927706453732e-6L,
 202             0.462596163522878599135e-8L,
 203             -0.281128735628831791805e-13L,
 204             0.99055709973310326855e-16L
 205          };
 206          static const T Q[] = {
 207             1L,
 208             0.591429344886417493481L,
 209             0.138151865749083321638L,
 210             0.0160746087093676504695L,
 211             0.000964011807005165528527L,
 212             0.275335474764726041141e-4L,
 213             0.282243172016108031869e-6L
 214          };
 215          T xs = x - 6;
 216          T R = tools::evaluate_polynomial(P, xs) / tools::evaluate_polynomial(Q, xs);
 217          result = Y * x + R * x;
 218       }
 219       else if(x < 44)
 220       {
 221          // Max error found: 5.697761e-20
 222          static const float Y = 0.99714565277099609375f;
 223          static const T P[] = {
 224             -0.0024978212791898131227L,
 225             -0.779190719229053954292e-5L,
 226             0.254723037413027451751e-4L,
 227             0.162397777342510920873e-5L,
 228             0.396341011304801168516e-7L,
 229             0.411632831190944208473e-9L,
 230             0.145596286718675035587e-11L,
 231             -0.116765012397184275695e-17L
 232          };
 233          static const T Q[] = {
 234             1L,
 235             0.207123112214422517181L,
 236             0.0169410838120975906478L,
 237             0.000690538265622684595676L,
 238             0.145007359818232637924e-4L,
 239             0.144437756628144157666e-6L,
 240             0.509761276599778486139e-9L
 241          };
 242          T xs = x - 18;
 243          T R = tools::evaluate_polynomial(P, xs) / tools::evaluate_polynomial(Q, xs);
 244          result = Y * x + R * x;
 245       }
 246       else
 247       {
 248          // Max error found: 1.279746e-20
 249          static const float Y = 0.99941349029541015625f;
 250          static const T P[] = {
 251             -0.000539042911019078575891L,
 252             -0.28398759004727721098e-6L,
 253             0.899465114892291446442e-6L,
 254             0.229345859265920864296e-7L,
 255             0.225561444863500149219e-9L,
 256             0.947846627503022684216e-12L,
 257             0.135880130108924861008e-14L,
 258             -0.348890393399948882918e-21L
 259          };
 260          static const T Q[] = {
 261             1L,
 262             0.0845746234001899436914L,
 263             0.00282092984726264681981L,
 264             0.468292921940894236786e-4L,
 265             0.399968812193862100054e-6L,
 266             0.161809290887904476097e-8L,
 267             0.231558608310259605225e-11L
 268          };
 269          T xs = x - 44;
 270          T R = tools::evaluate_polynomial(P, xs) / tools::evaluate_polynomial(Q, xs);
 271          result = Y * x + R * x;
 272       }
 273    }
 274    return result;
 275 }
 276
 277 template <class T, class Policy>
 278 struct erf_roots
 279 {
 280    std::tr1::tuple<T,T,T> operator()(const T& guess)
 281    {
 282       BOOST_MATH_STD_USING
 283       T derivative = sign * (2 / sqrt(constants::pi<T>())) * exp(-(guess * guess));
 284       T derivative2 = -2 * guess * derivative;
 285       return std::tr1::make_tuple(((sign > 0) ? boost::math::erf(guess, Policy()) : boost::math::erfc(guess, Policy())) - target, derivative, derivative2);
 286    }
 287    erf_roots(T z, int s) : target(z), sign(s) {}
 288 private:
 289    T target;
 290    int sign;
 291 };
 292
 293 template <class T, class Policy>
 294 T erf_inv_imp(const T& p, const T& q, const Policy& pol, const boost::mpl::int_<0>*)
 295 {
 296    //
 297    // Generic version, get a guess that's accurate to 64-bits (10^-19)
 298    //
 299    T guess = erf_inv_imp(p, q, pol, static_cast<mpl::int_<64> const*>(0));
 300    T result;
 301    //
 302    // If T has more bit's than 64 in it's mantissa then we need to iterate,
 303    // otherwise we can just return the result:
 304    //
 305    if(policies::digits<T, Policy>() > 64)
 306    {
 307       boost::uintmax_t max_iter = policies::get_max_root_iterations<Policy>();
 308       if(p <= 0.5)
 309       {
 310          result = tools::halley_iterate(detail::erf_roots<typename remove_cv<T>::type, Policy>(p, 1), guess, static_cast<T>(0), tools::max_value<T>(), (policies::digits<T, Policy>() * 2) / 3, max_iter);
 311       }
 312       else
 313       {
 314          result = tools::halley_iterate(detail::erf_roots<typename remove_cv<T>::type, Policy>(q, -1), guess, static_cast<T>(0), tools::max_value<T>(), (policies::digits<T, Policy>() * 2) / 3, max_iter);
 315       }
 316       policies::check_root_iterations("boost::math::erf_inv<%1%>", max_iter, pol);
 317    }
 318    else
 319    {
 320       result = guess;
 321    }
 322    return result;
 323 }
 324
 325 } // namespace detail
 326
 327 template <class T, class Policy>
 328 typename tools::promote_args<T>::type erfc_inv(T z, const Policy& pol)
 329 {
 330    typedef typename tools::promote_args<T>::type result_type;
 331    //
 332    // Begin by testing for domain errors, and other special cases:
 333    //
 334    static const char* function = "boost::math::erfc_inv<%1%>(%1%, %1%)";
 335    if((z < 0) || (z > 2))
 336       policies::raise_domain_error<result_type>(function, "Argument outside range [0,2] in inverse erfc function (got p=%1%).", z, pol);
 337    if(z == 0)
 338       return policies::raise_overflow_error<result_type>(function, 0, pol);
 339    if(z == 2)
 340       return -policies::raise_overflow_error<result_type>(function, 0, pol);
 341    //
 342    // Normalise the input, so it's in the range [0,1], we will
 343    // negate the result if z is outside that range.  This is a simple
 344    // application of the erfc reflection formula: erfc(-z) = 2 - erfc(z)
 345    //
 346    result_type p, q, s;
 347    if(z > 1)
 348    {
 349       q = 2 - z;
 350       p = 1 - q;
 351       s = -1;
 352    }
 353    else
 354    {
 355       p = 1 - z;
 356       q = z;
 357       s = 1;
 358    }
 359    //
 360    // A bit of meta-programming to figure out which implementation
 361    // to use, based on the number of bits in the mantissa of T:
 362    //
 363    typedef typename policies::precision<result_type, Policy>::type precision_type;
 364    typedef typename mpl::if_<
 365       mpl::or_<mpl::less_equal<precision_type, mpl::int_<0> >, mpl::greater<precision_type, mpl::int_<64> > >,
 366       mpl::int_<0>,
 367       mpl::int_<64>
 368    >::type tag_type;
 369    //
 370    // Likewise use internal promotion, so we evaluate at a higher
 371    // precision internally if it's appropriate:
 372    //
 373    typedef typename policies::evaluation<result_type, Policy>::type eval_type;
 374    typedef typename policies::normalise<
 375       Policy,
 376       policies::promote_float<false>,
 377       policies::promote_double<false>,
 378       policies::discrete_quantile<>,
 379       policies::assert_undefined<> >::type forwarding_policy;
 380
 381    //
 382    // And get the result, negating where required:
 383    //
 384    return s * policies::checked_narrowing_cast<result_type, forwarding_policy>(
 385       detail::erf_inv_imp(static_cast<eval_type>(p), static_cast<eval_type>(q), forwarding_policy(), static_cast<tag_type const*>(0)), function);
 386 }
 387
 388 template <class T, class Policy>
 389 typename tools::promote_args<T>::type erf_inv(T z, const Policy& pol)
 390 {
 391    typedef typename tools::promote_args<T>::type result_type;
 392    //
 393    // Begin by testing for domain errors, and other special cases:
 394    //
 395    static const char* function = "boost::math::erf_inv<%1%>(%1%, %1%)";
 396    if((z < -1) || (z > 1))
 397       policies::raise_domain_error<result_type>(function, "Argument outside range [-1, 1] in inverse erf function (got p=%1%).", z, pol);
 398    if(z == 1)
 399       return policies::raise_overflow_error<result_type>(function, 0, pol);
 400    if(z == -1)
 401       return -policies::raise_overflow_error<result_type>(function, 0, pol);
 402    if(z == 0)
 403       return 0;
 404    //
 405    // Normalise the input, so it's in the range [0,1], we will
 406    // negate the result if z is outside that range.  This is a simple
 407    // application of the erf reflection formula: erf(-z) = -erf(z)
 408    //
 409    result_type p, q, s;
 410    if(z < 0)
 411    {
 412       p = -z;
 413       q = 1 - p;
 414       s = -1;
 415    }
 416    else
 417    {
 418       p = z;
 419       q = 1 - z;
 420       s = 1;
 421    }
 422    //
 423    // A bit of meta-programming to figure out which implementation
 424    // to use, based on the number of bits in the mantissa of T:
 425    //
 426    typedef typename policies::precision<result_type, Policy>::type precision_type;
 427    typedef typename mpl::if_<
 428       mpl::or_<mpl::less_equal<precision_type, mpl::int_<0> >, mpl::greater<precision_type, mpl::int_<64> > >,
 429       mpl::int_<0>,
 430       mpl::int_<64>
 431    >::type tag_type;
 432    //
 433    // Likewise use internal promotion, so we evaluate at a higher
 434    // precision internally if it's appropriate:
 435    //
 436    typedef typename policies::evaluation<result_type, Policy>::type eval_type;
 437    typedef typename policies::normalise<
 438       Policy,
 439       policies::promote_float<false>,
 440       policies::promote_double<false>,
 441       policies::discrete_quantile<>,
 442       policies::assert_undefined<> >::type forwarding_policy;
 443    //
 444    // Likewise use internal promotion, so we evaluate at a higher
 445    // precision internally if it's appropriate:
 446    //
 447    typedef typename policies::evaluation<result_type, Policy>::type eval_type;
 448    //
 449    // And get the result, negating where required:
 450    //
 451    return s * policies::checked_narrowing_cast<result_type, forwarding_policy>(
 452       detail::erf_inv_imp(static_cast<eval_type>(p), static_cast<eval_type>(q), forwarding_policy(), static_cast<tag_type const*>(0)), function);
 453 }
 454
 455 template <class T>
 456 inline typename tools::promote_args<T>::type erfc_inv(T z)
 457 {
 458    return erfc_inv(z, policies::policy<>());
 459 }
 460
 461 template <class T>
 462 inline typename tools::promote_args<T>::type erf_inv(T z)
 463 {
 464    return erf_inv(z, policies::policy<>());
 465 }
 466
 467 } // namespace math
 468 } // namespace boost
 469
 470 #endif // BOOST_MATH_SF_ERF_INV_HPP
 471