Random (adj): a: lacking a definite plan, purpose, or pattern. b: made, done, or chosen at random c: relating to, having, or being elements or events with definite probability of occurrence. d: being or relating to a set or to an element of a set each of whose elements has equal probability of occurrence. [Oxford English Dictionary]
Before commencing deep discussion of the art of “true randomality”, it must first be made clear that true randomness is theoretically impossible by the defining principals of our universe. The definition above clearly defines the paradox that surrounds the concept of randomality when subject to probability. In essence we will claim that “truly random” is the state in which for a given set A, for any i, element in A, i if chosen at random, has a probability of [1/|A|] (where |x| denotes cardinality of the set) of occurrence. This is how we judge the “randomness” of a Random Number Generator (RNG(s)), by its ability to exploit probability; given a set A, a perfect RNG will not repeat an element before the set is exhausted; described as the period of a generator, its point of repetition.
I.i Various Uses of Random Number Generators:
Random numbers have a multitude of applications. Of particular interest to this study and intended future studies by the author is Cryptography. Many cryptographic protocols make use of RNGs, particularly, public key cryptography (RSA) and some implementations of symmetric ciphers (DES, Serpent). Besides cryptographic function however, RNGs are used in Simulations, for the realistic recreation of “natural” occurrences; in this case, computer games are qualified as simulations, in which RNGs are heavily used in conjunction with probability weights (Gaussian). They’re also used for integrity testing on various computer applications during development, even hardware tests, such as GPU to memory pipelines on AGP based graphic cards. Among those mentioned are many other uses and purposes for the development and “perfection” of making truly random choices.
I.ii Brief Algorithm Introduction:
Random number generating algorithms come in multiple flavors; these can be separated into two main groups, linear number generators (LNG(s)) and non-linear number generators (NLNG(s)). Each group contains multiple types of RNGs and each of these, have their purpose and uses. It is important to know that although not all generators are made equal, good generators have purposes for which other good generators are not suited to perform.
II Linear Congruential Generators:
LNGs ultimately generate a sequence of integers between 0 and a given modulus, for the equation Ij+1 = aIj + c (mod m). In this equation, m is used as the modulus, a is a multiplier, and c is an increment. The sequence will repeats within a period of m, where m is usually prime.
The advantage of the LNG is immediately noticed by the equation above; its fast, requiring one multiplication, one addition, and one modulus. This immediately lends itself to explaining its wide uses. This type of generator is used in a multitude of applications for which the nature of the random sequence doesn’t matter, only that it be a different sequence from execution to execution; Monte Carlo simulations for example. The speed and simplicity of the algorithm has also led to the amount of flavors developed for different applications. For instance, the equation above is the same equation that the ANSI C/C++ committee has dubbed for use with these languages, given appropriate values for a, c, and m. Besides the linear equation, there are also:
Xn = (aXn-12 + bXn-1 + c) mod m
Xn = (aXn-13 + bXn-12 + cXn-1 + d) mod m
It is possible to force an LCG to be probabilistically correct, by creating uniform deviations. The problem with focusing on the deviation of an LCG is that a well deviated LCG will have an extended period, but its complexity increases, due to the deviation, sometimes beyond the useful range of LCGs. It is also possible to use deviations normalized in a given interval, such as Gaussian deviations, where the period is lengthened such that every integer in the given field is selected.