Last active
March 13, 2017 13:02
-
-
Save mkurdej/b0697cd751407d7e142083263733c88f to your computer and use it in GitHub Desktop.
Pi day challenge
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <random> | |
template <typename T> | |
struct point_2d { | |
T x, y; | |
}; | |
static std::random_device random_device; | |
static std::mt19937 random_engine{random_device()}; | |
template <typename T> | |
point_2d<T> generate_random_point(T max_coordinate) { | |
std::uniform_real_distribution<T> coordinate_distribution(-max_coordinate, max_coordinate); | |
auto generate_coordinate = [&] { | |
return coordinate_distribution(random_engine); | |
}; | |
return {generate_coordinate(), generate_coordinate()}; | |
} | |
template <typename T> | |
T hypothenus_squared(const point_2d<T> & point) { | |
return (point.x * point.x) + (point.y * point.y); | |
} | |
template <typename T> | |
bool is_in_circle(const point_2d<T> & point, T radius_squared) { | |
return hypothenus_squared(point) <= radius_squared; | |
} | |
template <typename T> | |
struct irange | |
{ | |
irange(T first, T last) : _first(first), _last(last) {} | |
struct irange_iterator : public std::iterator_traits<T> { | |
using value_type = T; | |
using difference_type = std::ptrdiff_t; | |
using pointer = T*; | |
using reference = T&; | |
using iterator_category = std::input_iterator_tag; | |
explicit irange_iterator(T val) : _value{val} {} | |
irange_iterator & operator++() { ++_value; return *this; } | |
bool operator!=(const irange_iterator & other) { return _value != other._value; } | |
T operator*() { return _value; } | |
private: | |
T _value; | |
}; | |
irange_iterator begin() { return irange_iterator{_first}; } | |
irange_iterator end() { return irange_iterator{_last}; } | |
bool operator==(const irange & /*other*/) { return false; } | |
private: | |
const T _first; | |
const T _last; | |
}; | |
template <typename T> | |
T compute_pi_approximate(T radius, size_t samples) { | |
static_assert(std::is_floating_point_v<T>, "radius type should be floating-point"); | |
const T radius_squared = radius * radius; | |
irange<size_t> sample_range(0u, samples); | |
auto samples_in_circle = std::count_if(sample_range.begin(), sample_range.end(), [&](auto) { | |
return is_in_circle(generate_random_point(radius), radius_squared); | |
}); | |
static const T quadrant_count = 4; | |
return quadrant_count * samples_in_circle / samples; | |
} | |
#include <algorithm> | |
#include <iomanip> | |
#include <iostream> | |
#include <vector> | |
template <typename T> | |
auto generate_exponents_of(T multiplier, int n) { | |
std::vector<int> out(n + 1); | |
std::generate_n(out.begin(), out.size(), [=, v = 1]() mutable { return std::exchange(v, v * multiplier); }); | |
return out; | |
} | |
int main() | |
{ | |
static const double reference_pi = 3.14159265359; | |
auto generate_exponents_of_10 = [](int n) { | |
return generate_exponents_of(/*multiplier=*/10.0, n); | |
}; | |
for (double radius : generate_exponents_of_10(9)) { | |
for (size_t samples : generate_exponents_of_10(7)) { | |
auto our_pi = compute_pi_approximate(radius, samples); | |
std::cout << std::fixed << std::setprecision(8) << std::abs(our_pi - reference_pi) << ' '; | |
} | |
std::cout << '\n'; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment