A Super Tiny Random Number Generator

When I posted the last blog post about shuffling on the GameProgrammer.com mailing list, someone responded back with a super tiny random number generator that is actually pretty damn good. It is this:

x+=(x*x) | 5;

The high bit of X is the source of your random numbers, so if you want to generate an 8 bit random number, you have to call it 8 times. Apparently it passes a lot of tests for randomness really well and is a pretty high quality PRNG. Check this out for more info: http://www.woodmann.com/forum/showthread.php?3100-super-tiny-PRNG

You can start x at whatever you want, but it might take a few iterations to “warm up” especially if you start with a small seed (ie you may want to throw away the first 5-10 random bits it generates as they may not be that random). I adapted it into an example program below, along with some example output. I use time() to set the initial value of x.

#include
#include
#include
#include

// A super tiny prng
// http://www.woodmann.com/forum/showthread.php?3100-super-tiny-PRNG
//
unsigned int seed = 0;
unsigned int GenerateRandomBit()
{
seed += (seed * seed) | 5;
return seed & 0x80000000;
}

template
void GenerateRandom(T& value)
{
memset(&value, 0, sizeof(T));
const unsigned int numBits = sizeof(T) * 8;
unsigned int* dataPointer = (unsigned int *)&value;
for (unsigned int index = 0; index < numBits; ++index) { if(GenerateRandomBit()) { unsigned int pointerIndex = index / 32; unsigned int mask = 1 << index % 32; dataPointer[pointerIndex] |= mask; } } } int main(int argc, char **argv) { seed = (unsigned int)time(NULL); printf("seed = %u\r\n", seed); printf("9 random uints...\r\n"); for (unsigned int index = 0; index < 9; ++index) { unsigned int random; GenerateRandom(random); printf("%2u: %10u (%x)\r\n", index, random, random); } printf("3 random floats...\r\n"); for (unsigned int index = 0; index < 3; ++index) { float f; GenerateRandom(f); printf("%2u: %f (%x)\r\n", index, f, *((unsigned int*)&f)); } printf("8 random characters...\r\n"); char text[8]; GenerateRandom(text); for (unsigned int index = 0; index < 8; ++index) { printf("%2u: %c\r\n", index, text[index]); } system("pause"); return 0; } [/cpp] tinyprng1

tinyprng2

tinyprng3

tinyprng4

Comments

comments

About Demofox

I'm a game and engine programmer at Blizzard Entertainment and have been making games since 1990 (starting out with QBasic and TI-85 games) My shipped titles include: * Heroes of the Storm * StarCraft II: Heart of the Swarm & Legacy of the void * Insanely Twisted Shadow Planet (PC) * Gotham City Impostors (PC, 360, PS3) * Line Rider (PC, Wii, DS) I also like hiking, making music, learning cool new stuff and attempting the impossible.