[ceph.git] / ceph / src / boost / boost / math / quadrature / tanh_sinh.hpp

// Copyright Nick Thompson, 2017
// Use, modification and distribution are subject to the
// Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt
// or copy at http://www.boost.org/LICENSE_1_0.txt)

/*
 * This class performs tanh-sinh quadrature on the real line.
 * Tanh-sinh quadrature is exponentially convergent for integrands in Hardy spaces,
 * (see https://en.wikipedia.org/wiki/Hardy_space for a formal definition), and is optimal for a random function from that class.
 *
 * The tanh-sinh quadrature is one of a class of so called "double exponential quadratures"-there is a large family of them,
 * but this one seems to be the most commonly used.
 *
 * As always, there are caveats: For instance, if the function you want to integrate is not holomorphic on the unit disk,
 * then the rapid convergence will be spoiled. In this case, a more appropriate quadrature is (say) Romberg, which does not
 * require the function to be holomorphic, only differentiable up to some order.
 *
 * In addition, if you are integrating a periodic function over a period, the trapezoidal rule is better.
 *
 * References:
 *
 * 1) Mori, Masatake. "Quadrature formulas obtained by variable transformation and the DE-rule." Journal of Computational and Applied Mathematics 12 (1985): 119-130.
 * 2) Bailey, David H., Karthik Jeyabalan, and Xiaoye S. Li. "A comparison of three high-precision quadrature schemes." Experimental Mathematics 14.3 (2005): 317-329.
 * 3) Press, William H., et al. "Numerical recipes third edition: the art of scientific computing." Cambridge University Press 32 (2007): 10013-2473.
 *
 */

#ifndef BOOST_MATH_QUADRATURE_TANH_SINH_HPP
#define BOOST_MATH_QUADRATURE_TANH_SINH_HPP

#include <cmath>
#include <limits>
#include <memory>
#include <boost/math/quadrature/detail/tanh_sinh_detail.hpp>

namespace boost{ namespace math{ namespace quadrature {

template<class Real, class Policy = policies::policy<> >
class tanh_sinh
{
public:
    tanh_sinh(size_t max_refinements = 15, const Real& min_complement = tools::min_value<Real>() * 4)
    : m_imp(std::make_shared<detail::tanh_sinh_detail<Real, Policy>>(max_refinements, min_complement)) {}

    template<class F>
    auto integrate(const F f, Real a, Real b, Real tolerance = tools::root_epsilon<Real>(), Real* error = nullptr, Real* L1 = nullptr, std::size_t* levels = nullptr) ->decltype(std::declval<F>()(std::declval<Real>())) const;
    template<class F>
    auto integrate(const F f, Real a, Real b, Real tolerance = tools::root_epsilon<Real>(), Real* error = nullptr, Real* L1 = nullptr, std::size_t* levels = nullptr) ->decltype(std::declval<F>()(std::declval<Real>(), std::declval<Real>())) const;

    template<class F>
    auto integrate(const F f, Real tolerance = tools::root_epsilon<Real>(), Real* error = nullptr, Real* L1 = nullptr, std::size_t* levels = nullptr) ->decltype(std::declval<F>()(std::declval<Real>())) const;
    template<class F>
    auto integrate(const F f, Real tolerance = tools::root_epsilon<Real>(), Real* error = nullptr, Real* L1 = nullptr, std::size_t* levels = nullptr) ->decltype(std::declval<F>()(std::declval<Real>(), std::declval<Real>())) const;

private:
    std::shared_ptr<detail::tanh_sinh_detail<Real, Policy>> m_imp;
};

template<class Real, class Policy>
template<class F>
auto tanh_sinh<Real, Policy>::integrate(const F f, Real a, Real b, Real tolerance, Real* error, Real* L1, std::size_t* levels) ->decltype(std::declval<F>()(std::declval<Real>())) const
{
    BOOST_MATH_STD_USING
    using boost::math::constants::half;
    using boost::math::quadrature::detail::tanh_sinh_detail;

    static const char* function = "tanh_sinh<%1%>::integrate";

    typedef decltype(std::declval<F>()(std::declval<Real>())) result_type;

    if (!(boost::math::isnan)(a) && !(boost::math::isnan)(b))
    {

       // Infinite limits:
       if ((a <= -tools::max_value<Real>()) && (b >= tools::max_value<Real>()))
       {
          auto u = [&](const Real& t, const Real& tc)->result_type
          { 
             Real t_sq = t*t; 
             Real inv;
             if (t > 0.5f)
                inv = 1 / ((2 - tc) * tc);
             else if(t < -0.5)
                inv = 1 / ((2 + tc) * -tc);
             else
                inv = 1 / (1 - t_sq);
             return f(t*inv)*(1 + t_sq)*inv*inv; 
          };
          Real limit = sqrt(tools::min_value<Real>()) * 4;
          return m_imp->integrate(u, error, L1, function, limit, limit, tolerance, levels);
       }

       // Right limit is infinite:
       if ((boost::math::isfinite)(a) && (b >= tools::max_value<Real>()))
       {
          auto u = [&](const Real& t, const Real& tc)->result_type
          { 
             Real z, arg;
             if (t > -0.5f)
                z = 1 / (t + 1);
             else
                z = -1 / tc;
             if (t < 0.5)
                arg = 2 * z + a - 1;
             else
                arg = a + tc / (2 - tc);
             return f(arg)*z*z; 
          };
          Real left_limit = sqrt(tools::min_value<Real>()) * 4;
          result_type Q = Real(2) * m_imp->integrate(u, error, L1, function, left_limit, tools::min_value<Real>(), tolerance, levels);
          if (L1)
          {
             *L1 *= 2;
          }

          return Q;
       }

       if ((boost::math::isfinite)(b) && (a <= -tools::max_value<Real>()))
       {
          auto v = [&](const Real& t, const Real& tc)->result_type
          { 
             Real z;
             if (t > -0.5)
                z = 1 / (t + 1);
             else
                z = -1 / tc;
             Real arg;
             if (t < 0.5)
                arg = 2 * z - 1;
             else
                arg = tc / (2 - tc);
             return f(b - arg) * z * z;
          };

          Real left_limit = sqrt(tools::min_value<Real>()) * 4;
          result_type Q = Real(2) * m_imp->integrate(v, error, L1, function, left_limit, tools::min_value<Real>(), tolerance, levels);
          if (L1)
          {
             *L1 *= 2;
          }
          return Q;
       }

       if ((boost::math::isfinite)(a) && (boost::math::isfinite)(b))
       {
          if (b <= a)
          {
             return policies::raise_domain_error(function, "Arguments to integrate are in wrong order; integration over [a,b] must have b > a.", a, Policy());
          }
          Real avg = (a + b)*half<Real>();
          Real diff = (b - a)*half<Real>();
          Real avg_over_diff_m1 = a / diff;
          Real avg_over_diff_p1 = b / diff;
          bool have_small_left = fabs(a) < 0.5f;
          bool have_small_right = fabs(b) < 0.5f;
          Real left_min_complement = float_next(avg_over_diff_m1) - avg_over_diff_m1;
          Real min_complement_limit = (std::max)(tools::min_value<Real>(), Real(tools::min_value<Real>() / diff));
          if (left_min_complement < min_complement_limit)
             left_min_complement = min_complement_limit;
          Real right_min_complement = avg_over_diff_p1 - float_prior(avg_over_diff_p1);
          if (right_min_complement < min_complement_limit)
             right_min_complement = min_complement_limit;
          //
          // These asserts will fail only if rounding errors on
          // type Real have accumulated so much error that it's
          // broken our internal logic.  Should that prove to be
          // a persistent issue, we might need to add a bit of fudge
          // factor to move left_min_complement and right_min_complement
          // further from the end points of the range.
          //
          BOOST_ASSERT((left_min_complement * diff + a) > a);
          BOOST_ASSERT((b - right_min_complement * diff) < b);
          auto u = [&](Real z, Real zc)->result_type
          { 
             Real position;
             if (z < -0.5)
             {
                if(have_small_left)
                  return f(diff * (avg_over_diff_m1 - zc));
                position = a - diff * zc;
             }
             if (z > 0.5)
             {
                if(have_small_right)
                  return f(diff * (avg_over_diff_p1 - zc));
                position = b - diff * zc;
             }
             else
                position = avg + diff*z;
             BOOST_ASSERT(position != a);
             BOOST_ASSERT(position != b);
             return f(position);
          };
          result_type Q = diff*m_imp->integrate(u, error, L1, function, left_min_complement, right_min_complement, tolerance, levels);

          if (L1)
          {
             *L1 *= diff;
          }
          return Q;
       }
    }
    return policies::raise_domain_error(function, "The domain of integration is not sensible; please check the bounds.", a, Policy());
}

template<class Real, class Policy>
template<class F>
auto tanh_sinh<Real, Policy>::integrate(const F f, Real a, Real b, Real tolerance, Real* error, Real* L1, std::size_t* levels) ->decltype(std::declval<F>()(std::declval<Real>(), std::declval<Real>())) const
{
   BOOST_MATH_STD_USING
      using boost::math::constants::half;
   using boost::math::quadrature::detail::tanh_sinh_detail;

   static const char* function = "tanh_sinh<%1%>::integrate";

   if ((boost::math::isfinite)(a) && (boost::math::isfinite)(b))
   {
      if (b <= a)
      {
         return policies::raise_domain_error(function, "Arguments to integrate are in wrong order; integration over [a,b] must have b > a.", a, Policy());
      }
      auto u = [&](Real z, Real zc)->Real
      {
         if (z < 0)
            return f((a - b) * zc / 2 + a, (b - a) * zc / 2);
         else
            return f((a - b) * zc / 2 + b, (b - a) * zc / 2);
      };
      Real diff = (b - a)*half<Real>();
      Real left_min_complement = tools::min_value<Real>() * 4;
      Real right_min_complement = tools::min_value<Real>() * 4;
      Real Q = diff*m_imp->integrate(u, error, L1, function, left_min_complement, right_min_complement, tolerance, levels);

      if (L1)
      {
         *L1 *= diff;
      }
      return Q;
   }
   return policies::raise_domain_error(function, "The domain of integration is not sensible; please check the bounds.", a, Policy());
}

template<class Real, class Policy>
template<class F>
auto tanh_sinh<Real, Policy>::integrate(const F f, Real tolerance, Real* error, Real* L1, std::size_t* levels) ->decltype(std::declval<F>()(std::declval<Real>())) const
{
   using boost::math::quadrature::detail::tanh_sinh_detail;
   static const char* function = "tanh_sinh<%1%>::integrate";
   Real min_complement = tools::epsilon<Real>();
   return m_imp->integrate([&](const Real& arg, const Real&) { return f(arg); }, error, L1, function, min_complement, min_complement, tolerance, levels);
}

template<class Real, class Policy>
template<class F>
auto tanh_sinh<Real, Policy>::integrate(const F f, Real tolerance, Real* error, Real* L1, std::size_t* levels) ->decltype(std::declval<F>()(std::declval<Real>(), std::declval<Real>())) const
{
   using boost::math::quadrature::detail::tanh_sinh_detail;
   static const char* function = "tanh_sinh<%1%>::integrate";
   Real min_complement = tools::min_value<Real>() * 4;
   return m_imp->integrate(f, error, L1, function, min_complement, min_complement, tolerance, levels);
}

}
}
}
#endif
Commit	Line	Data
b32b8144 FG	1	// Copyright Nick Thompson, 2017
	2	// Use, modification and distribution are subject to the
	3	// Boost Software License, Version 1.0.
	4	// (See accompanying file LICENSE_1_0.txt
	5	// or copy at http://www.boost.org/LICENSE_1_0.txt)
	6
	7	/*
	8	* This class performs tanh-sinh quadrature on the real line.
	9	* Tanh-sinh quadrature is exponentially convergent for integrands in Hardy spaces,
	10	* (see https://en.wikipedia.org/wiki/Hardy_space for a formal definition), and is optimal for a random function from that class.
	11	*
	12	* The tanh-sinh quadrature is one of a class of so called "double exponential quadratures"-there is a large family of them,
	13	* but this one seems to be the most commonly used.
	14	*
	15	* As always, there are caveats: For instance, if the function you want to integrate is not holomorphic on the unit disk,
	16	* then the rapid convergence will be spoiled. In this case, a more appropriate quadrature is (say) Romberg, which does not
	17	* require the function to be holomorphic, only differentiable up to some order.
	18	*
	19	* In addition, if you are integrating a periodic function over a period, the trapezoidal rule is better.
	20	*
	21	* References:
	22	*
	23	* 1) Mori, Masatake. "Quadrature formulas obtained by variable transformation and the DE-rule." Journal of Computational and Applied Mathematics 12 (1985): 119-130.
	24	* 2) Bailey, David H., Karthik Jeyabalan, and Xiaoye S. Li. "A comparison of three high-precision quadrature schemes." Experimental Mathematics 14.3 (2005): 317-329.
	25	* 3) Press, William H., et al. "Numerical recipes third edition: the art of scientific computing." Cambridge University Press 32 (2007): 10013-2473.
	26	*
	27	*/
	28
	29	#ifndef BOOST_MATH_QUADRATURE_TANH_SINH_HPP
	30	#define BOOST_MATH_QUADRATURE_TANH_SINH_HPP
	31
	32	#include <cmath>
	33	#include <limits>
	34	#include <memory>
	35	#include <boost/math/quadrature/detail/tanh_sinh_detail.hpp>
	36
	37	namespace boost{ namespace math{ namespace quadrature {
	38
	39	template<class Real, class Policy = policies::policy<> >
	40	class tanh_sinh
	41	{
	42	public:
	43	tanh_sinh(size_t max_refinements = 15, const Real& min_complement = tools::min_value<Real>() * 4)
	44	: m_imp(std::make_shared<detail::tanh_sinh_detail<Real, Policy>>(max_refinements, min_complement)) {}
	45
	46	template<class F>
92f5a8d4	47	auto integrate(const F f, Real a, Real b, Real tolerance = tools::root_epsilon<Real>(), Real* error = nullptr, Real* L1 = nullptr, std::size_t* levels = nullptr) ->decltype(std::declval<F>()(std::declval<Real>())) const;
b32b8144	48	template<class F>
92f5a8d4	49	auto integrate(const F f, Real a, Real b, Real tolerance = tools::root_epsilon<Real>(), Real* error = nullptr, Real* L1 = nullptr, std::size_t* levels = nullptr) ->decltype(std::declval<F>()(std::declval<Real>(), std::declval<Real>())) const;
b32b8144 FG	50
b32b8144 FG	51	template<class F>
92f5a8d4	52	auto integrate(const F f, Real tolerance = tools::root_epsilon<Real>(), Real* error = nullptr, Real* L1 = nullptr, std::size_t* levels = nullptr) ->decltype(std::declval<F>()(std::declval<Real>())) const;
b32b8144	53	template<class F>
92f5a8d4	54	auto integrate(const F f, Real tolerance = tools::root_epsilon<Real>(), Real* error = nullptr, Real* L1 = nullptr, std::size_t* levels = nullptr) ->decltype(std::declval<F>()(std::declval<Real>(), std::declval<Real>())) const;
b32b8144 FG	55
	56	private:
	57	std::shared_ptr<detail::tanh_sinh_detail<Real, Policy>> m_imp;
	58	};
	59
	60	template<class Real, class Policy>
	61	template<class F>
92f5a8d4	62	auto tanh_sinh<Real, Policy>::integrate(const F f, Real a, Real b, Real tolerance, Real* error, Real* L1, std::size_t* levels) ->decltype(std::declval<F>()(std::declval<Real>())) const
b32b8144 FG	63	{
	64	BOOST_MATH_STD_USING
	65	using boost::math::constants::half;
	66	using boost::math::quadrature::detail::tanh_sinh_detail;
	67
	68	static const char* function = "tanh_sinh<%1%>::integrate";
	69
92f5a8d4 TL	70	typedef decltype(std::declval<F>()(std::declval<Real>())) result_type;
92f5a8d4 TL	71
b32b8144 FG	72	if (!(boost::math::isnan)(a) && !(boost::math::isnan)(b))
	73	{
	74
	75	// Infinite limits:
	76	if ((a <= -tools::max_value<Real>()) && (b >= tools::max_value<Real>()))
	77	{
92f5a8d4	78	auto u = [&](const Real& t, const Real& tc)->result_type
b32b8144 FG	79	{
	80	Real t_sq = t*t;
	81	Real inv;
	82	if (t > 0.5f)
	83	inv = 1 / ((2 - tc) * tc);
	84	else if(t < -0.5)
	85	inv = 1 / ((2 + tc) * -tc);
	86	else
	87	inv = 1 / (1 - t_sq);
	88	return f(tinv)(1 + t_sq)invinv;
	89	};
	90	Real limit = sqrt(tools::min_value<Real>()) * 4;
	91	return m_imp->integrate(u, error, L1, function, limit, limit, tolerance, levels);
	92	}
	93
	94	// Right limit is infinite:
	95	if ((boost::math::isfinite)(a) && (b >= tools::max_value<Real>()))
	96	{
92f5a8d4	97	auto u = [&](const Real& t, const Real& tc)->result_type
b32b8144 FG	98	{
	99	Real z, arg;
	100	if (t > -0.5f)
	101	z = 1 / (t + 1);
	102	else
	103	z = -1 / tc;
	104	if (t < 0.5)
	105	arg = 2 * z + a - 1;
	106	else
	107	arg = a + tc / (2 - tc);
	108	return f(arg)zz;
	109	};
	110	Real left_limit = sqrt(tools::min_value<Real>()) * 4;
92f5a8d4	111	result_type Q = Real(2) * m_imp->integrate(u, error, L1, function, left_limit, tools::min_value<Real>(), tolerance, levels);
b32b8144 FG	112	if (L1)
	113	{
	114	L1 = 2;
	115	}
	116
	117	return Q;
	118	}
	119
	120	if ((boost::math::isfinite)(b) && (a <= -tools::max_value<Real>()))
	121	{
92f5a8d4	122	auto v = [&](const Real& t, const Real& tc)->result_type
b32b8144 FG	123	{
	124	Real z;
	125	if (t > -0.5)
	126	z = 1 / (t + 1);
	127	else
	128	z = -1 / tc;
	129	Real arg;
	130	if (t < 0.5)
	131	arg = 2 * z - 1;
	132	else
	133	arg = tc / (2 - tc);
	134	return f(b - arg) * z * z;
	135	};
	136
	137	Real left_limit = sqrt(tools::min_value<Real>()) * 4;
92f5a8d4	138	result_type Q = Real(2) * m_imp->integrate(v, error, L1, function, left_limit, tools::min_value<Real>(), tolerance, levels);
b32b8144 FG	139	if (L1)
	140	{
	141	L1 = 2;
	142	}
	143	return Q;
	144	}
	145
	146	if ((boost::math::isfinite)(a) && (boost::math::isfinite)(b))
	147	{
	148	if (b <= a)
	149	{
	150	return policies::raise_domain_error(function, "Arguments to integrate are in wrong order; integration over [a,b] must have b > a.", a, Policy());
	151	}
	152	Real avg = (a + b)*half<Real>();
	153	Real diff = (b - a)*half<Real>();
	154	Real avg_over_diff_m1 = a / diff;
	155	Real avg_over_diff_p1 = b / diff;
	156	bool have_small_left = fabs(a) < 0.5f;
	157	bool have_small_right = fabs(b) < 0.5f;
	158	Real left_min_complement = float_next(avg_over_diff_m1) - avg_over_diff_m1;
92f5a8d4 TL	159	Real min_complement_limit = (std::max)(tools::min_value<Real>(), Real(tools::min_value<Real>() / diff));
	160	if (left_min_complement < min_complement_limit)
	161	left_min_complement = min_complement_limit;
b32b8144	162	Real right_min_complement = avg_over_diff_p1 - float_prior(avg_over_diff_p1);
92f5a8d4 TL	163	if (right_min_complement < min_complement_limit)
	164	right_min_complement = min_complement_limit;
	165	//
	166	// These asserts will fail only if rounding errors on
	167	// type Real have accumulated so much error that it's
	168	// broken our internal logic. Should that prove to be
	169	// a persistent issue, we might need to add a bit of fudge
	170	// factor to move left_min_complement and right_min_complement
	171	// further from the end points of the range.
	172	//
	173	BOOST_ASSERT((left_min_complement * diff + a) > a);
	174	BOOST_ASSERT((b - right_min_complement * diff) < b);
	175	auto u = [&](Real z, Real zc)->result_type
b32b8144	176	{
92f5a8d4 TL	177	Real position;
	178	if (z < -0.5)
	179	{
	180	if(have_small_left)
	181	return f(diff * (avg_over_diff_m1 - zc));
	182	position = a - diff * zc;
	183	}
	184	if (z > 0.5)
	185	{
	186	if(have_small_right)
	187	return f(diff * (avg_over_diff_p1 - zc));
	188	position = b - diff * zc;
	189	}
	190	else
	191	position = avg + diff*z;
b32b8144 FG	192	BOOST_ASSERT(position != a);
	193	BOOST_ASSERT(position != b);
	194	return f(position);
	195	};
92f5a8d4	196	result_type Q = diff*m_imp->integrate(u, error, L1, function, left_min_complement, right_min_complement, tolerance, levels);
b32b8144 FG	197
	198	if (L1)
	199	{
	200	L1 = diff;
	201	}
	202	return Q;
	203	}
	204	}
	205	return policies::raise_domain_error(function, "The domain of integration is not sensible; please check the bounds.", a, Policy());
	206	}
	207
	208	template<class Real, class Policy>
	209	template<class F>
92f5a8d4	210	auto tanh_sinh<Real, Policy>::integrate(const F f, Real a, Real b, Real tolerance, Real* error, Real* L1, std::size_t* levels) ->decltype(std::declval<F>()(std::declval<Real>(), std::declval<Real>())) const
b32b8144 FG	211	{
	212	BOOST_MATH_STD_USING
	213	using boost::math::constants::half;
	214	using boost::math::quadrature::detail::tanh_sinh_detail;
	215
	216	static const char* function = "tanh_sinh<%1%>::integrate";
	217
	218	if ((boost::math::isfinite)(a) && (boost::math::isfinite)(b))
	219	{
	220	if (b <= a)
	221	{
	222	return policies::raise_domain_error(function, "Arguments to integrate are in wrong order; integration over [a,b] must have b > a.", a, Policy());
	223	}
	224	auto u = [&](Real z, Real zc)->Real
	225	{
	226	if (z < 0)
	227	return f((a - b) * zc / 2 + a, (b - a) * zc / 2);
	228	else
	229	return f((a - b) * zc / 2 + b, (b - a) * zc / 2);
	230	};
	231	Real diff = (b - a)*half<Real>();
	232	Real left_min_complement = tools::min_value<Real>() * 4;
	233	Real right_min_complement = tools::min_value<Real>() * 4;
	234	Real Q = diff*m_imp->integrate(u, error, L1, function, left_min_complement, right_min_complement, tolerance, levels);
	235
	236	if (L1)
	237	{
	238	L1 = diff;
	239	}
	240	return Q;
	241	}
	242	return policies::raise_domain_error(function, "The domain of integration is not sensible; please check the bounds.", a, Policy());
	243	}
	244
	245	template<class Real, class Policy>
	246	template<class F>
92f5a8d4	247	auto tanh_sinh<Real, Policy>::integrate(const F f, Real tolerance, Real* error, Real* L1, std::size_t* levels) ->decltype(std::declval<F>()(std::declval<Real>())) const
b32b8144 FG	248	{
	249	using boost::math::quadrature::detail::tanh_sinh_detail;
	250	static const char* function = "tanh_sinh<%1%>::integrate";
	251	Real min_complement = tools::epsilon<Real>();
	252	return m_imp->integrate([&](const Real& arg, const Real&) { return f(arg); }, error, L1, function, min_complement, min_complement, tolerance, levels);
	253	}
	254
	255	template<class Real, class Policy>
	256	template<class F>
92f5a8d4	257	auto tanh_sinh<Real, Policy>::integrate(const F f, Real tolerance, Real* error, Real* L1, std::size_t* levels) ->decltype(std::declval<F>()(std::declval<Real>(), std::declval<Real>())) const
b32b8144 FG	258	{
	259	using boost::math::quadrature::detail::tanh_sinh_detail;
	260	static const char* function = "tanh_sinh<%1%>::integrate";
	261	Real min_complement = tools::min_value<Real>() * 4;
	262	return m_imp->integrate(f, error, L1, function, min_complement, min_complement, tolerance, levels);
	263	}
	264
	265	}
	266	}
	267	}
	268	#endif