Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

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. –  rightfold 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. –  rightfold Sep 20 '11 at 21:52
1  
9  
function rand() { return 4; /* determined by die roll - guaranteed to be random */ } –  Neil Sep 21 '11 at 7:54
show 4 more comments

5 Answers

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
2  
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
3  
@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
show 3 more comments

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
add comment

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
    
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
add comment

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
add comment

IMHO best standard way for human-usage use fractions (ms) of actual time ..humans are slow things ..and time is to fast for us :)

and.. it will always be pseudo!

edit:

ok, I get the neg. votes ..that doesnt explain how most methods work ..it should have been an suggestion for an easy, non-consuming method.

share|improve this answer
    
I have neither up- nor down-voted your answer, but I can name a reason why it is a really bad choice for a default RNG. It means random numbers generated in close temporal proximity will be identical or similar (imagine using "fractions of a second to 1-in-1000" for controlling the shuffling of a poker deck, you'll end up with a deck that will be shuffled in one of roughly thousand ways, instead of 1-in-52!). –  Vatine Sep 21 '11 at 8:56
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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