What do a dice roll, future weather conditions, and quantum
mechanics all have in common?
As far as we humans can tell, these 3 things are all completely
random, or at least based on
conditions we don't yet understand. Anything can be defined as
random so long as it is
"lacking a definite plan, purpose, or pattern." This becomes a
rather big problems for
computers, since by their deterministic nature they produce
predictable outcomes 100% of the
time; given the same input, a computer will give you the same
output, without deviation, every
time. So how do we get around this problem? Randomness can come in
quite handy for
certain applications, but by their very nature computers cannot be
random. The answer is
pseudorandomness. Although computers can never be truly random, it
turns out they're very
good at faking it.
Enter pseudorandom number generators. These are algorithms that generates numbers which appear to be random to us humans, but are actually deterministic and predictable. You feed the algorithm a starting number called a 'seed,' perform a series of math operations on that number, and voila, out comes a number that looks completely random. Common operations done on the numbers are exponentiation and bit-shifts. Because these algorithms are predictable and only pseudorandom, if you give it the same seed it will produce the same numbers. Every programming language and internet browser has a PRNG built in to conveniently provide random numbers to us when needed. However, not all PRNG algorithms are created equal. There comes a point in every algorithm that the numbers will start repeating themselves. The amount of numbers you generate before they start repeating is what is known as the 'period.' A small period is usually the sign of a bad algorithm. Another sign of a bad algorithm is if the numbers are not distributed equally. For example if could generate large numbers more often than it generates small numbers. Every algorithm must strike a balance of appearing random, but also being fast. Being very random but very slow is typically not ideal.
A good balance of speed and randomness is where the Mersenne Twister
shines. Developed in
1997 by Makoto Matsumoto and Takuji Nishimura, the MT is one of the
most widely used PRNGs
to date. Excel, Python, and MATLAB are a few examples among many
more that all use the
Mersenne Twister as the built in PRNG. The name comes from it's
period length, which
is 219937-1, a Mersenne prime, and then 'twisting'
(mostly performing bitwise operations) an array
to generate the pseudo-random numbers. When the Mersenne Twister was
published in 1997 it
corrected a lot of the problems that older PRNGs were suffering
from. Today, it still holds
up as being fast and reliably random for most common use-cases,
although some disadvantages
such as not being cryptographically secure have arisen (newer
versions of MT have been
published to correct these flaws). All in all, the Mersenne Twister
is a fantastic PRNG that
should be appreciated.