Anonymous user
Random Number Generator: Difference between revisions
no edit summary
| [unchecked revision] | [unchecked revision] |
(New page: = Random Number Generator = Random number generators can be implemented in lots of different ways. This article explains some of them. == Fibonacci random number == My OS uses a special...) |
No edit summary |
||
Line 1:
Random number generators (RNG) can be implemented in lots of different ways. This article explains some of them.▼
== Types of random number generators ==
▲Random number generators can be implemented in lots of different ways. This article explains some of them.
There are three types of random number generators:
*'''True random numbers:''' The generated values are really random, that means, that you cannot "predict" the next number, because they don't follow any recognizable patterns.
*'''pseudorandom numbers''': The generated values aren't random, because they are calculated.
*'''hybrid:''' The random number generator uses both methods to calculate the random number. E.g. it uses a true random number as s initial value (often refered to as "seed") for an algorithm, that generates pseudorandom numbers. This method is the most commonly used method in OSes, since it is fast and generates very useful results. Indeed [[Linux]] does it this way to provide <font color="blue" face="courier new">/dev/random</font>.
==
True random number generators use physical devices to generate random numbers, whose unpredictability can be traced to the laws of quantum mechanics.
Another commonly used "resource" is the behaviour of the user. Here the system generates values out of mouse movements, keyboard inputs or other human actions.
Finally a very simple way to obtain a seed is getting the time value of the system's [[Real Time Clock]].
== Pseudorandom number generators ==
My OS uses a special "remake" of the Fibonacci sequence to generate random numbers. This is done by having 4 "seeds", which start off as really weird values (e.g. 45, 80, 22, 32).▼
=== Linear congruential generator ===
The LCG is one of the oldest, but also one of the most simple algorithm to generate streams of pseudorandom numbers. Its based on this recurrence formula
X<sub>n+1</sub> = (aX<sub>n</sub> + c) mod m
where the modulus m is the number of random value the LCG produces.
The quality of this algorithm highly relies on chosing the right values for a, c and m. One good assignment is
m = 2<sup>32</sup>, a = 1103515245, c = 12345
as it's used in the glib.
So to generate a random number, choose a seed, which is X<sub>0</sub>. Then you can calculate the next random number in the stream, i.e. X<sub>1</sub>, by calculating:
X<sub>1</sub> = (aX<sub>0</sub> + c) mod m
To get the next random number X<sub>2</sub> take X<sub>1</sub> and calculate:
X<sub>2</sub> = (aX<sub>1</sub> + c) mod m
and so on.
Notice that this algorithm just generates m random numbers. So after m calculations it generates your seed again. Therefore it is a good idea to change the seed frequently.
For more values of a,c and m, see http://en.wikipedia.org/wiki/Linear_congruential_generator#LCGs_in_common_use.
=== Fibonacci random number ===
▲[[User:Mariuszp|My]] OS uses a special "remake" of the Fibonacci sequence to generate random numbers. This is done by having 4 "seeds", which start off as really weird values (e.g. 45, 80, 22, 32).
I implemented a seed() function which adds a new seed to the end of the sequence, and erases the first one (the seeds are referred to as A, B, C and D). The rand() function just returns the sum of the seeds, and calls seed() with the result.
| |||