How do random number generators work?

Question

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

How do random number generators work?

Answer 1

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!

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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