Random numbers represent uncertainty, which is widely used in the computing world. Such as encryption keys, password generation, simulation, and games. Some classic randomized algorithms(such as Monte Carlo Algorithm) also rely on random number generation.
In this post, we will discuss how random numbers are generated, how to use random numbers to shuffle cards.
Random number generation
Actually, there are some difficulties with generating random numbers only through computers.
Computers are good at executing determinate tasks and run coded instructions according to the program.
There are two types of random numbers generated by computers: truly random numbers and pseudo-random numbers, and each have their own advantages and disadvantages.
Pseudo-Random number generator (PRNG)
As its name suggests, a pseudo-random number is not truly random in the strict mathematical sense and is generally generated by some mathematical formula (or a calculated table).
For example, a simple Linear congruential generator could be used to generate pseudo-random numbers.
Let’s have a look at Borland’s random number generator:
Please note that the
RandSeed will be updated in each generation.
PRNG’s result is random in a statistical sense. The behavior of pseudo-random numbers is predictable, which means if we know the current state of the PRNG, we could get the next random number.
Moreover, the pseudo-random numbers may have a fixed period. For example, the following two bitmaps are generated by a real random number generator and a PHP pseudo-random number generator under Windows. The right one which generated with a pseudo-random generator has a noticeable pattern.
Because of it’s above features, pseudo-random generation’s usage is limited, it’s mostly adapted in programs such as simulation.
True random number generator (RNG)
“True” random number generator (RNG), by introducing some really unpredictable physical noises to the computer, such as keyboard strokes and mouse movements. This is known as
entropy. True random numbers are hard to predict or simply unpredictable.
The implementation of each operating system is different. On Linux, the root of all randomness is something called the
kernel entropy pool.
For example, the MAC address could be used to initialize the entropy pool, other random source includes interruption time, addressing time of hard disk, etc.
The interfaces are
get_random_bytes(). The difference between
/dev/urandom is that
/dev/random is stronger and blocking because more entropy is collected. And
get_random_bytes is used in the Kernel code.
Usage of a Random Number
Programs involving random numbers need to be especially careful.
For instance, let’s write a simple program. We know that the random number generated by
rand() in C programming language has a range
0~32767. How do we write a function to generate a random number in the range of
Maybe you would simply come out with this solution:
rand()%10. I’ve also used this approach before, but is it really random?
If you put all the numbers from 0 to 32767 with the operation of
%10, you can see that some numbers appear more often, so the probability of these numbers appearing at the end is correspondingly larger.
Card shuffling algorithm
Writing a proper program to shuffle cards seems easy, but it’s not.
That’s a pretty tough thing to have happen if you’re implementing online poker. You might want to make sure that if you’re advertising that you’re doing a random shuffle that you go ahead and do so.
—Robert Sedgewick, Professor of Computer Science
ASF Software wrote a popular online poker game many years ago, in which the shuffle program is this Pascal code:
Let’s look at just the core shuffling algorithm (note the array’s index start with 1 in Pascal):
The shuffling algorithm here has a problem: the probability for the
52! permutations is different.
Let’s take three cards 1, 2, 3 as an example, here is the result after 3 iterations:
We can see that
132 appear more often, so the corresponding probability is also larger.
A simple and elegant shuffle algorithm is called Fisher-Yates algorithm:
Another issue in the above program is hard to discover. A 32-bit number used as a seed is problematic for pseudorandom generators because the behavior of a given pseudo-random generator is predictable.
The number of possible values for a seed of 32 is
2^32, which is much smaller than
52!(8.0658 * 10^67). So you can even use brute-force to crack a 32-bit seed.
Some Random Number Exercises
1. Generate a random number in a range
You are given a
rand() can generate random integers between
[1, 5], how to use this function to generate random integers between [1, 7]?
2. Lottery program
Write a lottery program that randomly selects 10w winning users from 30w users?
3. Average salary (Open question)
There are 10 people sitting around a table and they want to know the average annual salary, but they’re all reluctant to disclose their salary to others.
Is there a way for them to get the answer, without exposing anyone’s salary to others?
Wiki: Random number generation.
How We Learned to Cheat at Online Poker: A Study in Software Security.
Algorithms by Robert Sedgewick