Simple and fast random number generator

This topic is 2007 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

I did an implementation of a linear congruential generator. It's at least twice as fast rand() on my machine, and the period is 2^63 instead of 2^32, which is the glibc implementation.

It's also reversible, meaning you have both int next() and int prev().

Tyche-i also seems reversible, how is the quality compared to an lcg?

#ifndef RLCG_HPP
#define RLCG_HPP

#include <cstdint>

namespace rlcg {

namespace details {

template<class T>
constexpr bool isPowerOfTwo(T x){
return (x & (x - 1)) == 0;
}

//constexpr implementation of euclids algorithm
constexpr uint64_t extendedEuclidY(uint64_t a, uint64_t b);
constexpr uint64_t extendedEuclidX(uint64_t a, uint64_t b){
return (b==0) ? 1 : extendedEuclidY(b, a - b * (a / b));
}
constexpr uint64_t extendedEuclidY(uint64_t a, uint64_t b){
return (b==0) ? 0 : extendedEuclidX(b, a - b * (a / b)) - (a / b) * extendedEuclidY(b, a - b * (a / b));
}

//modulus M, multiplicand A, increment C, least significant bits to discard D
template<uint64_t M = 1ul<<63ul, uint64_t A = 6364136223846793005, uint64_t C = 1442695040888963407, uint64_t D = 32>
class ReversibleLCG {
static_assert(isPowerOfTwo(M), "M is not a power of two as it should be");
uint64_t x;
public:
ReversibleLCG(unsigned int seed) : x(seed){}
unsigned int next() {
x = (A * x + C) & (M - 1);
return x >> D;
}
unsigned int prev() {
const uint64_t ainverse = extendedEuclidX(A, M); //don't worry, this is computed at compile time
x = ainverse * (x - C) & (M - 1);
return x >> D;
}
unsigned int max() const {
return (M - 1) >> D;
}
};

} // end namespace details

using ReversibleLCG = details::ReversibleLCG<>;

} // end namespace rlcg

#endif // RLCG_HPP


Share on other sites

What's wrong with well-known algorithms such as (complementary) Multiply-With-Carry, or Xor-Shift? Both roughly 20 years old, and both incidentially from the same author. Simple arithmetic operations, and few of them, and you can lag them any way you want if a period of 264-1 isn't enough for you (though in my opinion, that's plenty, maybe not if you're doing particle systems that simulate global weather, but for a game it is anyway).

Unless one needs a cryptographic RNG, I see no real reason to use anything more complicated or to even try inventing something better. The difference, if there is any, will probably not be observable.

Share on other sites

I have often used small RNGs for things like hashing functions.

say, for example:

seed=seed*4093+1;

val=(seed>>12)&4096;

or:

seed=seed*65521+1;

val=(seed>>16)&65535;

or, ...

while the period isn't necessarily great, the level of "randomness" is typically pretty usable, and when used as the basis for something like a hashing function, the deterministic behavior is pretty useful. it is also pretty fast as well.

say, for hashing a string:

s=str; h=0;

while(*s)h=(h*4093)+(*s++);

elsewhere I have an RNG that mostly just works by multiplying a large (IIRC 1024 bit) value by a very large number and adding a constant (with the high-order bits used as output), and is continuously seeded via an "entropy miner" which basically feeds in delta-values from the RDTSC instruction (which tend to be fairly noisy).

this is mostly used as a TRNG. I don't know if "cryptographically secure" or anything, but it seems to work reasonably ok for generating UUID-style numbers, as well as for things like reseeding smaller/faster PRNGs.

Share on other sites

But just why do people care so much about periods? There is no difference between a 264 period and a 264000 period. Assuming your computer runs at 2GHz and consumes one random number every cycle (rather unlikely!), it can run for 292 years on a 264 period.

How many people do you know who live 292 years? How many people do you know who can remember what numbers they saw 292 years ago?

Share on other sites

But just why do people care so much about periods? There is no difference between a 264 period and a 264000 period. Assuming your computer runs at 2GHz and consumes one random number every cycle (rather unlikely!), it can run for 292 years on a 264 period.

How many people do you know who live 292 years? How many people do you know who can remember what numbers they saw 292 years ago?

for most typical uses, a period of 2^32 or 2^64 is fine...

for a lot of PRNG algorithms, the average period is considerably smaller than the size of the seed-value though (for example, a 64-bit seed might only give a 32-bit average period, or a 32-bit PRNG giving a 16 bit period, ...).

an overly short period may also interfere with some use-cases.

...

the solution then is to use a bigger value and get a larger period, granted, past a certain point it may not matter much, and be offset by the added costs of doing arithmetic with very large numbers or similar.

so, a lot depends on what is "good enough" for the given use-case.

the main other situations are things like cryptography, where you want to be fairly certain that your numbers are actually pretty random (such that people trying to crack things will be less likely to be able to guess them...), and things like UUID values, where you generally want to have at least some confidence that the randomly generated ID number isn't being used anywhere else (meaning the RNG state needs to be considerably larger than the UUID being generated, and also seeded with reasonably unique values).

for example, a 128-bit UUID would be a bit of a fail if a given implementation could only produce in-total 2^32 unique UUIDs.

and, if this happened for cryptography, then the key could likely be broken in under 1 second.

so, a lot has also has to do with the use-case...

Share on other sites

I just wanted to point out that using a state as small as 16 bytes is more a liability than a feature. In my limited experience writing PRNGs and hash functions, a large state is one of the easiest ways to avoid some common pitfalls.

Have you guys tried something like the dieharder test suite to evaluate the quality of the pseudo-random numbers generated by your code?

I have done extensive testing with dieharder, in fact I was trying to find the minimum number of rounds needed. Turns out three rounds passes the dieharder tests with no problems. I did not invent the internal design myself, this is Bruce Schneier's cipher, I just simplified it slightly for use as a PRNG, rewrote it with vector instructions, and did some checking to ensure I didn't break anything. Inventing a PRNG from scratch is just asking for trouble, imho, but deriving it from an existing, proven construction is a hobby of mine.

But just why do people care so much about periods? There is no difference between a 264 period and a 264000 period. Assuming your computer runs at 2GHz and consumes one random number every cycle (rather unlikely!), it can run for 292 years on a 264 period.

I don't really understand that either, to be honest. This is also why I dislike the MT. It just looks over-engineered with its 2^19937 period, I mean, who cares? If anything, having an exact, predictable period is more of a failure than a feature since true random number generators do not exhibit regular periodicity. But it doesn't matter anyway because nobody will ever reach said period. 16 bytes of internal state is cutting it a bit close if your PRNG is particularly bad, but 32 bytes is more than enough.

And then you see people using MT for CUDA.. good grief, what a waste of memory.

Share on other sites

This beats what you have

What's wrong with well-known algorithms such as (complementary) Multiply-With-Carry, or Xor-Shift? Both roughly 20 years old, and both incidentially from the same author. Simple arithmetic operations, and few of them, and you can lag them any way you want if a period of 264-1 isn't enough for you (though in my opinion, that's plenty, maybe not if you're doing particle systems that simulate global weather, but for a game it is anyway).

Unless one needs a cryptographic RNG, I see no real reason to use anything more complicated or to even try inventing something better. The difference, if there is any, will probably not be observable.

QFT!

XorShift beats what I see here, in speed (i.e. fewer operations), cycle length (2128-1), and passes the diehard tests.

http://en.wikipedia.org/wiki/Xorshift

A reversible LCG is certainly an interesting toy, but programs don't tend to run in reverse.

1. 1
2. 2
Rutin
16
3. 3
4. 4
5. 5

• 26
• 11
• 9
• 9
• 11
• Forum Statistics

• Total Topics
633703
• Total Posts
3013455
×