From f5e475d44ffe9db1647c3f7d086faab1bbc83402 Mon Sep 17 00:00:00 2001 From: "madmaxoft@gmail.com" Date: Thu, 11 Jul 2013 08:34:41 +0000 Subject: Added the cFastRandom class git-svn-id: http://mc-server.googlecode.com/svn/trunk@1672 0a769ca7-a7f5-676a-18bf-c427514a06d6 --- source/FastRandom.cpp | 174 ++++++++++++++++++++++++++++++++++++++++++++++++++ source/FastRandom.h | 57 +++++++++++++++++ 2 files changed, 231 insertions(+) create mode 100644 source/FastRandom.cpp create mode 100644 source/FastRandom.h (limited to 'source') diff --git a/source/FastRandom.cpp b/source/FastRandom.cpp new file mode 100644 index 000000000..b778fb4bb --- /dev/null +++ b/source/FastRandom.cpp @@ -0,0 +1,174 @@ + +// FastRandom.cpp + +// Implements the cFastRandom class representing a fast random number generator + +#include "Globals.h" +#include +#include "FastRandom.h" + + + + + +#if 0 && defined(_DEBUG) +// Self-test +// Both ints and floats are quick-tested to see if the random is calculated correctly, checking the range in ASSERTs, +// and if it performs well in terms of distribution (checked by avg, expected to be in the range midpoint +class cFastRandomTest +{ +public: + cFastRandomTest(void) + { + TestInts(); + TestFloats(); + } + + + void TestInts(void) + { + printf("Testing ints...\n"); + cFastRandom rnd; + int sum = 0; + const int BUCKETS = 8; + int Counts[BUCKETS]; + memset(Counts, 0, sizeof(Counts)); + const int ITER = 10000; + for (int i = 0; i < ITER; i++) + { + int v = rnd.NextInt(1000); + ASSERT(v >= 0); + ASSERT(v < 1000); + Counts[v % BUCKETS]++; + sum += v; + } + double avg = (double)sum / ITER; + printf("avg: %f\n", avg); + for (int i = 0; i < BUCKETS; i++) + { + printf(" bucket %d: %d\n", i, Counts[i]); + } + } + + + void TestFloats(void) + { + printf("Testing floats...\n"); + cFastRandom rnd; + float sum = 0; + const int BUCKETS = 8; + int Counts[BUCKETS]; + memset(Counts, 0, sizeof(Counts)); + const int ITER = 10000; + for (int i = 0; i < ITER; i++) + { + float v = rnd.NextFloat(1000); + ASSERT(v >= 0); + ASSERT(v <= 1000); + Counts[((int)v) % BUCKETS]++; + sum += v; + } + sum = sum / ITER; + printf("avg: %f\n", sum); + for (int i = 0; i < BUCKETS; i++) + { + printf(" bucket %d: %d\n", i, Counts[i]); + } + } +} g_Test; + +#endif + + + + + + +int cFastRandom::m_SeedCounter = 0; + + + + + +cFastRandom::cFastRandom(void) : + m_Seed(m_SeedCounter++) +{ +} + + + + + +int cFastRandom::NextInt(int a_Range) +{ + ASSERT(a_Range <= 1000000); // The random is not sufficiently linearly distributed with bigger ranges + ASSERT(a_Range > 0); + + // Make the m_Counter operations as minimal as possible, to emulate atomicity + int Counter = m_Counter++; + + // Use a_Range, m_Counter and m_Seed as inputs to the pseudorandom function: + int n = a_Range + m_Counter * 57 + m_Seed * 57 * 57; + n = (n << 13) ^ n; + n = ((n * (n * n * 15731 + 789221) + 1376312589) & 0x7fffffff); + return ((n / 11) % a_Range); +} + + + + + +int cFastRandom::NextInt(int a_Range, int a_Salt) +{ + ASSERT(a_Range <= 1000000); // The random is not sufficiently linearly distributed with bigger ranges + ASSERT(a_Range > 0); + + // Make the m_Counter operations as minimal as possible, to emulate atomicity + int Counter = m_Counter++; + + // Use a_Range, a_Salt, m_Counter and m_Seed as inputs to the pseudorandom function: + int n = a_Range + m_Counter * 57 + m_Seed * 57 * 57 + a_Salt * 57 * 57 * 57; + n = (n << 13) ^ n; + n = ((n * (n * n * 15731 + 789221) + 1376312589) & 0x7fffffff); + return ((n / 11) % a_Range); +} + + + + + +float cFastRandom::NextFloat(float a_Range) +{ + // Make the m_Counter operations as minimal as possible, to emulate atomicity + int Counter = m_Counter++; + + // Use a_Range, a_Salt, m_Counter and m_Seed as inputs to the pseudorandom function: + int n = (int)a_Range + m_Counter * 57 + m_Seed * 57 * 57; + n = (n << 13) ^ n; + n = ((n * (n * n * 15731 + 789221) + 1376312589) & 0x7fffffff); + + // Convert the integer into float with the specified range: + return (((float)n / (float)0x7fffffff) * a_Range); +} + + + + + +float cFastRandom::NextFloat(float a_Range, int a_Salt) +{ + // Make the m_Counter operations as minimal as possible, to emulate atomicity + int Counter = m_Counter++; + + // Use a_Range, a_Salt, m_Counter and m_Seed as inputs to the pseudorandom function: + int n = (int)a_Range + m_Counter * 57 + m_Seed * 57 * 57 + a_Salt * 57 * 57 * 57; + n = (n << 13) ^ n; + n = ((n * (n * n * 15731 + 789221) + 1376312589) & 0x7fffffff); + + // Convert the integer into float with the specified range: + return (((float)n / (float)0x7fffffff) * a_Range); +} + + + + diff --git a/source/FastRandom.h b/source/FastRandom.h new file mode 100644 index 000000000..011c0c8da --- /dev/null +++ b/source/FastRandom.h @@ -0,0 +1,57 @@ + +// FastRandom.h + +// Declares the cFastRandom class representing a fast random number generator + +/* +The cFastRandom aims to provide a very fast, although not very cryptographically secure, random generator. +It is fast to instantiate, fast to query next, and partially multi-thread-safe. +It is multi-thread-safe in the sense that it can be accessed from multiple threads without crashing, but it may +yield duplicate numbers in that case. + +Internally, this works similar to cNoise's integral noise generation, with some predefined inputs: the seed is +taken from a global counter and the random is calculated using a counter that is incremented on each use (hence +the multi-thread duplication). Two alternatives exists for each function, one that takes a range parameter, +and another that takes an additional "salt" parameter; this salt is used as an additional input to the random, +in order to avoid multi-thread duplication. If two threads both use the class at the same time with different +salts, the values they get will be different. +*/ + + + + + +#pragma once + + + + + +class cFastRandom +{ +public: + cFastRandom(void); + + /// Returns a random int in the range [0 .. a_Range - 1]; a_Range must be less than 1M + int NextInt(int a_Range); + + /// Returns a random int in the range [0 .. a_Range - 1]; a_Range must be less than 1M; a_Salt is additional source of randomness + int NextInt(int a_Range, int a_Salt); + + /// Returns a random float in the range [0 .. a_Range]; a_Range must be less than 1M + float NextFloat(float a_Range); + + /// Returns a random float in the range [0 .. a_Range]; a_Range must be less than 1M; a_Salt is additional source of randomness + float NextFloat(float a_Range, int a_Salt); + +protected: + int m_Seed; + int m_Counter; + + /// Counter that is used to initialize the seed, incremented for each object created + static int m_SeedCounter; +} ; + + + + -- cgit v1.2.3