Introduction to Algorithms
Determinism is the property that identical inputs always produce identical outputs in a computer program—this is expected and usually desirable.
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 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?
Start with seed 42: The generator begins from the starting value 42 and follows its deterministic process.
Repeat with seed 42: Using the same starting value again produces the same sequence as the first run.
Start 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.
Assuming that running the same deterministic program twice should produce different results.
Determinism means identical inputs produce identical outputs.
Fix:
Treat repeatability as a normal and useful property of most computer programs.Thinking that pseudorandom numbers are truly random.
Pseudorandom numbers come from a deterministic algorithm, so the same seed produces the same sequence.
Fix:
Remember that pseudorandomness describes the random-looking appearance, not an unpredictable physical source.Using a fixed seed when every run should provide variety.
The same seed selects the same sequence.
Fix:
Use a seed that changes between runs when the goal is to make behavior appear different each time.Using pseudorandom numbers for security.
The source distinguishes pseudorandom numbers from truly random numbers needed for cryptography and security.
Fix:
Use 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
- Determinism means that identical inputs produce identical outputs.
- Predictability is useful for understanding, testing, and debugging programs.
- Pseudorandom numbers are generated deterministically but are designed to appear random.
- A seed starts a pseudorandom sequence; the same seed reproduces the same sequence.
- Games and simulations can use pseudorandom numbers, while cryptography and security need truly random numbers from physical entropy sources.
Key Takeaways
- 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.