Debian Codegraph @

third-party/boost-math/include/boost/math/quadrature/naive_monte_carlo.hpp

raw
1 /*
2 * Copyright Nick Thompson, 2018
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_QUADRATURE_NAIVE_MONTE_CARLO_HPP
8 #define BOOST_MATH_QUADRATURE_NAIVE_MONTE_CARLO_HPP
9 #include <sstream>
10 #include <algorithm>
11 #include <vector>
12 #include <atomic>
13 #include <memory>
14 #include <functional>
15 #include <future>
16 #include <thread>
17 #include <initializer_list>
18 #include <utility>
19 #include <random>
20 #include <chrono>
21 #include <map>
22 #include <type_traits>
23 #include <boost/math/policies/error_handling.hpp>
24 #include <boost/math/special_functions/fpclassify.hpp>
25
26 #ifdef BOOST_NAIVE_MONTE_CARLO_DEBUG_FAILURES
27 # include <iostream>
28 #endif
29
30 namespace boost { namespace math { namespace quadrature {
31
32 namespace detail {
33 enum class limit_classification {FINITE,
34 LOWER_BOUND_INFINITE,
35 UPPER_BOUND_INFINITE,
36 DOUBLE_INFINITE};
37 }
38
39 template<class Real, class F, class RandomNumberGenerator = std::mt19937_64, class Policy = boost::math::policies::policy<>,
40 typename std::enable_if<std::is_trivially_copyable<Real>::value, bool>::type = true>
41 class naive_monte_carlo
42 {
43 public:
44 naive_monte_carlo(const F& integrand,
45 std::vector<std::pair<Real, Real>> const & bounds,
46 Real error_goal,
47 bool singular = true,
48 uint64_t threads = std::thread::hardware_concurrency(),
49 uint64_t seed = 0) noexcept : m_num_threads{threads}, m_seed{seed}, m_volume(1)
50 {
51 using std::numeric_limits;
52 using std::sqrt;
53 using boost::math::isinf;
54
55 uint64_t n = bounds.size();
56 m_lbs.resize(n);
57 m_dxs.resize(n);
58 m_limit_types.resize(n);
59
60 static const char* function = "boost::math::quadrature::naive_monte_carlo<%1%>";
61 for (uint64_t i = 0; i < n; ++i)
62 {
63 if (bounds[i].second <= bounds[i].first)
64 {
65 boost::math::policies::raise_domain_error(function, "The upper bound is <= the lower bound.\n", bounds[i].second, Policy());
66 return;
67 }
68 if (isinf(bounds[i].first))
69 {
70 if (isinf(bounds[i].second))
71 {
72 m_limit_types[i] = detail::limit_classification::DOUBLE_INFINITE;
73 }
74 else
75 {
76 m_limit_types[i] = detail::limit_classification::LOWER_BOUND_INFINITE;
77 // Ok ok this is bad to use the second bound as the lower limit and then reflect.
78 m_lbs[i] = bounds[i].second;
79 m_dxs[i] = numeric_limits<Real>::quiet_NaN();
80 }
81 }
82 else if (isinf(bounds[i].second))
83 {
84 m_limit_types[i] = detail::limit_classification::UPPER_BOUND_INFINITE;
85 if (singular)
86 {
87 // I've found that it's easier to sample on a closed set and perturb the boundary
88 // than to try to sample very close to the boundary.
89 m_lbs[i] = std::nextafter(bounds[i].first, (std::numeric_limits<Real>::max)());
90 }
91 else
92 {
93 m_lbs[i] = bounds[i].first;
94 }
95 m_dxs[i] = numeric_limits<Real>::quiet_NaN();
96 }
97 else
98 {
99 m_limit_types[i] = detail::limit_classification::FINITE;
100 if (singular)
101 {
102 if (bounds[i].first == 0)
103 {
104 m_lbs[i] = std::numeric_limits<Real>::epsilon();
105 }
106 else
107 {
108 m_lbs[i] = std::nextafter(bounds[i].first, (std::numeric_limits<Real>::max)());
109 }
110
111 m_dxs[i] = std::nextafter(bounds[i].second, std::numeric_limits<Real>::lowest()) - m_lbs[i];
112 }
113 else
114 {
115 m_lbs[i] = bounds[i].first;
116 m_dxs[i] = bounds[i].second - bounds[i].first;
117 }
118 m_volume *= m_dxs[i];
119 }
120 }
121
122 m_integrand = [this, &integrand](std::vector<Real> & x)->Real
123 {
124 Real coeff = m_volume;
125 for (uint64_t i = 0; i < x.size(); ++i)
126 {
127 // Variable transformation are listed at:
128 // https://en.wikipedia.org/wiki/Numerical_integration
129 // However, we've made some changes to these so that we can evaluate on a compact domain.
130 if (m_limit_types[i] == detail::limit_classification::FINITE)
131 {
132 x[i] = m_lbs[i] + x[i]*m_dxs[i];
133 }
134 else if (m_limit_types[i] == detail::limit_classification::UPPER_BOUND_INFINITE)
135 {
136 Real t = x[i];
137 Real z = 1/(1 + numeric_limits<Real>::epsilon() - t);
138 coeff *= (z*z)*(1 + numeric_limits<Real>::epsilon());
139 x[i] = m_lbs[i] + t*z;
140 }
141 else if (m_limit_types[i] == detail::limit_classification::LOWER_BOUND_INFINITE)
142 {
143 Real t = x[i];
144 Real z = 1/(t+sqrt((numeric_limits<Real>::min)()));
145 coeff *= (z*z);
146 x[i] = m_lbs[i] + (t-1)*z;
147 }
148 else
149 {
150 Real t1 = 1/(1+numeric_limits<Real>::epsilon() - x[i]);
151 Real t2 = 1/(x[i]+numeric_limits<Real>::epsilon());
152 x[i] = (2*x[i]-1)*t1*t2/4;
153 coeff *= (t1*t1+t2*t2)/4;
154 }
155 }
156 return coeff*integrand(x);
157 };
158
159 // If we don't do a single function call in the constructor,
160 // we can't do a restart.
161 std::vector<Real> x(m_lbs.size());
162
163 // If the seed is zero, that tells us to choose a random seed for the user:
164 if (seed == 0)
165 {
166 std::random_device rd;
167 seed = rd();
168 }
169
170 RandomNumberGenerator gen(seed);
171 Real inv_denom = 1/static_cast<Real>(((gen.max)()-(gen.min)()));
172
173 m_num_threads = (std::max)(m_num_threads, static_cast<uint64_t>(1));
174 m_thread_calls.reset(new std::atomic<uint64_t>[threads]);
175 m_thread_Ss.reset(new std::atomic<Real>[threads]);
176 m_thread_averages.reset(new std::atomic<Real>[threads]);
177
178 Real avg = 0;
179 for (uint64_t i = 0; i < m_num_threads; ++i)
180 {
181 for (uint64_t j = 0; j < m_lbs.size(); ++j)
182 {
183 x[j] = (gen()-(gen.min)())*inv_denom;
184 }
185 Real y = m_integrand(x);
186 m_thread_averages[i] = y; // relaxed store
187 m_thread_calls[i] = 1;
188 m_thread_Ss[i] = 0;
189 avg += y;
190 }
191 avg /= m_num_threads;
192 m_avg = avg; // relaxed store
193
194 m_error_goal = error_goal; // relaxed store
195 m_start = std::chrono::system_clock::now();
196 m_done = false; // relaxed store
197 m_total_calls = m_num_threads; // relaxed store
198 m_variance = (numeric_limits<Real>::max)();
199 }
200
201 std::future<Real> integrate()
202 {
203 // Set done to false in case we wish to restart:
204 m_done.store(false); // relaxed store, no worker threads yet
205 m_start = std::chrono::system_clock::now();
206 return std::async(std::launch::async,
207 &naive_monte_carlo::m_integrate, this);
208 }
209
210 void cancel()
211 {
212 // If seed = 0 (meaning have the routine pick the seed), this leaves the seed the same.
213 // If seed != 0, then the seed is changed, so a restart doesn't do the exact same thing.
214 m_seed = m_seed*m_seed;
215 m_done = true; // relaxed store, worker threads will get the message eventually
216 // Make sure the error goal is infinite, because otherwise we'll loop when we do the final error goal check:
217 m_error_goal = (std::numeric_limits<Real>::max)();
218 }
219
220 Real variance() const
221 {
222 return m_variance.load();
223 }
224
225 Real current_error_estimate() const
226 {
227 using std::sqrt;
228 //
229 // There is a bug here: m_variance and m_total_calls get updated asynchronously
230 // and may be out of synch when we compute the error estimate, not sure if it matters though...
231 //
232 return sqrt(m_variance.load()/m_total_calls.load());
233 }
234
235 std::chrono::duration<Real> estimated_time_to_completion() const
236 {
237 auto now = std::chrono::system_clock::now();
238 std::chrono::duration<Real> elapsed_seconds = now - m_start;
239 Real r = this->current_error_estimate()/m_error_goal.load(); // relaxed load
240 if (r*r <= 1) {
241 return 0*elapsed_seconds;
242 }
243 return (r*r - 1)*elapsed_seconds;
244 }
245
246 void update_target_error(Real new_target_error)
247 {
248 m_error_goal = new_target_error; // relaxed store
249 }
250
251 Real progress() const
252 {
253 Real r = m_error_goal.load()/this->current_error_estimate(); // relaxed load
254 if (r*r >= 1)
255 {
256 return 1;
257 }
258 return r*r;
259 }
260
261 Real current_estimate() const
262 {
263 return m_avg.load();
264 }
265
266 uint64_t calls() const
267 {
268 return m_total_calls.load(); // relaxed load
269 }
270
271 private:
272
273 Real m_integrate()
274 {
275 uint64_t seed;
276 // If the user tells us to pick a seed, pick a seed:
277 if (m_seed == 0)
278 {
279 std::random_device rd;
280 seed = rd();
281 }
282 else // use the seed we are given:
283 {
284 seed = m_seed;
285 }
286 RandomNumberGenerator gen(seed);
287 int max_repeat_tries = 5;
288 do{
289
290 if (max_repeat_tries < 5)
291 {
292 m_done = false;
293
294 #ifdef BOOST_NAIVE_MONTE_CARLO_DEBUG_FAILURES
295 std::cerr << "Failed to achieve required tolerance first time through..\n";
296 std::cerr << " variance = " << m_variance << std::endl;
297 std::cerr << " average = " << m_avg << std::endl;
298 std::cerr << " total calls = " << m_total_calls << std::endl;
299
300 for (std::size_t i = 0; i < m_num_threads; ++i)
301 std::cerr << " thread_calls[" << i << "] = " << m_thread_calls[i] << std::endl;
302 for (std::size_t i = 0; i < m_num_threads; ++i)
303 std::cerr << " thread_averages[" << i << "] = " << m_thread_averages[i] << std::endl;
304 for (std::size_t i = 0; i < m_num_threads; ++i)
305 std::cerr << " thread_Ss[" << i << "] = " << m_thread_Ss[i] << std::endl;
306 #endif
307 }
308
309 std::vector<std::thread> threads(m_num_threads);
310 for (uint64_t i = 0; i < threads.size(); ++i)
311 {
312 threads[i] = std::thread(&naive_monte_carlo::m_thread_monte, this, i, gen());
313 }
314 do {
315 std::this_thread::sleep_for(std::chrono::milliseconds(100));
316 uint64_t total_calls = 0;
317 for (uint64_t i = 0; i < m_num_threads; ++i)
318 {
319 uint64_t t_calls = m_thread_calls[i].load(std::memory_order_consume);
320 total_calls += t_calls;
321 }
322 Real variance = 0;
323 Real avg = 0;
324 for (uint64_t i = 0; i < m_num_threads; ++i)
325 {
326 uint64_t t_calls = m_thread_calls[i].load(std::memory_order_consume);
327 // Will this overflow? Not hard to remove . . .
328 avg += m_thread_averages[i].load(std::memory_order_relaxed)*(static_cast<Real>(t_calls) / static_cast<Real>(total_calls));
329 variance += m_thread_Ss[i].load(std::memory_order_relaxed);
330 }
331 m_avg.store(avg, std::memory_order_release);
332 m_variance.store(variance / (total_calls - 1), std::memory_order_release);
333 m_total_calls = total_calls; // relaxed store, it's just for user feedback
334 // Allow cancellation:
335 if (m_done) // relaxed load
336 {
337 break;
338 }
339 } while (m_total_calls < 2048 || this->current_error_estimate() > m_error_goal.load(std::memory_order_consume));
340 // Error bound met; signal the threads:
341 m_done = true; // relaxed store, threads will get the message in the end
342 std::for_each(threads.begin(), threads.end(),
343 std::mem_fn(&std::thread::join));
344 if (m_exception)
345 {
346 std::rethrow_exception(m_exception);
347 }
348 // Incorporate their work into the final estimate:
349 uint64_t total_calls = 0;
350 for (uint64_t i = 0; i < m_num_threads; ++i)
351 {
352 uint64_t t_calls = m_thread_calls[i].load(std::memory_order_consume);
353 total_calls += t_calls;
354 }
355 Real variance = 0;
356 Real avg = 0;
357
358 for (uint64_t i = 0; i < m_num_threads; ++i)
359 {
360 uint64_t t_calls = m_thread_calls[i].load(std::memory_order_consume);
361 // Averages weighted by the number of calls the thread made:
362 avg += m_thread_averages[i].load(std::memory_order_relaxed)*(static_cast<Real>(t_calls) / static_cast<Real>(total_calls));
363 variance += m_thread_Ss[i].load(std::memory_order_relaxed);
364 }
365 m_avg.store(avg, std::memory_order_release);
366 m_variance.store(variance / (total_calls - 1), std::memory_order_release);
367 m_total_calls = total_calls; // relaxed store, this is just user feedback
368
369 // Sometimes, the master will observe the variance at a very "good" (or bad?) moment,
370 // Then the threads proceed to find the variance is much greater by the time they hear the message to stop.
371 // This *WOULD* make sure that the final error estimate is within the error bounds.
372 }
373 while ((--max_repeat_tries >= 0) && (this->current_error_estimate() > m_error_goal));
374
375 return m_avg.load(std::memory_order_consume);
376 }
377
378 void m_thread_monte(uint64_t thread_index, uint64_t seed)
379 {
380 using std::numeric_limits;
381 try
382 {
383 std::vector<Real> x(m_lbs.size());
384 RandomNumberGenerator gen(seed);
385 Real inv_denom = static_cast<Real>(1) / static_cast<Real>(( (gen.max)() - (gen.min)() ));
386 Real M1 = m_thread_averages[thread_index].load(std::memory_order_consume);
387 Real S = m_thread_Ss[thread_index].load(std::memory_order_consume);
388 // Kahan summation is required or the value of the integrand will go on a random walk during long computations.
389 // See the implementation discussion.
390 // The idea is that the unstabilized additions have error sigma(f)/sqrt(N) + epsilon*N, which diverges faster than it converges!
391 // Kahan summation turns this to sigma(f)/sqrt(N) + epsilon^2*N, and the random walk occurs on a timescale of 10^14 years (on current hardware)
392 Real compensator = 0;
393 uint64_t k = m_thread_calls[thread_index].load(std::memory_order_consume);
394 while (!m_done) // relaxed load
395 {
396 int j = 0;
397 // If we don't have a certain number of calls before an update, we can easily terminate prematurely
398 // because the variance estimate is way too low. This magic number is a reasonable compromise, as 1/sqrt(2048) = 0.02,
399 // so it should recover 2 digits if the integrand isn't poorly behaved, and if it is, it should discover that before premature termination.
400 // Of course if the user has 64 threads, then this number is probably excessive.
401 int magic_calls_before_update = 2048;
402 while (j++ < magic_calls_before_update)
403 {
404 for (uint64_t i = 0; i < m_lbs.size(); ++i)
405 {
406 x[i] = (gen() - (gen.min)())*inv_denom;
407 }
408 Real f = m_integrand(x);
409 using std::isfinite;
410 if (!isfinite(f))
411 {
412 // The call to m_integrand transform x, so this error message states the correct node.
413 std::stringstream os;
414 os << "Your integrand was evaluated at {";
415 for (uint64_t i = 0; i < x.size() -1; ++i)
416 {
417 os << x[i] << ", ";
418 }
419 os << x[x.size() -1] << "}, and returned " << f << std::endl;
420 static const char* function = "boost::math::quadrature::naive_monte_carlo<%1%>";
421 boost::math::policies::raise_domain_error(function, os.str().c_str(), /*this is a dummy arg to make it compile*/ 7.2, Policy());
422 }
423 ++k;
424 Real term = (f - M1)/k;
425 Real y1 = term - compensator;
426 Real M2 = M1 + y1;
427 compensator = (M2 - M1) - y1;
428 S += (f - M1)*(f - M2);
429 M1 = M2;
430 }
431 m_thread_averages[thread_index].store(M1, std::memory_order_release);
432 m_thread_Ss[thread_index].store(S, std::memory_order_release);
433 m_thread_calls[thread_index].store(k, std::memory_order_release);
434 }
435 }
436 catch (...)
437 {
438 // Signal the other threads that the computation is ruined:
439 m_done = true; // relaxed store
440 std::lock_guard<std::mutex> lock(m_exception_mutex); // Scoped lock to prevent race writing to m_exception
441 m_exception = std::current_exception();
442 }
443 }
444
445 std::function<Real(std::vector<Real> &)> m_integrand;
446 uint64_t m_num_threads;
447 std::atomic<uint64_t> m_seed;
448 std::atomic<Real> m_error_goal;
449 std::atomic<bool> m_done{};
450 std::vector<Real> m_lbs;
451 std::vector<Real> m_dxs;
452 std::vector<detail::limit_classification> m_limit_types;
453 Real m_volume;
454 std::atomic<uint64_t> m_total_calls{};
455 // I wanted these to be vectors rather than maps,
456 // but you can't resize a vector of atomics.
457 std::unique_ptr<std::atomic<uint64_t>[]> m_thread_calls;
458 std::atomic<Real> m_variance;
459 std::unique_ptr<std::atomic<Real>[]> m_thread_Ss;
460 std::atomic<Real> m_avg;
461 std::unique_ptr<std::atomic<Real>[]> m_thread_averages;
462 std::chrono::time_point<std::chrono::system_clock> m_start;
463 std::exception_ptr m_exception;
464 std::mutex m_exception_mutex;
465 };
466
467 }}}
468 #endif