Random Number and Card Shuffling Algorithm

Original Post: https://coderscat.com/random-number-and-card-shuffling-algorithm

Random numbers represent uncertainty, which is widely used in computers, 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 will be some difficulties when we want to generate 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, both of which have their own advantages and disadvantages.

Pseudo-Random number generator (PRNG)

As its name suggests, a pseudo-random number is not truely 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 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 generated by a real random number generator and a PHP pseudo-random number generator under Windows. The right one 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(), where get_random_bytes is used in the kernel. The difference between /dev/random and /dev/urandom is that /dev/random is stronger and blocking because more entropy is collected.

Usage of random number

Programs involving random numbers need to be especially careful.

For example, 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 to write a function to generate a random number in the range of 0~10?

Maybe you would simply come out with a solution: rand()%10 (I also used this before), but is this really random?

If you put all the numbers from 0 to 32767 with the operation of %10, you can find out that some numbers appear more often, so the probability of some numbers appearing at the end is correspondingly larger.

Card shuffling algorithm

Writing a proper shuffle program 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 simply the core shuffling algorithm (Note 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. 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 large.

The correct shuffle algorithm is, which is called Fisher-Yates algorithm:

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

Another issue that could be hard to found out, a 32-bit number 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 for a 32-bit seed, you can even use brute-force to crack.

Some random-number related exercises for you

1. Generate a random number in 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 sit down around a table and they wanted to know the average annual salary, but everyone was 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
How To Randomize (Shuffle) A JavaScript Array?