How does a random number generator work?

Question

How do random number generator works? (for example in C/C++ Java)

How can I write my own random number generator? (for example in C/C++ Java)

Answer 1

There is also this algorithm:

Oh, and more seriously:

Random number generators use mathematical formulas that transfer set of numbers to another one. If, for example, you take a constant number N and another number n_0, and then take the value of n mod N (the modulo operator), you will get a new number n_1, which looks as it if is unrelated to n_0. Now, repeat the same process with n_1 and you'll get another number. What you have here is a (VERY BAD) generator of seemingly random numbers.

Remember, the method I've described here is a toy method that should not be used for anything serious. It does, however, illustrate the general principle.

Also note:

If all scientific papers whose results are in doubt because of bad rands were to disappear from library shelves, there would be a gap on each shelf about as big as your fist.

(paraphrased from chapter 7 of Numerical recipes). This is a must-read text for anyone who uses random number generators for any serious work.

Answer 2

One of the things to keep in mind is that there are no 'true' random number generators. They just generate numbers that look random to us mere mortals.

One of the easiest examples of this (to implement, as well) is the Linear congruential generator. Sure, the numbers look unpredictable to you and me, but they're actually evenly spaced within a finite field.

Of course, some generators, like Blum Blum Shub aren't predictable for an outsider even if he applies serious mathematical skills and computing power to the task, but at the fundamental level, random number generators aren't random; they're regular and predictable.

Answer 3

How I made them in the old days was by getting some value from the system that changes really rapidly, for example the system millisecond timer.

The next thing you have to do is to apply some formula that will generate a new number from this "input" number and clip it to the range you need, eg 0..255:

random_number = integer(formula(timer-value)) MOD 255

That way, you have a new "random" number every time you call the function.

An example formula function could be:
formula(x) = ((x XOR constant) + constant2) MOD range
XOR used to be one of my favourites.

---

Update: I realize that this formula is a very bad one, it generates a pretty predictable set of numbers. Also, the system timer is too predictable as a source. So for most applications, this does not suffice. If you need better randomness, use more sources than just the system timer and better formulas to combine them.

Answer 4

I found this one for Java:

http://www.javamex.com/tutorials/random_numbers/java_util_random_algorithm.shtml

by googling how random functions work java

I'm sure the answer is language-specific, but you can try altering my Google query for the language of your choice.

Answer 5

There is a lot of information available about how they are working ... see Konamiman's answer and use google a bit.

Why would you like to write a new random generator? You probably should not try to do so ... until you need something very special. For example in a game you could use a shuffle bag which produces 'fair' random values - have a look at this interesting question on SO.
I post this here, because I really liked the idea and implementation when I read about it the first time :)

Answer 6

It's also common to seed these types of generators by using something like the fifth decimal of the current clock time which also appears random to us. Add together inputs from a few chaotic systems, e.g. weather data, stock market data, again, using modulus and you have good seed numbers.