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 pseudorandom numbers, and each have their own advantages and disadvantages.
PseudoRandom number generator (PRNG)
As its name suggests, a pseudorandom 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 pseudorandom 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 pseudorandom numbers is predictable, which means if we know the current state of the PRNG, we could get the next random number.
Moreover, the pseudorandom numbers may have a fixed period. For example, the following two bitmaps are generated by a real random number generator and a PHP pseudorandom number generator under Windows. The right one which generated with a pseudorandom generator has a noticeable pattern.
Because of it’s above features, pseudorandom 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 /dev/random
, /dev/urandom
, get_random_bytes()
. The difference between /dev/random
and /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 0~10
?
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 231
, 213
, 132
appear more often, so the corresponding probability is also larger.
A simple and elegant shuffle algorithm is called FisherYates algorithm:

Another issue in the above program is hard to discover. A 32bit number used as a seed is problematic for pseudorandom generators because the behavior of a given pseudorandom 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 bruteforce to crack a 32bit 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?
Reference
Wiki: Random number generation.
How We Learned to Cheat at Online Poker: A Study in Software Security.