How to choose a fair random number in a range, or, who gets the last beer:

Alice and Bob both want the last beer, and they most certainly will not share. They each prefer to gamble, by flipping a coin. Since the outcome of the coinflip is unpredictable and fair (equal probability of each possible outcome), and since there are two people and two sides of the coin, they can easily agree on a mapping of coinflip results to selection of the person who gets the beer.

Now imagine they don’t have a coin, but they have a 6-sided die. It’s still easy to assign a die outcome to a fair selection of person-who-gets-beer, because there are two people, and an even number of sides on the die. Six divides evenly by two.

Things would be a bit more tricky, if Alice, Bob, Carol, and David were all contending for that last beer, because 6 doesn’t divide evenly by 4…

The trickiest case of all occurs when we have a very large many-sided die (20 sides in the image below) to select from a group (3 letters, or peoples’ names in the image below), and the size of the outcome group doesn’t divide evenly into the size of the die.

How many fair groups are there? How many times does 3 go into 20? The answer is 6. Divide 20 by 3, discard the remainder.

What is the largest fair number on the die? It’s the number of fair groups, multiplied by the size of each group. 6 * 3 = 18. So the way to select a fair random outcome is to roll the die, and if it produces one of the unfair outcomes, roll again until you get one of the fair outcomes. Finally, let’s make use of this in a computer:

In the computer, there’s a difference between “random” and “crypto random.” Just plain “random” is a low-cost math function, whose output looks “random” to a human, but with some careful analysis on some known section of output, the next bytes and even previous bytes can be predicted or calculated. Just plain “random” is good for toy video games and entertainment, but not good for games that have material consequence, such as gambling or hacking into national security systems (for “fun”). Crypto random has the characteristic of each individual byte being unrelated to each other (cannot be used to calculate earlier or later bytes), and each value having equal probability. In other words, getting a crypto random byte is just like rolling a 256-sided die, numbered from 0 to 255.

Realistically, most CPU’s can’t work on data smaller than 32 bits wide, so if you perform a calculation on a single byte, the CPU is actually working on 4 bytes and discarding 3 bytes. For simplicity and by way of example, let’s assume we’re working with unsigned 32 bit integers, UInt32. When we generate 4 random bytes (a random UInt32), this is analogous to a 232 sided die, with each side numbered from 0 to 4,294,967,295. To illustrate, we’ll assume you want to randomly select one of 17 people or things, numbered 0-16.

Clearly, you can calculate your Selection #, by getting the remainder (modulus) after dividing the random Die # by 17, as long as the Die # is less than or equal to 4,294,967,294. If the Die # happens to be the unfair value 4,294,967,295, then you’ve got to roll the die again.

Naturally, we don’t want to hard-code the numbers 17 or 4,294,967,294 into our program. We want to create a function that can return a random number in an arbitrarily sized, user-specified range. So inside the RandomRange function, we need to calculate the maximum fair die value, based on the size of the die, and the size of the requested range. The C# code below should translate easily into most other languages.

// Returns a randomly selected UInt32 in the range min to max, inclusive
UInt32 RandomRange(UInt32 min, UInt32 max) {
	return min + RandomRange(max - min);
}

// Returns a randomly selected UInt32 in the range 0 to max, inclusive
UInt32 RandomRange(UInt32 max) {
	// If the user requests a random value from 0 to 0, give them a 0.
	if (max == 0) {
		return 0;
	}

	UInt32 die = GetRandomUInt32();

	// If they requested a random UInt32 with literally no restriction, not
	// only do we already have a valid return value, it's also *important* 
	// that we return now, before trying to add one to max, which would be an
	// overflow.
	if (max == UInt32.MaxValue) {
		return die;
	}

	// Suppose max is 17, then the user wants a number from 0 to 17 inclusive,
	// which means the size of the range they specified is 18.
	UInt32 rangeSize = max + 1;

	UInt32 maxFair;
	if (UInt32.MaxValue % rangeSize == max) {
		// there are no unfair groups
		maxFair = UInt32.MaxValue;
	}
	else {
		// divide by rangeSize and multiply by rangeSize...
		// because these are ints, the division truncates, so after
		// multiplication, this has the effect of rounding down to the
		// bottom of the group.
		// Subtract one to get the maximum of the previous group, which
		// is the max fair value.
		maxFair = UInt32.MaxValue / rangeSize * rangeSize - 1;
	}

	while (die > maxFair) {
		die = GetRandomUInt32();
	}
	return die % rangeSize;
}

UInt32 GetRandomUInt32() {
	using (var rng = new RNGCryptoServiceProvider()) {
		var randomBytes = new byte[sizeof(UInt32)];
		rng.GetBytes(randomBytes);
		UInt32 retVal = BitConverter.ToUInt32(randomBytes,0);
		Array.Clear(randomBytes,0,randomBytes.Length); // crypto obsession
		return retVal;
	}
}

Comments are closed.