# How do random number generators work?

I am a Programmer out of Oregon, I currently work as a web developer for a local company, and am starting college this winter for Computer Science.

I was just pondering about php `rand()` function, and thinking about how I could remake it, and I came up completely stupified.

How the heck do random number generators work?

-

## migrated from stackoverflow.comSep 21 '11 at 7:26

This question came from our site for professional and enthusiast programmers.

Pseudo random number generators use a seed, a table of predefined constants and mathematical formulas. Real random number generators usually use atmospheric noise. You can easily get random numbers from reading /dev/random. – Elyse Sep 20 '11 at 21:50
Is atmospheric noise guaranteed to be random? – Korvin Szanto Sep 20 '11 at 21:51
@Korven Szanro yes, atmospheric noise is about the most random thing you can get, but special hardware is needed. The Linux kernel uses noise from the CPU AFAIK, which is also extremely random. – Elyse Sep 20 '11 at 21:52
`function rand() { return 4; /* determined by die roll - guaranteed to be random */ }` – Neil Sep 21 '11 at 7:54

Random Number Generators(RNGs) are really generating pseudorandom numbers, since it's impossible to actually generate a TRULY random number. The only really truly random things are acts of God, like lightning.

This wikipedia article might be able to help you out in the explanation: http://en.wikipedia.org/wiki/Random_number_generators

From what I understand, there are basically two parts of an RNG: the seed, and then the random number chosen from that seed. When you seed the RNG, you are giving it an equivalent to a starting point. That starting point then has a bunch of numbers that are "inside" of it that the program chooses from. In PHP, you can use srand() to "shuffle" the seeds, so you almost always get a different answer. You can then use rand(min, max) to go into the seed and choose a number between the min and the max, inclusive.

Think of each 'seed' as an ice chest, and then the random numbers as ice cubes. Let's say you have 1000 ice chests and each chest has 1000 ice cubes inside. At the county fair, they'll choose an ice chest to start using for drinks, and they can only use one ice cube. However, they only need ice cubes bigger than 1 cubic inch. So they'll choose a chest at random between those 1000 chests, and then they'll choose an ice cube inside that chest at random. If it works for the size they want, they use it. If it's not, they put it back in the chest with the others. If they want to make it a little more fun they change chests beforehand for total obliviousness, if you will!

As for how PHP actually physically chooses the seed and the random number, I don't have enough knowledge for that(which is probably what you were wondering the most about!). I wouldn't try and redo the rand() function; for most web based applications that you'll make, rand() should suffice for any random number you'll need.

Also check out linear congruential generators, this might be more of what you're looking for if you want the dirty details: http://en.wikipedia.org/wiki/Linear_congruential_generator

Hope this helps!

-
How would acts of `god` be random in the least bit? On top of that, lightning isn't random either, it follows a path determined by various conditions. Also, the interpreter generating the number is essentially irrelevant. – Korvin Szanto Sep 20 '11 at 21:59
I'm using acts of God in the legal sense: en.wikipedia.org/wiki/Act_of_God They are considered random since they are beyond apparent human control. – Mr. Starburst Sep 20 '11 at 22:01
So essentially, there is nothing that is random. But that would require every seemingly random occurance to be influenced, which doesn't work when you get to the very beginning of time.... Looks like I'm going to take some philosophy classes =D – Korvin Szanto Sep 20 '11 at 22:13
@Korvin, as far as we know, quantum phenomena like radioactive decay, or the emission of a photon by an excited atom are genuinely random. However, mathematicians and philosophers do argue what it means to be genuinely random. And while ordinary folks think a coin toss is pretty random, agile stage magicians (news.stanford.edu/pr/2004/diaconis-69.html) can regularly get 10 heads on 10 flips. – Charles E. Grant Sep 21 '11 at 7:45
@Charles - A coin toss isn't even a binary heads/tails, it's actually heads/tails/edge, so a really good stage magician could get it to come down neither heads nor tails. *8') – Mark Booth Sep 21 '11 at 12:57

They're usually not truly random, but are called pseudo-random because they generate a number sequence that appears random. This is done with some interesting mathematical formulas. One of the most common is the Linear Congruential Generator.

Pseudo-random numbers do have one useful property that true random numbers don't: if you use the same seed when you start you will get back an identical sequence. This can be very handy for testing.

-
If I'm understanding your second statement correctly: `random(5332)` will always be equal to `random(5332)` ? – Korvin Szanto Sep 20 '11 at 21:58
@Korvin, no I mean if you call `srand(5332)` then the next number returned by `rand` will always be the same. – Mark Ransom Sep 20 '11 at 22:00
"appears random" -> have same statistical properties as truly random numbers. – user1249 Sep 21 '11 at 7:47
+1 for the LGC Wikipedia link, this has an excellent animation of why simplt PRNGs have serious limitations when doing multidimansional Monte-carlo simulations. – Mark Booth Sep 21 '11 at 13:02

There are many ways to attempt to emulate a "random" sequence of numbers. Your first stop should be to read about linear congruential generators, for sure. This is how most basic random number generators work, and I'd bet it's how PHP's rand() function works.

The more interesting next question to ponder is how does it seed itself? time? IP address? etc.

-
The seed is what is confusing me, I can't think of anything that can possibly seed the function without some sort of pattern, and even if not, then what is causing the random seed to be generated in the first place! – Korvin Szanto Sep 20 '11 at 21:53
I believe a timestamp is often used as an initial seed when none is actually provided from some other source. In old BASIC, `RANDOMIZE TIMER` was a common idiom, and "good enough" for most (non-cryptographic) purposes. According to man 3 srand, the GNU C library uses a fixed seed of 1 until the PRNG is reseeded. – Michael Kjörling Sep 21 '11 at 8:05