From 4c9004671af455a03acb4e2750b12d62b2b3c917 Mon Sep 17 00:00:00 2001 From: Ferenc Arn Date: Sat, 14 Jan 2017 23:34:51 -0600 Subject: Replace the existing PRNG (Xorshift31) with (minimal) PCG (XSH-RR variant with 32-bit output, 64-bit state). PCG is better than many alternatives by many metrics (see www.pcg-random.org) including statistical quality with good speed. --- core/math/math_funcs.cpp | 25 ++++++++++++------------- core/math/math_funcs.h | 7 ++++--- core/math/pcg.cpp | 15 +++++++++++++++ core/math/pcg.h | 14 ++++++++++++++ 4 files changed, 45 insertions(+), 16 deletions(-) create mode 100644 core/math/pcg.cpp create mode 100644 core/math/pcg.h (limited to 'core') diff --git a/core/math/math_funcs.cpp b/core/math/math_funcs.cpp index 8353aa0ebe..ef8c1ec539 100644 --- a/core/math/math_funcs.cpp +++ b/core/math/math_funcs.cpp @@ -31,8 +31,9 @@ #include "core/os/os.h" #include "float.h" -uint32_t Math::default_seed=1; +#include "pcg.h" +pcg32_random_t Math::default_pcg = {1, PCG_DEFAULT_INC_64}; #define PHI 0x9e3779b9 @@ -40,28 +41,26 @@ uint32_t Math::default_seed=1; static uint32_t Q[4096]; #endif -uint32_t Math::rand_from_seed(uint32_t *seed) { - // Xorshift31 PRNG - if ( *seed == 0 ) *seed = Math::RANDOM_MAX; - (*seed) ^= (*seed) << 13; - (*seed) ^= (*seed) >> 17; - (*seed) ^= (*seed) << 5; - return (*seed) & Math::RANDOM_MAX; +// TODO: we should eventually expose pcg.inc too +uint32_t Math::rand_from_seed(uint64_t *seed) { + pcg32_random_t pcg = {*seed, PCG_DEFAULT_INC_64}; + uint32_t r = pcg32_random_r(&pcg); + *seed = pcg.state; + return r; } -void Math::seed(uint32_t x) { - default_seed=x; +void Math::seed(uint64_t x) { + default_pcg.state=x; } void Math::randomize() { OS::Time time = OS::get_singleton()->get_time(); - seed(OS::get_singleton()->get_ticks_usec()*(time.hour+1)*(time.min+1)*(time.sec+1)*rand()); /* *OS::get_singleton()->get_time().sec); // windows doesn't have get_time(), returns always 0 */ + seed(OS::get_singleton()->get_ticks_usec()*(time.hour+1)*(time.min+1)*(time.sec+1)*rand()); // TODO: can be simplified. } uint32_t Math::rand() { - - return rand_from_seed(&default_seed); + return pcg32_random_r(&default_pcg); } double Math::randf() { diff --git a/core/math/math_funcs.h b/core/math/math_funcs.h index 8ce59224ff..e81646b1ca 100644 --- a/core/math/math_funcs.h +++ b/core/math/math_funcs.h @@ -31,6 +31,7 @@ #include "typedefs.h" #include "math_defs.h" +#include "pcg.h" #ifndef NO_MATH_H #include @@ -41,8 +42,8 @@ class Math { + static pcg32_random_t default_pcg; - static uint32_t default_seed; public: Math() {} // useless to instance @@ -150,12 +151,12 @@ public: } - static uint32_t rand_from_seed(uint32_t *seed); + static uint32_t rand_from_seed(uint64_t *seed); static double ease(double p_x, double p_c); static int step_decimals(double p_step); static double stepify(double p_value,double p_step); - static void seed(uint32_t x=0); + static void seed(uint64_t x=0); static void randomize(); static uint32_t larger_prime(uint32_t p_val); static double dectime(double p_value,double p_amount, double p_step); diff --git a/core/math/pcg.cpp b/core/math/pcg.cpp new file mode 100644 index 0000000000..eac3b36d36 --- /dev/null +++ b/core/math/pcg.cpp @@ -0,0 +1,15 @@ +// *Really* minimal PCG32 code / (c) 2014 M.E. O'Neill / pcg-random.org +// Licensed under Apache License 2.0 (NO WARRANTY, etc. see website) + +#include "pcg.h" + +uint32_t pcg32_random_r(pcg32_random_t* rng) +{ + uint64_t oldstate = rng->state; + // Advance internal state + rng->state = oldstate * 6364136223846793005ULL + (rng->inc|1); + // Calculate output function (XSH RR), uses old state for max ILP + uint32_t xorshifted = ((oldstate >> 18u) ^ oldstate) >> 27u; + uint32_t rot = oldstate >> 59u; + return (xorshifted >> rot) | (xorshifted << ((-rot) & 31)); +} diff --git a/core/math/pcg.h b/core/math/pcg.h new file mode 100644 index 0000000000..81f4c9770e --- /dev/null +++ b/core/math/pcg.h @@ -0,0 +1,14 @@ +// *Really* minimal PCG32 code / (c) 2014 M.E. O'Neill / pcg-random.org +// Licensed under Apache License 2.0 (NO WARRANTY, etc. see website) + +#ifndef RANDOM_H +#define RANDOM_H + +#include "typedefs.h" + +#define PCG_DEFAULT_INC_64 1442695040888963407ULL + +typedef struct { uint64_t state; uint64_t inc; } pcg32_random_t; +uint32_t pcg32_random_r(pcg32_random_t* rng); + +#endif // RANDOM_H -- cgit v1.2.3