A machine that cannot flip a coin
A computer follows instructions exactly. Give it the same input and it produces the same output, every time. That is the whole point of a computer, and it is also a problem: how can a machine built to be predictable produce a random number?
Mostly, it does not. random() in nearly every language gives you numbers that only look random. They are produced by a fixed formula, and they are called pseudo-random.
A formula and a starting point
A pseudo-random generator has two parts:
- a rule that turns one number into the next, and
- a seed: the number it starts from.
Apply the rule to the seed to get the first number. Apply it to that to get the second. And so on. A good rule scrambles its input so thoroughly that the output shows no visible pattern.
Here is a deliberately tiny one, small enough to check by hand: multiply by 5, add 3, keep the remainder after dividing by 16.
Run 1, seed 7
Run 2, seed 7
Run 3, seed 2
Start. Each run starts from its seed and repeats one rule: multiply by 5, add 3, keep the remainder after dividing by 16.
Run 1 and run 2 start from the same seed, so they are identical: the same numbers, in the same order. They have to be. Each number is computed from the one before, and the first is computed from the seed.
Example
Checking it yourself
Seed 7. (5 × 7 + 3) = 38. 38 mod 16 = 6.
Next: (5 × 6 + 3) = 33. 33 mod 16 = 1.
Next: (5 × 1 + 3) = 8. 8 mod 16 = 8.
Anyone who knows the rule and the seed can write out the entire sequence in advance.
This toy can only produce 16 different numbers, so it repeats after 16 steps. Real generators use the same idea with enormous numbers. The one in Python repeats only after a number of steps with more than 6,000 digits.
So why do my programs get different numbers each time?
Because by default the seed is different each time. If you do not give one, the language picks something that varies, such as the current time down to a tiny fraction of a second, or a value from the operating system.
Set the seed yourself and the "randomness" disappears:
import random
random.seed(42)
print(random.randint(1, 100), random.randint(1, 100)) # 82 15
random.seed(42)
print(random.randint(1, 100), random.randint(1, 100)) # 82 15, againBeing repeatable is a feature
- Tests. A test that uses random data and fails once in fifty runs is misery. Seed it, and the failure happens every time and can be fixed.
- Simulations and experiments. A result that cannot be reproduced is not much of a result. Publish the seed with it.
- Games. A whole generated world can be recreated from one number. Share the seed and a friend gets the same world.
- Debugging. Log the seed when something goes wrong, and you can replay exactly what happened.
Every animation on this site that involves chance uses a fixed seed for the same reason: so that it plays out identically each time you press replay.
And it is a security hole
If the sequence is fixed by the seed, then anyone who learns or guesses the seed knows every "random" number you will ever produce. Worse, for many common generators, observing a few hundred outputs is enough to work out the internal state and predict all the rest.
That is fatal for anything that must be unguessable:
- passwords and password reset links,
- session ids and login tokens,
- encryption keys,
- shuffling cards in a game played for money.
| Ordinary generator | Secure generator | |
|---|---|---|
| Speed | Very fast | Slower |
| Repeatable with a seed | Yes | No, by design |
| Predictable from past outputs | Often | No |
| Use for | Simulations, games, tests, sampling | Tokens, keys, passwords, anything secret |
Key takeaways
- Most random numbers in programs come from a formula applied over and over, starting from a seed.
- The same seed always produces the same sequence.
- Programs seem random because the seed is taken from something that varies, such as the clock.
- Fixing the seed makes tests, simulations and bugs repeatable.
- Ordinary generators are predictable. Use a cryptographically secure one for anything secret.