| 1 |
// Copyright Nick Thompson, 2019 |
| 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 |
#ifndef BOOST_MATH_QUADRATURE_DETAIL_OOURA_FOURIER_INTEGRALS_DETAIL_HPP |
| 7 |
#define BOOST_MATH_QUADRATURE_DETAIL_OOURA_FOURIER_INTEGRALS_DETAIL_HPP |
| 8 |
#include <utility> // for std::pair. |
| 9 |
#include <vector> |
| 10 |
#include <iostream> |
| 11 |
#include <boost/math/special_functions/expm1.hpp> |
| 12 |
#include <boost/math/special_functions/sin_pi.hpp> |
| 13 |
#include <boost/math/special_functions/cos_pi.hpp> |
| 14 |
#include <boost/math/constants/constants.hpp> |
| 15 |
#include <boost/math/tools/config.hpp> |
| 16 |
|
| 17 |
#ifdef BOOST_MATH_HAS_THREADS |
| 18 |
#include <mutex> |
| 19 |
#include <atomic> |
| 20 |
#endif |
| 21 |
|
| 22 |
namespace boost { namespace math { namespace quadrature { namespace detail { |
| 23 |
|
| 24 |
// Ooura and Mori, A robust double exponential formula for Fourier-type integrals, |
| 25 |
// eta is the argument to the exponential in equation 3.3: |
| 26 |
template<class Real> |
| 27 |
std::pair<Real, Real> ooura_eta(Real x, Real alpha) { |
| 28 |
using std::expm1; |
| 29 |
using std::exp; |
| 30 |
using std::abs; |
| 31 |
Real expx = exp(x); |
| 32 |
Real eta_prime = 2 + alpha/expx + expx/4; |
| 33 |
Real eta; |
| 34 |
// This is the fast branch: |
| 35 |
if (abs(x) > 0.125) { |
| 36 |
eta = 2*x - alpha*(1/expx - 1) + (expx - 1)/4; |
| 37 |
} |
| 38 |
else {// this is the slow branch using expm1 for small x: |
| 39 |
eta = 2*x - alpha*expm1(-x) + expm1(x)/4; |
| 40 |
} |
| 41 |
return {eta, eta_prime}; |
| 42 |
} |
| 43 |
|
| 44 |
// Ooura and Mori, A robust double exponential formula for Fourier-type integrals, |
| 45 |
// equation 3.6: |
| 46 |
template<class Real> |
| 47 |
Real calculate_ooura_alpha(Real h) |
| 48 |
{ |
| 49 |
using boost::math::constants::pi; |
| 50 |
using std::log1p; |
| 51 |
using std::sqrt; |
| 52 |
Real x = sqrt(16 + 4*log1p(pi<Real>()/h)/h); |
| 53 |
return 1/x; |
| 54 |
} |
| 55 |
|
| 56 |
template<class Real> |
| 57 |
std::pair<Real, Real> ooura_sin_node_and_weight(long n, Real h, Real alpha) |
| 58 |
{ |
| 59 |
using std::expm1; |
| 60 |
using std::exp; |
| 61 |
using std::abs; |
| 62 |
using boost::math::constants::pi; |
| 63 |
using std::isnan; |
| 64 |
|
| 65 |
if (n == 0) { |
| 66 |
// Equation 44 of https://arxiv.org/pdf/0911.4796.pdf |
| 67 |
// Fourier Transform of the Stretched Exponential Function: Analytic Error Bounds, |
| 68 |
// Double Exponential Transform, and Open-Source Implementation, |
| 69 |
// Joachim Wuttke, |
| 70 |
// The C library libkww provides functions to compute the Kohlrausch-Williams-Watts function, |
| 71 |
// the Laplace-Fourier transform of the stretched (or compressed) exponential function exp(-t^beta) |
| 72 |
// for exponent beta between 0.1 and 1.9 with sixteen decimal digits accuracy. |
| 73 |
|
| 74 |
Real eta_prime_0 = Real(2) + alpha + Real(1)/Real(4); |
| 75 |
Real node = pi<Real>()/(eta_prime_0*h); |
| 76 |
Real weight = pi<Real>()*boost::math::sin_pi(1/(eta_prime_0*h)); |
| 77 |
Real eta_dbl_prime = -alpha + Real(1)/Real(4); |
| 78 |
Real phi_prime_0 = (1 - eta_dbl_prime/(eta_prime_0*eta_prime_0))/2; |
| 79 |
weight *= phi_prime_0; |
| 80 |
return {node, weight}; |
| 81 |
} |
| 82 |
Real x = n*h; |
| 83 |
auto p = ooura_eta(x, alpha); |
| 84 |
auto eta = p.first; |
| 85 |
auto eta_prime = p.second; |
| 86 |
|
| 87 |
Real expm1_meta = expm1(-eta); |
| 88 |
Real exp_meta = exp(-eta); |
| 89 |
Real node = -n*pi<Real>()/expm1_meta; |
| 90 |
|
| 91 |
|
| 92 |
// I have verified that this is not a significant source of inaccuracy in the weight computation: |
| 93 |
Real phi_prime = -(expm1_meta + x*exp_meta*eta_prime)/(expm1_meta*expm1_meta); |
| 94 |
|
| 95 |
// The main source of inaccuracy is in computation of sin_pi. |
| 96 |
// But I've agonized over this, and I think it's as good as it can get: |
| 97 |
Real s = pi<Real>(); |
| 98 |
Real arg; |
| 99 |
if(eta > 1) { |
| 100 |
arg = n/( 1/exp_meta - 1 ); |
| 101 |
s *= boost::math::sin_pi(arg); |
| 102 |
if (n&1) { |
| 103 |
s *= -1; |
| 104 |
} |
| 105 |
} |
| 106 |
else if (eta < -1) { |
| 107 |
arg = n/(1-exp_meta); |
| 108 |
s *= boost::math::sin_pi(arg); |
| 109 |
} |
| 110 |
else { |
| 111 |
arg = -n*exp_meta/expm1_meta; |
| 112 |
s *= boost::math::sin_pi(arg); |
| 113 |
if (n&1) { |
| 114 |
s *= -1; |
| 115 |
} |
| 116 |
} |
| 117 |
|
| 118 |
Real weight = s*phi_prime; |
| 119 |
return {node, weight}; |
| 120 |
} |
| 121 |
|
| 122 |
#ifdef BOOST_MATH_INSTRUMENT_OOURA |
| 123 |
template<class Real> |
| 124 |
void print_ooura_estimate(size_t i, Real I0, Real I1, Real omega) { |
| 125 |
using std::abs; |
| 126 |
std::cout << std::defaultfloat |
| 127 |
<< std::setprecision(std::numeric_limits<Real>::digits10) |
| 128 |
<< std::fixed; |
| 129 |
std::cout << "h = " << Real(1)/Real(1<<i) << ", I_h = " << I0/omega |
| 130 |
<< " = " << std::hexfloat << I0/omega << ", absolute error estimate = " |
| 131 |
<< std::defaultfloat << std::scientific << abs(I0-I1) << std::endl; |
| 132 |
} |
| 133 |
#endif |
| 134 |
|
| 135 |
|
| 136 |
template<class Real> |
| 137 |
std::pair<Real, Real> ooura_cos_node_and_weight(long n, Real h, Real alpha) |
| 138 |
{ |
| 139 |
using std::expm1; |
| 140 |
using std::exp; |
| 141 |
using std::abs; |
| 142 |
using boost::math::constants::pi; |
| 143 |
|
| 144 |
Real x = h*(n-Real(1)/Real(2)); |
| 145 |
auto p = ooura_eta(x, alpha); |
| 146 |
auto eta = p.first; |
| 147 |
auto eta_prime = p.second; |
| 148 |
Real expm1_meta = expm1(-eta); |
| 149 |
Real exp_meta = exp(-eta); |
| 150 |
Real node = pi<Real>()*(Real(1)/Real(2)-n)/expm1_meta; |
| 151 |
|
| 152 |
Real phi_prime = -(expm1_meta + x*exp_meta*eta_prime)/(expm1_meta*expm1_meta); |
| 153 |
|
| 154 |
// Takuya Ooura and Masatake Mori, |
| 155 |
// Journal of Computational and Applied Mathematics, 112 (1999) 229-241. |
| 156 |
// A robust double exponential formula for Fourier-type integrals. |
| 157 |
// Equation 4.6 |
| 158 |
Real s = pi<Real>(); |
| 159 |
Real arg; |
| 160 |
if (eta < -1) { |
| 161 |
arg = -(n-Real(1)/Real(2))/expm1_meta; |
| 162 |
s *= boost::math::cos_pi(arg); |
| 163 |
} |
| 164 |
else { |
| 165 |
arg = -(n-Real(1)/Real(2))*exp_meta/expm1_meta; |
| 166 |
s *= boost::math::sin_pi(arg); |
| 167 |
if (n&1) { |
| 168 |
s *= -1; |
| 169 |
} |
| 170 |
} |
| 171 |
|
| 172 |
Real weight = s*phi_prime; |
| 173 |
return {node, weight}; |
| 174 |
} |
| 175 |
|
| 176 |
|
| 177 |
template<class Real> |
| 178 |
class ooura_fourier_sin_detail { |
| 179 |
public: |
| 180 |
ooura_fourier_sin_detail(const Real relative_error_goal, size_t levels) { |
| 181 |
#ifdef BOOST_MATH_INSTRUMENT_OOURA |
| 182 |
std::cout << "ooura_fourier_sin with relative error goal " << relative_error_goal |
| 183 |
<< " & " << levels << " levels." << std::endl; |
| 184 |
#endif // BOOST_MATH_INSTRUMENT_OOURA |
| 185 |
if (relative_error_goal < std::numeric_limits<Real>::epsilon() * 2) { |
| 186 |
throw std::domain_error("The relative error goal cannot be smaller than the unit roundoff."); |
| 187 |
} |
| 188 |
using std::abs; |
| 189 |
requested_levels_ = levels; |
| 190 |
starting_level_ = 0; |
| 191 |
rel_err_goal_ = relative_error_goal; |
| 192 |
big_nodes_.reserve(levels); |
| 193 |
bweights_.reserve(levels); |
| 194 |
little_nodes_.reserve(levels); |
| 195 |
lweights_.reserve(levels); |
| 196 |
|
| 197 |
for (size_t i = 0; i < levels; ++i) { |
| 198 |
if (std::is_same<Real, float>::value) { |
| 199 |
add_level<double>(i); |
| 200 |
} |
| 201 |
else if (std::is_same<Real, double>::value) { |
| 202 |
add_level<long double>(i); |
| 203 |
} |
| 204 |
else { |
| 205 |
add_level<Real>(i); |
| 206 |
} |
| 207 |
} |
| 208 |
} |
| 209 |
|
| 210 |
std::vector<std::vector<Real>> const & big_nodes() const { |
| 211 |
return big_nodes_; |
| 212 |
} |
| 213 |
|
| 214 |
std::vector<std::vector<Real>> const & weights_for_big_nodes() const { |
| 215 |
return bweights_; |
| 216 |
} |
| 217 |
|
| 218 |
std::vector<std::vector<Real>> const & little_nodes() const { |
| 219 |
return little_nodes_; |
| 220 |
} |
| 221 |
|
| 222 |
std::vector<std::vector<Real>> const & weights_for_little_nodes() const { |
| 223 |
return lweights_; |
| 224 |
} |
| 225 |
|
| 226 |
template<class F> |
| 227 |
std::pair<Real,Real> integrate(F const & f, Real omega) { |
| 228 |
using std::abs; |
| 229 |
using std::max; |
| 230 |
using boost::math::constants::pi; |
| 231 |
|
| 232 |
if (omega == 0) { |
| 233 |
return {Real(0), Real(0)}; |
| 234 |
} |
| 235 |
if (omega < 0) { |
| 236 |
auto p = this->integrate(f, -omega); |
| 237 |
return {-p.first, p.second}; |
| 238 |
} |
| 239 |
|
| 240 |
Real I1 = std::numeric_limits<Real>::quiet_NaN(); |
| 241 |
Real relative_error_estimate = std::numeric_limits<Real>::quiet_NaN(); |
| 242 |
// As we compute integrals, we learn about their structure. |
| 243 |
// Assuming we compute f(t)sin(wt) for many different omega, this gives some |
| 244 |
// a posteriori ability to choose a refinement level that is roughly appropriate. |
| 245 |
size_t i = starting_level_; |
| 246 |
do { |
| 247 |
Real I0 = estimate_integral(f, omega, i); |
| 248 |
#ifdef BOOST_MATH_INSTRUMENT_OOURA |
| 249 |
print_ooura_estimate(i, I0, I1, omega); |
| 250 |
#endif |
| 251 |
Real absolute_error_estimate = abs(I0-I1); |
| 252 |
Real scale = (max)(abs(I0), abs(I1)); |
| 253 |
if (!isnan(I1) && absolute_error_estimate <= rel_err_goal_*scale) { |
| 254 |
starting_level_ = (max)(long(i) - 1, long(0)); |
| 255 |
return {I0/omega, absolute_error_estimate/scale}; |
| 256 |
} |
| 257 |
I1 = I0; |
| 258 |
} while(++i < big_nodes_.size()); |
| 259 |
|
| 260 |
// We've used up all our precomputed levels. |
| 261 |
// Now we need to add more. |
| 262 |
// It might seems reasonable to just keep adding levels indefinitely, if that's what the user wants. |
| 263 |
// But in fact the nodes and weights just merge into each other and the error gets worse after a certain number. |
| 264 |
// This value for max_additional_levels was chosen by observation of a slowly converging oscillatory integral: |
| 265 |
// f(x) := cos(7cos(x))sin(x)/x |
| 266 |
size_t max_additional_levels = 4; |
| 267 |
while (big_nodes_.size() < requested_levels_ + max_additional_levels) { |
| 268 |
size_t ii = big_nodes_.size(); |
| 269 |
if (std::is_same<Real, float>::value) { |
| 270 |
add_level<double>(ii); |
| 271 |
} |
| 272 |
else if (std::is_same<Real, double>::value) { |
| 273 |
add_level<long double>(ii); |
| 274 |
} |
| 275 |
else { |
| 276 |
add_level<Real>(ii); |
| 277 |
} |
| 278 |
Real I0 = estimate_integral(f, omega, ii); |
| 279 |
Real absolute_error_estimate = abs(I0-I1); |
| 280 |
Real scale = (max)(abs(I0), abs(I1)); |
| 281 |
#ifdef BOOST_MATH_INSTRUMENT_OOURA |
| 282 |
print_ooura_estimate(ii, I0, I1, omega); |
| 283 |
#endif |
| 284 |
if (absolute_error_estimate <= rel_err_goal_*scale) { |
| 285 |
starting_level_ = (max)(long(ii) - 1, long(0)); |
| 286 |
return {I0/omega, absolute_error_estimate/scale}; |
| 287 |
} |
| 288 |
I1 = I0; |
| 289 |
++ii; |
| 290 |
} |
| 291 |
|
| 292 |
starting_level_ = static_cast<long>(big_nodes_.size() - 2); |
| 293 |
return {I1/omega, relative_error_estimate}; |
| 294 |
} |
| 295 |
|
| 296 |
private: |
| 297 |
|
| 298 |
template<class PreciseReal> |
| 299 |
void add_level(size_t i) { |
| 300 |
using std::abs; |
| 301 |
size_t current_num_levels = big_nodes_.size(); |
| 302 |
Real unit_roundoff = std::numeric_limits<Real>::epsilon()/2; |
| 303 |
// h0 = 1. Then all further levels have h_i = 1/2^i. |
| 304 |
// Since the nodes don't nest, we could conceivably divide h by (say) 1.5, or 3. |
| 305 |
// It's not clear how much benefit (or loss) would be obtained from this. |
| 306 |
PreciseReal h = PreciseReal(1)/PreciseReal(1<<i); |
| 307 |
|
| 308 |
std::vector<Real> bnode_row; |
| 309 |
std::vector<Real> bweight_row; |
| 310 |
|
| 311 |
// This is a pretty good estimate for how many elements will be placed in the vector: |
| 312 |
bnode_row.reserve((static_cast<size_t>(1)<<i)*sizeof(Real)); |
| 313 |
bweight_row.reserve((static_cast<size_t>(1)<<i)*sizeof(Real)); |
| 314 |
|
| 315 |
std::vector<Real> lnode_row; |
| 316 |
std::vector<Real> lweight_row; |
| 317 |
|
| 318 |
lnode_row.reserve((static_cast<size_t>(1)<<i)*sizeof(Real)); |
| 319 |
lweight_row.reserve((static_cast<size_t>(1)<<i)*sizeof(Real)); |
| 320 |
|
| 321 |
Real max_weight = 1; |
| 322 |
auto alpha = calculate_ooura_alpha(h); |
| 323 |
long n = 0; |
| 324 |
Real w; |
| 325 |
do { |
| 326 |
auto precise_nw = ooura_sin_node_and_weight(n, h, alpha); |
| 327 |
Real node = static_cast<Real>(precise_nw.first); |
| 328 |
Real weight = static_cast<Real>(precise_nw.second); |
| 329 |
w = weight; |
| 330 |
if (bnode_row.size() == bnode_row.capacity()) { |
| 331 |
bnode_row.reserve(2*bnode_row.size()); |
| 332 |
bweight_row.reserve(2*bnode_row.size()); |
| 333 |
} |
| 334 |
|
| 335 |
bnode_row.push_back(node); |
| 336 |
bweight_row.push_back(weight); |
| 337 |
if (abs(weight) > max_weight) { |
| 338 |
max_weight = abs(weight); |
| 339 |
} |
| 340 |
++n; |
| 341 |
// f(t)->0 as t->infty, which is why the weights are computed up to the unit roundoff. |
| 342 |
} while(abs(w) > unit_roundoff*max_weight); |
| 343 |
|
| 344 |
// This class tends to consume a lot of memory; shrink the vectors back down to size: |
| 345 |
bnode_row.shrink_to_fit(); |
| 346 |
bweight_row.shrink_to_fit(); |
| 347 |
// Why we are splitting the nodes into regimes where t_n >> 1 and t_n << 1? |
| 348 |
// It will create the opportunity to sensibly truncate the quadrature sum to significant terms. |
| 349 |
n = -1; |
| 350 |
do { |
| 351 |
auto precise_nw = ooura_sin_node_and_weight(n, h, alpha); |
| 352 |
Real node = static_cast<Real>(precise_nw.first); |
| 353 |
if (node <= 0) { |
| 354 |
break; |
| 355 |
} |
| 356 |
Real weight = static_cast<Real>(precise_nw.second); |
| 357 |
w = weight; |
| 358 |
using std::isnan; |
| 359 |
if (isnan(node)) { |
| 360 |
// This occurs at n = -11 in quad precision: |
| 361 |
break; |
| 362 |
} |
| 363 |
if (lnode_row.size() > 0) { |
| 364 |
if (lnode_row[lnode_row.size()-1] == node) { |
| 365 |
// The nodes have fused into each other: |
| 366 |
break; |
| 367 |
} |
| 368 |
} |
| 369 |
if (lnode_row.size() == lnode_row.capacity()) { |
| 370 |
lnode_row.reserve(2*lnode_row.size()); |
| 371 |
lweight_row.reserve(2*lnode_row.size()); |
| 372 |
} |
| 373 |
lnode_row.push_back(node); |
| 374 |
lweight_row.push_back(weight); |
| 375 |
if (abs(weight) > max_weight) { |
| 376 |
max_weight = abs(weight); |
| 377 |
} |
| 378 |
--n; |
| 379 |
// f(t)->infty is possible as t->0, hence compute up to the min. |
| 380 |
} while(abs(w) > (std::numeric_limits<Real>::min)()*max_weight); |
| 381 |
|
| 382 |
lnode_row.shrink_to_fit(); |
| 383 |
lweight_row.shrink_to_fit(); |
| 384 |
|
| 385 |
#ifdef BOOST_MATH_HAS_THREADS |
| 386 |
// std::scoped_lock once C++17 is more common? |
| 387 |
std::lock_guard<std::mutex> lock(node_weight_mutex_); |
| 388 |
#endif |
| 389 |
// Another thread might have already finished this calculation and appended it to the nodes/weights: |
| 390 |
if (current_num_levels == big_nodes_.size()) { |
| 391 |
big_nodes_.push_back(bnode_row); |
| 392 |
bweights_.push_back(bweight_row); |
| 393 |
|
| 394 |
little_nodes_.push_back(lnode_row); |
| 395 |
lweights_.push_back(lweight_row); |
| 396 |
} |
| 397 |
} |
| 398 |
|
| 399 |
template<class F> |
| 400 |
Real estimate_integral(F const & f, Real omega, size_t i) { |
| 401 |
// Because so few function evaluations are required to get high accuracy on the integrals in the tests, |
| 402 |
// Kahan summation doesn't really help. |
| 403 |
//auto cond = boost::math::tools::summation_condition_number<Real, true>(0); |
| 404 |
Real I0 = 0; |
| 405 |
auto const & b_nodes = big_nodes_[i]; |
| 406 |
auto const & b_weights = bweights_[i]; |
| 407 |
// Will benchmark if this is helpful: |
| 408 |
Real inv_omega = 1/omega; |
| 409 |
for(size_t j = 0 ; j < b_nodes.size(); ++j) { |
| 410 |
I0 += f(b_nodes[j]*inv_omega)*b_weights[j]; |
| 411 |
} |
| 412 |
|
| 413 |
auto const & l_nodes = little_nodes_[i]; |
| 414 |
auto const & l_weights = lweights_[i]; |
| 415 |
// If f decays rapidly as |t|->infty, not all of these calls are necessary. |
| 416 |
for (size_t j = 0; j < l_nodes.size(); ++j) { |
| 417 |
I0 += f(l_nodes[j]*inv_omega)*l_weights[j]; |
| 418 |
} |
| 419 |
return I0; |
| 420 |
} |
| 421 |
|
| 422 |
#ifdef BOOST_MATH_HAS_THREADS |
| 423 |
std::mutex node_weight_mutex_; |
| 424 |
#endif |
| 425 |
// Nodes for n >= 0, giving t_n = pi*phi(nh)/h. Generally t_n >> 1. |
| 426 |
std::vector<std::vector<Real>> big_nodes_; |
| 427 |
// The term bweights_ will indicate that these are weights corresponding |
| 428 |
// to the big nodes: |
| 429 |
std::vector<std::vector<Real>> bweights_; |
| 430 |
|
| 431 |
// Nodes for n < 0: Generally t_n << 1, and an invariant is that t_n > 0. |
| 432 |
std::vector<std::vector<Real>> little_nodes_; |
| 433 |
std::vector<std::vector<Real>> lweights_; |
| 434 |
Real rel_err_goal_; |
| 435 |
|
| 436 |
#ifdef BOOST_MATH_HAS_THREADS |
| 437 |
std::atomic<long> starting_level_{}; |
| 438 |
#else |
| 439 |
long starting_level_; |
| 440 |
#endif |
| 441 |
size_t requested_levels_; |
| 442 |
}; |
| 443 |
|
| 444 |
template<class Real> |
| 445 |
class ooura_fourier_cos_detail { |
| 446 |
public: |
| 447 |
ooura_fourier_cos_detail(const Real relative_error_goal, size_t levels) { |
| 448 |
#ifdef BOOST_MATH_INSTRUMENT_OOURA |
| 449 |
std::cout << "ooura_fourier_cos with relative error goal " << relative_error_goal |
| 450 |
<< " & " << levels << " levels." << std::endl; |
| 451 |
std::cout << "epsilon for type = " << std::numeric_limits<Real>::epsilon() << std::endl; |
| 452 |
#endif // BOOST_MATH_INSTRUMENT_OOURA |
| 453 |
if (relative_error_goal < std::numeric_limits<Real>::epsilon() * 2) { |
| 454 |
throw std::domain_error("The relative error goal cannot be smaller than the unit roundoff!"); |
| 455 |
} |
| 456 |
|
| 457 |
using std::abs; |
| 458 |
requested_levels_ = levels; |
| 459 |
starting_level_ = 0; |
| 460 |
rel_err_goal_ = relative_error_goal; |
| 461 |
big_nodes_.reserve(levels); |
| 462 |
bweights_.reserve(levels); |
| 463 |
little_nodes_.reserve(levels); |
| 464 |
lweights_.reserve(levels); |
| 465 |
|
| 466 |
for (size_t i = 0; i < levels; ++i) { |
| 467 |
if (std::is_same<Real, float>::value) { |
| 468 |
add_level<double>(i); |
| 469 |
} |
| 470 |
else if (std::is_same<Real, double>::value) { |
| 471 |
add_level<long double>(i); |
| 472 |
} |
| 473 |
else { |
| 474 |
add_level<Real>(i); |
| 475 |
} |
| 476 |
} |
| 477 |
|
| 478 |
} |
| 479 |
|
| 480 |
template<class F> |
| 481 |
std::pair<Real,Real> integrate(F const & f, Real omega) { |
| 482 |
using std::abs; |
| 483 |
using std::max; |
| 484 |
using boost::math::constants::pi; |
| 485 |
|
| 486 |
if (omega == 0) { |
| 487 |
throw std::domain_error("At omega = 0, the integral is not oscillatory. The user must choose an appropriate method for this case.\n"); |
| 488 |
} |
| 489 |
|
| 490 |
if (omega < 0) { |
| 491 |
return this->integrate(f, -omega); |
| 492 |
} |
| 493 |
|
| 494 |
Real I1 = std::numeric_limits<Real>::quiet_NaN(); |
| 495 |
Real absolute_error_estimate = std::numeric_limits<Real>::quiet_NaN(); |
| 496 |
Real scale = std::numeric_limits<Real>::quiet_NaN(); |
| 497 |
size_t i = starting_level_; |
| 498 |
do { |
| 499 |
Real I0 = estimate_integral(f, omega, i); |
| 500 |
#ifdef BOOST_MATH_INSTRUMENT_OOURA |
| 501 |
print_ooura_estimate(i, I0, I1, omega); |
| 502 |
#endif |
| 503 |
absolute_error_estimate = abs(I0-I1); |
| 504 |
scale = (max)(abs(I0), abs(I1)); |
| 505 |
if (!isnan(I1) && absolute_error_estimate <= rel_err_goal_*scale) { |
| 506 |
starting_level_ = (max)(long(i) - 1, long(0)); |
| 507 |
return {I0/omega, absolute_error_estimate/scale}; |
| 508 |
} |
| 509 |
I1 = I0; |
| 510 |
} while(++i < big_nodes_.size()); |
| 511 |
|
| 512 |
size_t max_additional_levels = 4; |
| 513 |
while (big_nodes_.size() < requested_levels_ + max_additional_levels) { |
| 514 |
size_t ii = big_nodes_.size(); |
| 515 |
if (std::is_same<Real, float>::value) { |
| 516 |
add_level<double>(ii); |
| 517 |
} |
| 518 |
else if (std::is_same<Real, double>::value) { |
| 519 |
add_level<long double>(ii); |
| 520 |
} |
| 521 |
else { |
| 522 |
add_level<Real>(ii); |
| 523 |
} |
| 524 |
Real I0 = estimate_integral(f, omega, ii); |
| 525 |
#ifdef BOOST_MATH_INSTRUMENT_OOURA |
| 526 |
print_ooura_estimate(ii, I0, I1, omega); |
| 527 |
#endif |
| 528 |
absolute_error_estimate = abs(I0-I1); |
| 529 |
scale = (max)(abs(I0), abs(I1)); |
| 530 |
if (absolute_error_estimate <= rel_err_goal_*scale) { |
| 531 |
starting_level_ = (max)(long(ii) - 1, long(0)); |
| 532 |
return {I0/omega, absolute_error_estimate/scale}; |
| 533 |
} |
| 534 |
I1 = I0; |
| 535 |
++ii; |
| 536 |
} |
| 537 |
|
| 538 |
starting_level_ = static_cast<long>(big_nodes_.size() - 2); |
| 539 |
return {I1/omega, absolute_error_estimate/scale}; |
| 540 |
} |
| 541 |
|
| 542 |
private: |
| 543 |
|
| 544 |
template<class PreciseReal> |
| 545 |
void add_level(size_t i) { |
| 546 |
using std::abs; |
| 547 |
size_t current_num_levels = big_nodes_.size(); |
| 548 |
Real unit_roundoff = std::numeric_limits<Real>::epsilon()/2; |
| 549 |
PreciseReal h = PreciseReal(1)/PreciseReal(1<<i); |
| 550 |
|
| 551 |
std::vector<Real> bnode_row; |
| 552 |
std::vector<Real> bweight_row; |
| 553 |
bnode_row.reserve((static_cast<size_t>(1)<<i)*sizeof(Real)); |
| 554 |
bweight_row.reserve((static_cast<size_t>(1)<<i)*sizeof(Real)); |
| 555 |
|
| 556 |
std::vector<Real> lnode_row; |
| 557 |
std::vector<Real> lweight_row; |
| 558 |
|
| 559 |
lnode_row.reserve((static_cast<size_t>(1)<<i)*sizeof(Real)); |
| 560 |
lweight_row.reserve((static_cast<size_t>(1)<<i)*sizeof(Real)); |
| 561 |
|
| 562 |
Real max_weight = 1; |
| 563 |
auto alpha = calculate_ooura_alpha(h); |
| 564 |
long n = 0; |
| 565 |
Real w; |
| 566 |
do { |
| 567 |
auto precise_nw = ooura_cos_node_and_weight(n, h, alpha); |
| 568 |
Real node = static_cast<Real>(precise_nw.first); |
| 569 |
Real weight = static_cast<Real>(precise_nw.second); |
| 570 |
w = weight; |
| 571 |
if (bnode_row.size() == bnode_row.capacity()) { |
| 572 |
bnode_row.reserve(2*bnode_row.size()); |
| 573 |
bweight_row.reserve(2*bnode_row.size()); |
| 574 |
} |
| 575 |
|
| 576 |
bnode_row.push_back(node); |
| 577 |
bweight_row.push_back(weight); |
| 578 |
if (abs(weight) > max_weight) { |
| 579 |
max_weight = abs(weight); |
| 580 |
} |
| 581 |
++n; |
| 582 |
// f(t)->0 as t->infty, which is why the weights are computed up to the unit roundoff. |
| 583 |
} while(abs(w) > unit_roundoff*max_weight); |
| 584 |
|
| 585 |
bnode_row.shrink_to_fit(); |
| 586 |
bweight_row.shrink_to_fit(); |
| 587 |
n = -1; |
| 588 |
do { |
| 589 |
auto precise_nw = ooura_cos_node_and_weight(n, h, alpha); |
| 590 |
Real node = static_cast<Real>(precise_nw.first); |
| 591 |
// The function cannot be singular at zero, |
| 592 |
// so zero is not a unreasonable node, |
| 593 |
// unlike in the case of the Fourier Sine. |
| 594 |
// Hence only break if the node is negative. |
| 595 |
if (node < 0) { |
| 596 |
break; |
| 597 |
} |
| 598 |
Real weight = static_cast<Real>(precise_nw.second); |
| 599 |
w = weight; |
| 600 |
if (lnode_row.size() > 0) { |
| 601 |
if (lnode_row.back() == node) { |
| 602 |
// The nodes have fused into each other: |
| 603 |
break; |
| 604 |
} |
| 605 |
} |
| 606 |
if (lnode_row.size() == lnode_row.capacity()) { |
| 607 |
lnode_row.reserve(2*lnode_row.size()); |
| 608 |
lweight_row.reserve(2*lnode_row.size()); |
| 609 |
} |
| 610 |
|
| 611 |
lnode_row.push_back(node); |
| 612 |
lweight_row.push_back(weight); |
| 613 |
if (abs(weight) > max_weight) { |
| 614 |
max_weight = abs(weight); |
| 615 |
} |
| 616 |
--n; |
| 617 |
} while(abs(w) > (std::numeric_limits<Real>::min)()*max_weight); |
| 618 |
|
| 619 |
lnode_row.shrink_to_fit(); |
| 620 |
lweight_row.shrink_to_fit(); |
| 621 |
|
| 622 |
#ifdef BOOST_MATH_HAS_THREADS |
| 623 |
std::lock_guard<std::mutex> lock(node_weight_mutex_); |
| 624 |
#endif |
| 625 |
|
| 626 |
// Another thread might have already finished this calculation and appended it to the nodes/weights: |
| 627 |
if (current_num_levels == big_nodes_.size()) { |
| 628 |
big_nodes_.push_back(bnode_row); |
| 629 |
bweights_.push_back(bweight_row); |
| 630 |
|
| 631 |
little_nodes_.push_back(lnode_row); |
| 632 |
lweights_.push_back(lweight_row); |
| 633 |
} |
| 634 |
} |
| 635 |
|
| 636 |
template<class F> |
| 637 |
Real estimate_integral(F const & f, Real omega, size_t i) { |
| 638 |
Real I0 = 0; |
| 639 |
auto const & b_nodes = big_nodes_[i]; |
| 640 |
auto const & b_weights = bweights_[i]; |
| 641 |
Real inv_omega = 1/omega; |
| 642 |
for(size_t j = 0 ; j < b_nodes.size(); ++j) { |
| 643 |
I0 += f(b_nodes[j]*inv_omega)*b_weights[j]; |
| 644 |
} |
| 645 |
|
| 646 |
auto const & l_nodes = little_nodes_[i]; |
| 647 |
auto const & l_weights = lweights_[i]; |
| 648 |
for (size_t j = 0; j < l_nodes.size(); ++j) { |
| 649 |
I0 += f(l_nodes[j]*inv_omega)*l_weights[j]; |
| 650 |
} |
| 651 |
return I0; |
| 652 |
} |
| 653 |
|
| 654 |
#ifdef BOOST_MATH_HAS_THREADS |
| 655 |
std::mutex node_weight_mutex_; |
| 656 |
#endif |
| 657 |
|
| 658 |
std::vector<std::vector<Real>> big_nodes_; |
| 659 |
std::vector<std::vector<Real>> bweights_; |
| 660 |
|
| 661 |
std::vector<std::vector<Real>> little_nodes_; |
| 662 |
std::vector<std::vector<Real>> lweights_; |
| 663 |
Real rel_err_goal_; |
| 664 |
|
| 665 |
#ifdef BOOST_MATH_HAS_THREADS |
| 666 |
std::atomic<long> starting_level_{}; |
| 667 |
#else |
| 668 |
long starting_level_; |
| 669 |
#endif |
| 670 |
|
| 671 |
size_t requested_levels_; |
| 672 |
}; |
| 673 |
|
| 674 |
|
| 675 |
}}}} |
| 676 |
#endif |