From 31faa1f22626b8745ed4a1541497832b6f595df2 Mon Sep 17 00:00:00 2001 From: Yuri Roubinsky Date: Thu, 29 Oct 2020 15:40:53 +0300 Subject: Fix biased output of randi_range --- thirdparty/misc/pcg.cpp | 10 ++++++++++ thirdparty/misc/pcg.h | 1 + 2 files changed, 11 insertions(+) (limited to 'thirdparty/misc') diff --git a/thirdparty/misc/pcg.cpp b/thirdparty/misc/pcg.cpp index c421e16f89..5f4bf40460 100644 --- a/thirdparty/misc/pcg.cpp +++ b/thirdparty/misc/pcg.cpp @@ -23,3 +23,13 @@ void pcg32_srandom_r(pcg32_random_t* rng, uint64_t initstate, uint64_t initseq) rng->state += initstate; pcg32_random_r(rng); } + +// Source from https://github.com/imneme/pcg-c-basic/blob/master/pcg_basic.c +uint32_t pcg32_boundedrand_r(pcg32_random_t *rng, uint32_t bound) { + uint32_t threshold = -bound % bound; + for (;;) { + uint32_t r = pcg32_random_r(rng); + if (r >= threshold) + return r % bound; + } +} diff --git a/thirdparty/misc/pcg.h b/thirdparty/misc/pcg.h index 6f42b3b094..0faab73e64 100644 --- a/thirdparty/misc/pcg.h +++ b/thirdparty/misc/pcg.h @@ -11,5 +11,6 @@ typedef struct { uint64_t state; uint64_t inc; } pcg32_random_t; uint32_t pcg32_random_r(pcg32_random_t* rng); void pcg32_srandom_r(pcg32_random_t* rng, uint64_t initstate, uint64_t initseq); +uint32_t pcg32_boundedrand_r(pcg32_random_t* rng, uint32_t bound); #endif // RANDOM_H -- cgit v1.2.3