Replace used <random> methods by own.

This makes our random numbers cross-platform.

2 files changed, 86 insertions, 9 deletions

diff --git a/src/random.cc b/src/random.cc
index 3d94a25..f6b5b34 100644
--- a/src/random.cc
+++ b/src/random.cc
@@ -27,6 +27,8 @@
 #include "random.h"
 
 #include <chrono>
+#include <type_traits>
+#include <cmath>
 
 Random::Random()
 	: Random(std::chrono::system_clock::now().time_since_epoch().count())
@@ -45,18 +47,89 @@ void Random::setSeed(unsigned int seed)
 
 int Random::intInRange(int lower_bound, int upper_bound)
 {
-	std::uniform_int_distribution<int> distribution(lower_bound, upper_bound);
-	return distribution(generator);
+	auto generate = [this]()
+	{
+		return (int)generator() - generator.min();
+	};
+
+	const int in_range = generator.max() - generator.min();
+	const int out_range = upper_bound - lower_bound;
+
+	int rand;
+
+	// scale in_range DOWN to out_range.
+	// (see: http://www.azillionmonkeys.com/qed/random.html)
+	if (in_range > out_range)
+	{
+		const int rand_inv_range = in_range / (out_range + 1);
+
+		do
+		{
+			rand = generate();
+		}
+		while (rand >= (out_range + 1) * rand_inv_range);
+
+		rand = lower_bound + rand/rand_inv_range;
+	}
+	// scale in_range UP to out_range.
+	// (see: http://stackoverflow.com/a/30738381)
+	else if (in_range < out_range)
+	{
+		int scale = out_range / (in_range + 1);
+
+		do
+		{
+			rand = generate() + intInRange(0, scale) * (in_range + 1);
+		}
+		while (rand < lower_bound && rand > upper_bound);
+
+		rand = lower_bound + rand;
+	}
+	// naive case
+	else
+	{
+		rand = lower_bound + generate();
+	}
+
+	return rand;
 }
 
 float Random::floatInRange(float lower_bound, float upper_bound)
 {
-	std::uniform_real_distribution<float> distribution(lower_bound, upper_bound);
-	return distribution(generator);
+	return generateFloat() * (upper_bound - lower_bound) + lower_bound;
 }
 
+// For details regarding the algorithm see:
+// https://en.wikipedia.org/wiki/Marsaglia_polar_method
 float Random::normalDistribution(float mean, float stddev)
 {
-	std::normal_distribution<float> distribution(mean, stddev);
-	return distribution(generator);
+	if (has_saved_value)
+	{
+		has_saved_value = false;
+		return saved_value * stddev + mean;
+	}
+	else
+	{
+		float u, v, s;
+		do
+		{
+			u = 2.0f*generateFloat() - 1;
+			v = 2.0f*generateFloat() - 1;
+			s = (u * u) + (v * v);
+		}
+		while (s > 1.0f || s == 0.0f);
+
+		s = std::sqrt(-2*std::log(s) / s);
+		saved_value = u * s;
+		has_saved_value = true;
+
+		return mean + stddev * (v * s);
+	}
+}
+
+float Random::generateFloat()
+{
+	return std::generate_canonical<float,
+	                               std::numeric_limits<float>::digits,
+	                               decltype(generator)>(generator);
 }
diff --git a/src/random.h b/src/random.h
index a18f5b6..7f53c05 100644
--- a/src/random.h
+++ b/src/random.h
@@ -56,12 +56,16 @@ private:
 	// minstd_rand0, so make sure we use that all platforms regardless of which
 	// stdlib we link with.
 	std::minstd_rand0 generator;
+
+	float generateFloat();
+
+	// variables for normalDistribution
+	bool has_saved_value = false;
+	float saved_value;
 };
 
 template <typename T>
 T& Random::choose(std::vector<T>& vec)
 {
-	std::uniform_int_distribution<size_t> distribution(0, vec.size()-1);
-	size_t rand_index = distribution(generator);
-	return vec[rand_index];
+	return vec[intInRange(0, vec.size() - 1)];
 }