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:

long long RandSeed = 0xdeadbeaf ; // initialize a random seed
unsigned long Random(long max)
{
    long long x ;
    double i ;
    unsigned long final ;
    x = 0xffffffff;
    x += 1 ;

    RandSeed *= ((long long)134775813);
    RandSeed += 1 ;
    RandSeed = RandSeed % x ;
    i = ((double)RandSeed) / (double)0xffffffff ;
    final = (long) (max * i) ;

    return (unsigned long)final;
}

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 /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:

procedure TDeck.Shuffle;
var
   ctr: Byte;
   tmp: Byte;
   random_number: Byte;
begin
   { Fill the deck with unique cards }
   for ctr := 1 to 52 do
      Card[ctr] := ctr;
   { Generate a new seed based on the system clock }
   randomize;
   { Randomly rearrange each card }
   for ctr := 1 to 52 do begin
      random_number := random(51)+1;
      tmp := card[random_number];
      card[random_number] := card[ctr];
      card[ctr] := tmp;
   end;
   CurrentCard := 1;
   JustShuffled := True;
end;

Let’s look at just the core shuffling algorithm (note the array’s index start with 1 in Pascal):

for (i is 1 to N)
  j = random integer that 1 <= j <= N
  Swap a[i] with a[j]

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 Fisher-Yates algorithm:

for (i is 1 to N)
  j = random integer that i <= j <= N // (not 1 <= j <= N here!)
  Swap a[i] with a[j]

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?

Reference

Wiki: Random number generation.

How We Learned to Cheat at Online Poker: A Study in Software Security.

Algorithms by Robert Sedgewick