Step 7 of 7

Random numbers and shuffling

Games, simulations and tests all need random numbers. C's standard library has a simple generator in <stdlib.h>:

• rand() returns a number from 0 to RAND_MAX (at least 32767; on this site and on Linux it's 2147483647).
• srand(seed) sets the seed, the starting point of the sequence.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(void) {
    srand((unsigned) time(NULL));        // seed once, from the clock
    int counts[7] = {0};
    for (int i = 0; i < 6000; i++) {
        int roll = rand() % 6 + 1;       // 1 to 6
        counts[roll]++;
    }
    int even = 1;
    for (int face = 1; face <= 6; face++) {
        if (counts[face] < 800 || counts[face] > 1200) even = 0;
    }
    printf("every face came up about 1000 times: %s\n", even ? "yes" : "no");
    return 0;
}

every face came up about 1000 times: yes

Pseudo-random

rand() isn't truly random. It's a formula that turns each number into the next, so the whole sequence is decided by the seed. That has consequences:

• Without srand, every run starts from seed 1 and produces the same numbers. That's handy for debugging, useless for a game.
• srand(time(NULL)) seeds from the current time in seconds, so each run differs. Call it once, at the start of main. Calling it before every rand() restarts the sequence, and within the same second you'd get the same number over and over.
• Different C libraries use different formulas. After srand(1), rand() % 100 is 0 on this site but 83 with GCC's library on Linux. Never write a test that expects particular random values.
• rand() % n gives 0 to n - 1. When RAND_MAX + 1 isn't a multiple of n, the smaller results come up very slightly more often. That's fine for a game, not for statistics.
• rand() is not for passwords, tokens or anything security-related: its output is predictable. Operating systems provide secure sources for that.

Shuffling fairly

To shuffle an array, the correct algorithm is the Fisher-Yates shuffle. Walk from the last element down to the second; for each position i, pick a random position j from 0 to i (inclusive) and swap the two:

for i from n - 1 down to 1:
    j = random number from 0 to i
    swap a[i] and a[j]

Every ordering comes out exactly equally likely. The tempting shortcut, swapping each element with a random position anywhere in the array, is biased: for 3 elements it makes 3 × 3 × 3 = 27 equally likely choices, which can't be split evenly among the 6 possible orders, so some orders come up more often than others.

Your turn: write roll(sides), returning a random number from 1 to sides, and shuffle(a, n), a Fisher-Yates shuffle of the n elements of a. The tests seed the generator themselves and check that every order of a 3-element array is equally likely, so the biased shortcut won't pass.

Previous: 2D arrays