CODEWITHSUNDEEP
language-agnosticrandom
Phantom73
Phantom73

Reputation: 207

Pseudo-random number generator

What is the best way to create the best pseudo-random number generator? (any language works)

Upvotes: 14

Views: 11001

Answers (12)

Tim
Tim

Reputation: 86

In production code it is definitely safer to leverage an established library, but understanding how pseudorandom number generators work and writing your own can be fun and worthwhile from an educational standpoint.

There are many different techniques, but one straight forward approach is based on the logistic map. I.e.

x = r * x * (1 - x)

With the right value for r, values of x demonstrate chaotic and unpredictable behavior. There are pitfalls to be aware of which you can read about in the references below.

References

  1. https://tim.cogan.dev/random-num/
  2. https://scholar.google.com/scholar?hl=en&as_sdt=0%2C44&q=Logistic+map%3A+A+possible+random-number+generator&btnG=

Upvotes: 0

sosei
sosei

Reputation: 11

https://github.com/fsssosei/Pure_PRNG Python libraries for PRNG algorithms that pass statistical tests

Upvotes: 0

Thomas
Thomas

Reputation: 181745

It all depends on the application. The generator that creates the "most random" numbers might not be the fastest or most memory-efficient one, for example.

The Mersenne Twister algorithm is a popular, fairly fast pseudo-random number generator that produces quite good results. It has a humongously large period, but also a relatively humongous state (2.5 kB). However it is not deemed good enough for cryptographic applications.

Update: Since this answer was written, the PCG family of algorithms was published that seems to outperform existing non-cryptographic algorithms on most fronts (speed, memory, randomness and period), making it an excellent all-round choice for anything but cryptography.

If you're doing crypto though, my answer remains: don't roll your own.

Upvotes: 13

Bob
Bob

Reputation: 99694

My favorites are Hardware random number generators

Upvotes: -4

David Thornley
David Thornley

Reputation: 57036

If you're going to work in C++, Boost has a collection of PRNGs that I'd trust a lot more than whatever comes in standard libraries. The documentation might be helpful in picking one out. As always, how good a PRNG is depends on what you're using it for.

Upvotes: 0

Jason B
Jason B

Reputation: 11

See this link for the TestU01 suite of tests, which includes several batteries of tests.

http://www.iro.umontreal.ca/~simardr/testu01/tu01.html

In the paper, the author demonstrates the test result on a variety of existing RNGs, but not .NET System.Random (as far as I can tell). Though he does test VB6's generator.

Very few pass all the tests...

Upvotes: 1

John D. Cook
John D. Cook

Reputation: 30089

See Pitfalls in Random Number Generation

Upvotes: 2

Wedge
Wedge

Reputation: 19805

PRNG algorithms are complicated, as is acquiring the right sources of entropy to make them work well. This is not something you want to do yourself. Every modern language has a PRNG library that will almost certainly be suitable for your use.

xkcd random number

Upvotes: 4

cdonner
cdonner

Reputation: 37668

The German magazine C't tested a number of software and hardware generators in the 2/2009 issue and ran the results through various statistical tests.

I scanned the results here.

I would not bother writing my own. The article mentions that even Donald Knuth failed with his "Super-random number generator", which was not so random after all. Get one that passed all tests (had a result > 0 in all columns). They also tested a setup with a VIA EPIA M10000 mobo, which has a hardware RNG. I like this option for a commercial or semi-commercial setup that requires a robust random number server with high throughput.

Unless, of course, you are just playing around, in which case this may be good enough.

Upvotes: 7

gnovice
gnovice

Reputation: 125854

Yikes, that can get VEEEEEERY complicated! There seem to be a number of metrics for how to measure the "randomness" of a random number generator, so it's difficult to meaure which are "best". I would start with Numerical Recipes in C (or whatever langauge you can find one for) for a few examples. I coded up my first simple one from the examples given there.

EDIT: It's also important to start by determining how complex you need your random number generator to be. I remember a rude awakening I had in C years ago when I discovered that the default random number generator had a period somewhere around 32,767, meaning that it tended to repeat itself periodically after generating that many numbers! If you need a few dice rolls, that's fine. But not when you need to generate millions of "random" values for a simulation.

Upvotes: 3

EvilTeach
EvilTeach

Reputation: 28837

Steal the one out of knuth seminumeric. It is high quality and simple to implement. It uses a pair of arrays, addition, and a couple of ifs. Cheap, effective, and a nice long period 2^55 if i recall correctly.

Upvotes: 0

coobird
coobird

Reputation: 160954

Best way to create one is to not to.

Pseudo-random number generators are a very complex subject, so it's better off to use the implementations produced by the people that have a good understanding of the subject.

Upvotes: 25

Related Questions