Pseudo-random number generator

Question

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

This is a significant field of study and there is no well agreed metric for best...what are you trying to achieve? — dmckee --- ex-moderator kitten, Feb 25 '09 at 03:12
Do you want something like true randomness or you want random-like series that you can repeat? — Robert Gould, Feb 25 '09 at 04:03
@Robert Gould: He has specified pseudo random. If he's looking for true randomness he is barking up the wrong tree indeed... — dmckee --- ex-moderator kitten, Feb 25 '09 at 04:05
From an answer that is going to be deleted: [Hardware random number generator](https://en.wikipedia.org/wiki/Hardware_random_number_generator) — Jayan, Mar 17 '16 at 09:19

score 26 · Accepted Answer · answered Feb 25 '09 at 03:12

26

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.

answered Feb 25 '09 at 03:12

coobird

159,216
35
211
226

12

I downvoted because "don't reinvent the wheel" is a terrible answer, made even worse because it is continually propagated by inept programmers. You should never be told not to do something. – Krythic Sep 28 '15 at 13:32
4

I agree with @Krythic's comment. You should never discourage a person, or a beginner saying that this is far too complex. This stops the learning process, and is wrong. -1 – Box Box Box Box Mar 16 '16 at 15:16
For some reason, this type of answer bothers me a lot, if a beginner is genuinely trying to implement this as an exercise, then don't discourage them from doing so. Similar with beginners asking "how to implement an HTML parser as an exercise" before people saying "use beautifulsoup". Agree with @Krythic – Feb 22 '21 at 20:06
1

@expressjs123 I'm quite literally reinventing the wheel right now with a color picker that I'm making. Are there existing color pickers I could use? Probably. But I want to make it myself. Reinventing the wheel is how you learn new things, and I'll never tell anyone not to do it. Here's a picture of my project: https://imgur.com/a/A6hnv8F – Krythic Feb 23 '21 at 06:16

Thomas · Answer 2 · 2019-01-25T10:14:34.690

12

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.

edited Jan 25 '19 at 10:14

answered Feb 25 '09 at 03:14

Thomas

174,939
50
355
478

MT also has the advantage of drawing n-tuples evenly over n*[0-1)-space for large n. Something that not every PRNG can do. This is a reason for it being very popular in Monte Carlo studies across many fields. – dmckee --- ex-moderator kitten Feb 25 '09 at 03:25
"it is not deemed good enough for cryptographic applications": no, MT is *absolutely forbidden* for crypto, because a sequence of 624 output numbers from MT lets you predict its entire future output! Capturing the output sequence of a proper crypto RNG gives NO information on its future output. – kquinn Feb 25 '09 at 04:16
3

"Capturing the output sequence of a proper crypto RNG gives NO information on its future output." Thats wrong, the information is there. The future output just needs to be infeasibly hard to compute. – starblue Feb 25 '09 at 09:47

score 7 · Answer 3 · edited May 23 '17 at 12:17

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.

Hardware RNGs are a no-go if you specifically need a PRNG, i. e. something that has reproducible output, which is a very important trait for use in simulations. — Joey, Mar 04 '09 at 15:43

score 5 · Answer 4 · edited Feb 08 '17 at 14:07

5

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

edited Feb 08 '17 at 14:07

Community

1
1

answered Feb 25 '09 at 04:29

Wedge

19,513
7
48
71

gnovice · Answer 5 · 2009-02-25T03:26:47.193

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.

Numerical Recipes is a dangerous field, as they don't allow you to use the code unless you purchase a license for every user. That's a trap we ran into with a university simulation framework which created a major hassle. And for the C RNG the period is usually around 2^32, it only emits just 15 bits — Joey, Mar 04 '09 at 15:46

score 2 · Answer 6 · answered Feb 25 '09 at 13:14

2

See Pitfalls in Random Number Generation

answered Feb 25 '09 at 13:14

John D. Cook

29,517
10
67
94

score 1 · Answer 7 · answered Oct 16 '09 at 16:24

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...

score 0 · Answer 8 · answered Oct 16 '09 at 16:31

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.

score 0 · Answer 9 · answered Feb 25 '09 at 03:15

0

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.

answered Feb 25 '09 at 03:15

EvilTeach

28,120
21
85
141

I vaguely remember something about a RNG from a famous book being pretty crappy, but widely used because it was in a famous book. I can't find anything about this anymore, though. It might well have been a different book. Be sure to check this before you use it for any critical purpose, though. – Thomas Feb 25 '09 at 03:21

score 0 · Answer 10 · answered Jul 10 '21 at 16:57

0

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

answered Jul 10 '21 at 16:57

sosei

21
2

You can't just straightaway add a link to some repository. That repository might get deprecated at some point in time, and people won't get the solution to the problem. Instead, explain how this solved the problem asked by the OP. – Abhishek Dutt Jul 10 '21 at 18:14
1

Okay. My advice is: don't create your own "PRNG" if you're not an expert in the field.Use an off-the-shelf library, such as PRNG in Numpy – sosei Jul 11 '21 at 13:17

score 0 · Answer 11 · answered Feb 26 '22 at 01:15

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

score -3 · Answer 12 · edited Mar 17 '16 at 09:18

-3

My favorites are Hardware random number generators

edited Mar 17 '16 at 09:18

Jayan

18,003
15
89
143

answered Feb 25 '09 at 03:13

Bob

97,670
29
122
130

Pseudo-random number generator

12 Answers12

Linked

Related