Introduction to Algorithms
If the seed changes, the sequence changes, even though the underlying algorithm remains deterministic.
Predictable Programs
Many people initially expect a computer to behave unpredictably: run the same program twice and perhaps receive different results. Most computer programs work differently. When they receive identical inputs, they produce identical outputs. This property is called determinism.
Adding 2 and 3 produces 5 each time, and sorting the same list produces the same order. This predictability is usually desirable because it makes a program's behavior understandable and dependable.
Why Unpredictability Matters
Determinism is often exactly what developers want. Predictable behavior helps people understand a program and makes it possible to reproduce what happened. However, some applications need behavior that appears unpredictable. A game that always behaved identically would become repetitive. A simulation of weather or disease spread would not explore different possible scenarios if it always produced one identical result. Security systems also need unpredictability because predictable behavior can be exploited by an attacker.
The challenge is not that deterministic programs are defective. The challenge is to create useful unpredictable-looking behavior while keeping the advantages of deterministic computation.
| Source of numbers | How it behaves | Typical use described in the source |
|---|---|---|
| Truly random numbers | Come from physical entropy sources | Cryptography and security |
| Pseudorandom numbers | Generated by a deterministic algorithm but designed to appear random | Games and simulations |
The important distinction is between the physical source of true randomness and the deterministic algorithm used for pseudorandomness.
The Pseudorandom Pipeline
A pseudorandom number generator uses a deterministic process to produce numbers that appear random. You provide a seed, which is the generator's starting value. The generator applies a deterministic mathematical formula to that seed and produces a pseudorandom number. That number then becomes the input to the formula again, producing the next pseudorandom number. Repeating this process creates a sequence.
Comparing Two Seeds
A program generates a pseudorandom sequence first with seed 42 and then with seed 100. What should you expect?
- 1Start with seed 42
The generator begins from the starting value 42 and follows its deterministic process.
- 2Repeat with seed 42
Using the same starting value again produces the same sequence as the first run.
- 3Start with seed 100
Changing the starting value selects a different sequence of pseudorandom numbers.
The same seed reproduces the same sequence, while a different seed produces a different sequence.
Seeds and Reproducibility
A seed is the starting value for a pseudorandom number generator. It determines which sequence of pseudorandom numbers the generator will produce.
If two runs use the same seed, they produce the same pseudorandom sequence. This makes results reproducible: a developer can repeat the same behavior during testing or debugging instead of trying to rediscover an earlier sequence by chance. If the seed changes, the sequence changes, even though the underlying algorithm remains deterministic.
Choosing the Right Randomness
Use pseudorandom numbers when an application needs behavior that appears random, such as a game or simulation, and when reproducibility is useful for testing or debugging. Do not treat pseudorandom numbers as sufficient for cryptography or security. Those applications need truly random numbers from physical entropy sources.
Common mistake Assuming that running the same deterministic program twice should produce different results.
What it looks likeA learner expects a program given the same inputs to change its output on the second run.
Why it failsDeterminism means identical inputs produce identical outputs.
Do this insteadTreat repeatability as a normal and useful property of most computer programs.
Common mistake Thinking that pseudorandom numbers are truly random.
What it looks likeA learner assumes that a pseudorandom sequence cannot be reproduced.
Why it failsPseudorandom numbers come from a deterministic algorithm, so the same seed produces the same sequence.
Do this insteadRemember that pseudorandomness describes the random-looking appearance, not an unpredictable physical source.
Common mistake Using a fixed seed when every run should provide variety.
What it looks likeA game uses the same seed on every run and repeatedly creates the same sequence.
Why it failsThe same seed selects the same sequence.
Do this insteadUse a seed that changes between runs when the goal is to make behavior appear different each time.
Common mistake Using pseudorandom numbers for security.
What it looks likeA security system relies on a reproducible pseudorandom sequence.
Why it failsThe source distinguishes pseudorandom numbers from truly random numbers needed for cryptography and security.
Do this insteadUse truly random numbers from a physical entropy source for cryptography and security.
Check Your Understanding
A simulation produces an unexpected result. The developer wants to run the same scenario again to investigate the problem. Should the developer use a fixed seed or a changing seed? Explain why.
Hints
- Ask whether the developer needs variety or repeatability.
- Recall what happens when the same seed is used again.
Classify each situation as one that generally benefits from determinism, pseudorandomness, or truly random numbers: reproducing a bug, making a game less repetitive, and supporting cryptography or security. Give one reason for each choice.
Hints
- Debugging benefits from repeatable behavior.
- Games and simulations can use pseudorandom behavior.
- Security requires the stronger source described in the article.
Key Takeaways
- 1Determinism means that identical inputs produce identical outputs.
- 2Predictability is useful for understanding, testing, and debugging programs.
- 3Pseudorandom numbers are generated deterministically but are designed to appear random.
- 4A seed starts a pseudorandom sequence; the same seed reproduces the same sequence.
- 5Games and simulations can use pseudorandom numbers, while cryptography and security need truly random numbers from physical entropy sources.
At a glance
- Deterministic programs produce the same output from the same input.
- Pseudorandom generators use deterministic algorithms to create random-looking sequences.
- The seed determines which pseudorandom sequence is produced.
- Fixed seeds support reproducibility, while changing seeds provide variety.
- Pseudorandomness is suitable for many games and simulations but not for cryptography or security.