What are some fast ways to generate random numbers?

Question

Many programming languages come with a function to give random numbers. I wonder how they implement that. Also, assuming the language doesn't have a random function, is there a way to generate them quickly? Another related question is if the language (and included libraries) had this random function included, could someone write a faster one just using the "primitives" of the language? I don't remember ever hearing about this in college but for probability simulation I have been using random numbers a lot and now am wondering how they do it and get it so there is no bias and not the same repeating pattern of numbers. Do they just reference some internal clocks of the computer? If so, wouldn't that then bias the numbers some?

I should clarify and say what if I only needed random numbers from 0 to 255 (8 bit) to simulate most card hands, die rolls... Is there a way I can write my own or has anyone on this site tinkered around with writing their own successfully?

It would be fun on a very fast computer to have some algorithm that gives me random numbers as quickly as possible (even storing them in memory or streaming them). For example, if I wanted 1 trillion random numbers to run a simulation without spending a lot of CPU cycles generating them so there is more available CPU speed to actually run the simulation.

Answer 1

Virtually all computer "random" number generators generate "pseudo-random numbers", meaning that in many senses the numbers generated do not follow any easily predictable pattern but the sequence is deterministic. They usually take a "seed" as input to start generating the sequence at an arbitrary point. For more non-deterministic behavior you can use the system clock value as the seed, which is basically random. Some famous "good" pseudo-random number generators include the Mersenne twister. A very simple psuedo random number generator you can implement yourself is to assume that all random numbers are between 1 and some large prime $p$, and then choose random $a,b$ that are large between 1 and $p$ and relatively prime, and then given one number $x_n$ in your random sequence you generate the next "random" number as $x_{n+1} = ax_n + b \mod p$. However there are much better pseudo-random number generators out there, without getting into detail about what it means for a generator to be "good."

Answer 2

Chaos from Dynamical Systems can model randomness in a very close way. Consider the humble Logistic Recurrence... $$X_{n+1}=a \cdot X_n \cdot (1-X_n)$$ It looks innocent, but using the methods of dynamical systems and bifurcation theory, we find that after a series of period doublings, instances were the number of solutions doubles, the system becomes chaotic, or unpredictable.

You can see the number of solutions doubling as a increases, but the solutions double quicker than a increases eventually reaching infinity in a finite amount parameter variation, chaos follows, then ebbs, then comes back again!

You can clearly see regions of complete randomness followed up by regions of calmness and predictability, the key is to only use the chaotic parts in your number generator. You'd do this by picking seed values $v$ and making sure to convert that seed to values of $a$ such that the logistic equation is chaotic. I should add that the seed value $v$ could be based off the time that your computer has, or any other consistent but varied parameter.