If you don’t need the random numbers to be cryptographically secure, you can use a Linear Congruential Generator.
An LCG is a formula of the form X_n+1 = X_n * a + c (mod m), it needs constant memory and constant time for every generated number.
If proper values for the LCG are chosen, it will have a full period length, meaning it will output every number between 0 and your chosen modulus.
An LCG has a full period if and only if:
- The modulus and the increment are relatively prime, i.e.
GCD(m, c) = 1
a - 1
is divisible by all prime factors ofm
- If
m
is divisible by 4,a - 1
must be divisible by 4.
Our modulus is 2 ^ 32
, meaning a
must be a number of form 4k + 1
where k is an arbitrary integer, and c
must not be divisible by 2.
While this is a C# question I’ve coded a small C++ program to test the speed of this solution, since I’m more comfortable in that language:
#include <iostream>
#include <stdlib.h>
class lcg {
private:
unsigned a, c, val;
public:
lcg(unsigned seed=0) : lcg(seed, rand() * 4 + 1, rand() * 2 + 1) {}
lcg(unsigned seed, unsigned a, unsigned c) {
val = seed;
this->a = a;
this->c = c;
std::cout << "Initiated LCG with seed " << seed << "; a = " << a << "; c = " << c << std::endl;
}
unsigned next() {
this->val = a * this->val + c;
return this->val;
}
};
int main() {
srand(time(NULL));
unsigned seed = rand();
int dummy = 0;
lcg gen(seed);
time_t t = time(NULL);
for (uint64_t i = 0; i < 0x100000000ULL; i++) {
if (gen.next() < 1000) dummy++; // Avoid optimizing this out with -O2
}
std::cout << "Finished cycling through. Took " << (time(NULL) - t) << " seconds." << std::endl;
if (dummy > 0) return 0;
return 1;
}
You may notice I am not using the modulus operation anywhere in the lcg class, that’s because we use 32 bit integer overflow for our modulus operation.
This produces all values in the range [0, 4294967295]
inclusive.
I also had to add a dummy variable for the compiler not to optimize everything out.
With no optimization this solution finishes in about 15 seconds, while with -O2, a moderate optimization it finishes under 5 seconds.
If “true” randomness is not an issue, this is a very fast solution.