Chapter 4.7 - Pseudo Random Numbers
Time Estimate: 45 minutes
4.7.1. Introduction and Goals
As we saw in the Coin Flip App, Thunkable contains blocks that will generate random numbers and we can use those random numbers to simulate real-world events. But how does Thunkable create those numbers? How does a computer do randomness?
This Khan Academy video by Brit Cruise provides a nice conceptual overview of pseudorandomness and how it differs from true randomness. The type of pseudorandom number generator (PRNG) described in the video is different from the type described in the lessons below. But the general principles are very much the same.
Learning Objectives: I will learn to
use modular arithmetic to produce a remainder, which can be used to create pseudorandom numbers
recognize the difference between random and pseduorandom numbers, and the implciations of this difference on real world applications
Language Objectives: I will be able to
examine a series of numbers and discuss whether or not they look random
use target vocabulary, such as random number generator, modular arithmetic, and mod operator while considering how a computer models randomness, with the support of concept definitions and vocabulary notes from this lesson
4.7.2. Learning Activities
text-version | slides | YouTube video Part I | YouTube video Part II | YouTube video Part III | Slot Machine Video | Exercises
Computer Randomness
It is difficult for a computer to create a truly random event. Therefore, computers use a form of randomness known as pseudo randomness -- that is, they simulate randomness.
A pseudo random event looks random but is completely predictable -- we say it is deterministic because its output can be known by someone who knows how the event was programmed. What looks random to the user is actually the result of a completely predictable mathematical algorithm.
How does a PRNG Work
Activity: 4.7.2.1 YouTube (IZ56vqQZux4)
Q-1: Suppose our PRNG generates the following sequence of numbers and suppose you seeded it with the value 11:
... 14 11 5 24 2 0 17 15 8 4 ...
What would be the next number after 11 generated by the PRNG?
Q-2: Suppose your PRNG uses the following formula:
Xi+1 = Xi * 2 + 1
And suppose that X1 is 12. What value will X2 have?
Q-3: Suppose your PRNG uses the following formula:
Xi+1 = Xi * 2 + 1
And suppose that X1 is 10. What are the next three numbers that the formula would generate? Type your answers into the text box, separating the numbers by a single comma.
Clock Arithmetic and the MOD operator
The MOD operator gives the remainder when one number is divided by another. For example, 3 MOD 2 is 1 because 3 can be divided by 2 once with a remainder of 1. In the AP CSP exam, the a MOD b operator is defined as the remainder of a divided by b for positive numbers a and b. Thunkable also has a "Remainder Of" block. In arithmetic expressions, the MOD operator has the same precedence as the * and / operators which means that MOD, *, and / are evaluated before + and - unless there are parentheses.
We use modulo 12 arithmetic every day when we read clocks with 12 hours.
Q-4: Evaluate the following expression: (8 + 14) mod 13.
Q-5: Evaluate the following expression: (8 + 34) mod 13.
Q-6: Evaluate the following expression.
33 mod 5
Q-9: Suppose your PRNG uses the following formula:
Xi+1 = (Xi * 2 + 1) mod 13
What would the next number be if the current number is 10?
Q-10: Suppose your PRNG uses the following formula:
Xi+1 = (Xi * 2 + 1) mod 13
What would the next five numbers be if the current number is 10? Separate the numbers in your sequence by commas.
If you want to practice your modular arithmetic before moving on, here are some nice exercises, with links to the answers.
4.7.3. Summary
In this lesson, you learned how to:
Learning Objective AAP-2.C: Evaluate expressions that use arithmetic operators.
Learning Objective AAP-2.M.a: For algorithms: a. Create algorithms.
Learning Objective AAP-2.M.b: For algorithms: b. Combine and modify existing algorithms.
Learning Objective AAP-3.E.a: For generating random values: a. Write expressions to generate possible values.
Learning Objective AAP-3.E.b: For generating random values: b. Evaluate expressions to determine the possible results.
Learning Objective AAP-3.F.a: For simulations: a. Explain how computers can be used to represent real-world phenomena or outcomes.
Learning Objective AAP-3.F.b: For simulations: b. Compare simulations with real-world contexts.
4.7.4. Still Curious?
Learn about how a Russian crew was able to figure out how not to lose at slot machines in this Planet Money podcast.
Read more about linear congruential generators on Wikipedia.
PRNGs are also useful when securing the Internet, which is covered later in the course. For now, you can watch this video about CloudFlare and how lava lamps are helping to keep the Internet secure.
4.7.5. Self-Check
Here is a table of the technical terms introduced in this lesson. Hover over the terms to review the definitions.
deterministic
PRNG
modular arithmetic
mod operator
4.7.6. Reflection: For Your Portfolio
Answer the following portfolio reflection questions as directed by your instructor. Questions are also available in this Google Doc where you may use File > Make a Copy to make your own editable copy.
Last updated