Have you played a video game lately? Purchased something on the web? Trained a Neural Network? Used a Genetic Algorithm for optimization? Run software from Microsoft? Applied textures to a photograph? Played the stock market? If the answer is "yes" to any of these questions, Random Number Generator (RNG) have affected your life[1].

Thank heavens I'm currently attenting a lecture on PRNGs! Here is a short summary of the first lecture (all proofs are surpressed ;-D):

Introduction to PRNGs: The output from a computer algorithm is deterministic, not random. What we require instead are algorithms that produce sequences of output that behave in important ways like sequences of realizations from random variables would behave. Such algorithmically created numerical sequences are termed random numbers, random variates, or random deviates to distinguish them from the (mathematically ideal) random variables they are intended to simulate. Just as random numbers are the fundamental building block of computer simulation studies, uniformly distributed random numbers are the building blocks for random numbers (and other random objects) with arbitrarily specified distributions. <> Physical methods of generating random numbers were known to the ancients; tossing coins and throwing dice are familiar examples. The advent of digital computers brought a need for lengthy streams of random numbers, and methods for generating them automatically were among the first general-purpose algorithms invented for the computing devices. Two fundamental types of uniform generators are in common use and are the basis for many variants: the linear congruential generators (LCGs) and the feedback shift-register (FSR) generators.[2]

In the first lecture of the RNG-course we dealt with LCGs - the 'simplest and unfortunately most widely employed PRNGs'[1]. The linear congruence method for generating pseudorandom numbers uses the linear recurrence relation (click here if you are not familiar with the notion of congruence): This PRNG is often denoted by and uniform pseudorandom numbers in [0,1) are obtained by the transformation u_n := x_n/m. Leamer proposed the generator LCG(10⁸+1, 23, 0, 47594118) which had a repetition period of 5882352. The problem: LCGs allow an easy (number-) theoretical analysis based on the lattice structure formed by δ-dimensional vectors u_n = (u_n,...,u_n+δ-1) of all generated uniforms u_n.[3]

Example: Lattice structure of the infamous RANDU [LCG(2³¹,65539,0,1)] This problem was pointed out by Marsaglia (1968) who wrote: "[A]ll multiplicative (b=0) congruential random number generators have a defect--a defect that makes them unsuitable for many Monte Carlo problems and that cannot be removed by adjusting the starting value, multiplier, or modulus. The problem lies in the "Crystalline" nature of multiplicative generators--if n-tuples (u₁,u₂,...,u_n), (u₂,u₃,...,u_n+1),... of uniform variates produced by the generator are viewed as points in the unit cube of n dimensions, then all the points will be found to lie in a relatively small number of parallel hyperplanes. Furthermore, there are many systems of parallel hyperplanes which contain all of the points; the points are about as randomly spaced in the unit n-cube as the atoms in a perfect crystal at absolute zero."

You may wish to read How to crack a Linear Congruential Generator. Makes somehow fun to play around. Here is my quick and dirty Mathematica implementation: lcgfun (nb, 5 KB) (I've seen that almost 100 readers downloaded the notebook on the logistic equation so far... how cool is that?)

[1] Not knowing your RNG could be costly: Random Generators - Why are they important? [2] Elements of Statistical Computing Volume 2 Draft Notes [3] A collection of classical pseudorandom number generators with linear structures