Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question

migrated from stackoverflow.com Sep 21 '11 at 7:26

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

2  
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. – Zoidberg 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. – Zoidberg Sep 20 '11 at 21:52
2  
10  
function rand() { return 4; /* determined by die roll - guaranteed to be random */ } – Neil Sep 21 '11 at 7:54
up vote 2 down vote accepted

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.


WARNING, POSSIBLE CHEESY ANALOGY AHEAD!

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!

share|improve this answer
3  
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
2  
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
1  
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
5  
@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
1  
@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

First of all, virtually all rand() functions do not provide true randomness, rather they provide so-called pseudo-random numbers.

So, how do pseudo-random number generators work? Basically in the same way that encryption works: You have a function (a hash) that takes some input, and produces some output in such a complex manner that it's impossible from the output to guess the input or vice versa. That is, every cypher can be used to create a rather good pseudo-random generator. However, while you could use any pseudo-random generator to do encryption in principle, most pseudo-random number generators are primarily developed for speed, not cryptographic security, so they won't give hackers any headaches.

For a pseudo-random generator, the hashing function is applied to some hidden internal state of the generator, and its output is used to a) modify that internal state, and b) to compute the output of the rand() function. The next invocation of rand() will use that changed internal state, and thus produce a different result. The better the hash function, the less easily the results are distinguishable from true random numbers.


As a matter of fact, computers nowadays have access to real random numbers: They stem from jitter in the timing of interrupts produced by external devices. Linux uses these values of small uncertainty to constantly stir an "entropy pool", which is just a few kilobytes of internal state. Cryptographic hashes based on this entropy pool are made available via the /dev/random and /dev/urandom devices. So, access to some really really good random numbers is as simple as opening one of these two devices and reading some bytes from them.

share|improve this answer

Random Numbers are numbers generated by the process whose output is unpredictable. i.e we can’t tell what is going to be next output. We can take some simple example outcome of the dice. What is going to be output when we throw a dice is unpredictable.

There are two types of Random Number 1. True random numbers 2. Pseudo random numbers.

How Random numbers are genrated

share|improve this answer
1  
Please use quote formatting to highlight which parts of the answer are yours and which are from the source you cite. If all your answer is is a copy/paste from an external source, it's not a good answer here. – Mat May 1 at 12:29
    
this doesn't seem to offer anything substantial over points made and explained in prior 6 answers – gnat May 1 at 13:17

Are you asking for Pseudorandom or Random? Others answered about pseudorandom, let me talk about Random.

There were (are?) actual hardware-based Random Number Generators in sale. They were based on a chip with a small radio measuring white noise of deep space radiation, or a small radioactive sample and measuring periods between its decay. The problem with them was the bandwidth - the amount of entropy they could generate wasn't very high so they were used for seeds of pseudorandom algorithms. They were used in bank systems, high-security and the likes.

OTOH, if you meet any embedded systems developer, they will laugh at these. For common purposes in programming a microcontroller, reading low 4 bits of any 16-bit Analog-Digital Converter woth a floating (unconnected) pin will produce a perfectly good random noise, at more than sufficient bandwidth (the shorter the polling period the more "noisy" the readout), and easier than writing actual RNG routine. And considering ADCs are commonly found implemented in silicon of microcontrollers, commonly implemented, and often implemented with 8 channels from which you need maybe 5 for your application, it's practically free.

And even if you don't have an ADC, couple of elements connected to a digital GPIO pin will produce a pretty good noise. In embedded, noise is ever-present (and constantly fought), and so obtaining some true randomness is very easy.

share|improve this answer

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.

share|improve this answer
    
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
2  
"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.

share|improve this answer
    
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
1  
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

protected by gnat May 1 at 13:16

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.