Merge pull request #40718 from Chaosus/rand_range

Exposed randi_range to global funcs + renamed rand_range to randf_range

1 files changed, 23 insertions, 0 deletions

diff --git a/thirdparty/misc/pcg.cpp b/thirdparty/misc/pcg.cpp
index 5f4bf40460..914a353874 100644
--- a/thirdparty/misc/pcg.cpp
+++ b/thirdparty/misc/pcg.cpp
@@ -25,8 +25,31 @@ void pcg32_srandom_r(pcg32_random_t* rng, uint64_t initstate, uint64_t initseq)
 }
 
 // Source from https://github.com/imneme/pcg-c-basic/blob/master/pcg_basic.c
+// pcg32_boundedrand_r(rng, bound):
+//     Generate a uniformly distributed number, r, where 0 <= r < bound
 uint32_t pcg32_boundedrand_r(pcg32_random_t *rng, uint32_t bound) {
+	// To avoid bias, we need to make the range of the RNG a multiple of
+	// bound, which we do by dropping output less than a threshold.
+	// A naive scheme to calculate the threshold would be to do
+	//
+	//     uint32_t threshold = 0x100000000ull % bound;
+	//
+	// but 64-bit div/mod is slower than 32-bit div/mod (especially on
+	// 32-bit platforms).  In essence, we do
+	//
+	//     uint32_t threshold = (0x100000000ull-bound) % bound;
+	//
+	// because this version will calculate the same modulus, but the LHS
+	// value is less than 2^32.
 	uint32_t threshold = -bound % bound;
+
+	// Uniformity guarantees that this loop will terminate.  In practice, it
+	// should usually terminate quickly; on average (assuming all bounds are
+	// equally likely), 82.25% of the time, we can expect it to require just
+	// one iteration.  In the worst case, someone passes a bound of 2^31 + 1
+	// (i.e., 2147483649), which invalidates almost 50% of the range.  In
+	// practice, bounds are typically small and only a tiny amount of the range
+	// is eliminated.
 	for (;;) {
 		uint32_t r = pcg32_random_r(rng);
 		if (r >= threshold)