How Does a Computer Roll a Die?

Do one step by hand first. 2083 × 2083 = 4,338,889. Written with eight digits, that is 04338889: a zero goes in front, so that there is always a middle. The middle four digits are 3388, so 3388 is the next number. Check it against the widget.

• a.Press Run until one comes back for the seed 2083. How many different numbers did you get before one came back?
• b.Try your own seeds: your birth year, your phone’s last four digits, 1234.
• c.Try 2000, 3792 and 0540. What goes wrong?

Each die roll is the remainder when the number is divided by 6, plus 1, so it is always 1 to 6. When the numbers loop, the rolls loop with them.

Look at the rule again: the next number is worked out only from the number before it. Nothing else goes in: not the time, not a tumble, not a guess. So whenever the same number turns up, everything after it turns up again too, in the same order. Once one number repeats, the whole chain repeats.

And a number must repeat, because there are only 10,000 four-digit numbers. After at most 10,000 steps the rule runs out of new ones. With the middle-square rule it happens far sooner.

A computer’s random numbers are like this today too: worked out by a rule from a starting number, the seed. They aren’t really random, so they are called pseudo-random (“pretend random”), as Grade 7 said. That has two sides:

• The same seed gives the same numbers. That is useful. Topics like Why do snakes and ladders games take so long? and How far does a wandering ant get? start with random.seed(1) or random.seed(3), so that your run gives exactly the numbers printed on the page. Testers fix the seed to repeat a bug.
• Anyone who knows the rule and the seed knows every number. For a game of Ludo that doesn’t matter. For a lottery it matters a lot.

Step 1: square, keep the middle

x * x // 100 divides by 100 and throws away the remainder, which drops the last two digits. % 10000 keeps the last four of what is left. Together they keep the middle four of the eight.

def middle_square(x):    return x * x // 100 % 10000 numbers = []x = 2083for i in range(12):    numbers.append(x)    x = middle_square(x)print(numbers)

[2083, 3388, 4785, 8962, 3174, 742, 5505, 3050, 3025, 1506, 2680, 1824]

Python leaves out zeros at the front, so 742 is the 0742 of the widget.

Step 2: find the loop

To catch the loop, keep every number in a list, seen, and stop as soon as the next one is already in it. seen.index(x) says where it was first.

def middle_square(x):    return x * x // 100 % 10000 seen = []x = 2083while x not in seen:    seen.append(x)    x = middle_square(x)first = seen.index(x)print('Different numbers:', len(seen))print(x, 'came back; it was number', first + 1)print('The loop:', seen[first:])

Different numbers: 294100 came back; it was number 26The loop: [4100, 8100, 6100, 2100]

The same as the widget. Change x = 2083 to your own seed.

Step 3: every seed there is

A computer can do this for all 10,000 seeds in less than a second. This program finds the seed that runs longest before a number comes back, and names each loop by its smallest number, counting how many seeds end up in it.

def middle_square(x):    return x * x // 100 % 10000 def run(seed):    seen = []    x = seed    while x not in seen:        seen.append(x)        x = middle_square(x)    return seen, seen.index(x) longest = 0loops = []counts = []for seed in range(10000):    seen, first = run(seed)    if len(seen) > longest:        longest = len(seen)        best = seed    loop = min(seen[first:])    if loop in loops:        counts[loops.index(loop)] += 1    else:        loops.append(loop)        counts.append(1)print('Longest:', best, 'gives', longest, 'different numbers')for i in range(len(loops)):    print('Loop through', loops[i], ':', counts[i], 'seeds')

Longest: 6239 gives 111 different numbersLoop through 0 : 1968 seedsLoop through 100 : 104 seedsLoop through 2100 : 6291 seedsLoop through 1600 : 1360 seedsLoop through 540 : 86 seedsLoop through 2500 : 130 seedsLoop through 7600 : 60 seedsLoop through 3792 : 1 seeds

(return seen, seen.index(x) gives back two things at once, and seen, first = run(seed) takes them apart.)

Step 4: a better formula, in blocks

Here is a different rule, of the kind computers used for decades after: multiply, add, keep the remainder. Take x, multiply it by 21, add 7, and keep the remainder after dividing by 100. The die is again the remainder after dividing by 6, plus 1.

The same seed gives the same ten rolls, every time. But look at the rolls themselves. From the seed 83 they are 3, 4, 5, 2, 1, 2, 3, 4, 3, 6. Do you see a pattern?

Step 5: fair counts, bad die

The same rule in Python, with two ways of turning x into a roll: the remainder, as in the blocks, and a second way that uses the first digit of x instead of the last: x * 6 // 100 is 0 for x from 0 to 16, 1 for 17 to 33, and so on up to 5. The program rolls each die 600 times, counts each face, and counts how often an odd roll is followed by another odd one.

def next_number(x):    return (21 * x + 7) % 100 def try_die(way):    x = 83    rolls = []    for i in range(600):        x = next_number(x)        if way == 'last digit':            rolls.append(x % 6 + 1)        else:            rolls.append(x * 6 // 100 + 1)    print(way, rolls[:12])    for face in range(1, 7):        print('  ', face, 'came up', rolls.count(face), 'times')    odd_odd = 0    for i in range(599):        if rolls[i] % 2 == 1 and rolls[i + 1] % 2 == 1:            odd_odd += 1    print('   odd then odd:', odd_odd, 'times') try_die('last digit')try_die('first digit')

last digit [3, 4, 5, 2, 1, 2, 3, 4, 3, 6, 3, 4]   1 came up 102 times   2 came up 102 times   3 came up 102 times   4 came up 102 times   5 came up 96 times   6 came up 96 times   odd then odd: 0 timesfirst digit [4, 4, 1, 6, 2, 6, 6, 3, 2, 4, 2, 2]   1 came up 102 times   2 came up 102 times   3 came up 96 times   4 came up 102 times   5 came up 102 times   6 came up 96 times   odd then odd: 150 times

Both dice look perfectly fair if you only count the faces: every face about 100 times in 600. But the first never rolls two odd numbers in a row, not once in 600 rolls. A real die would do it about a quarter of the time, and the second die does: 150 times in 599 pairs. The last digit of a formula like this is its weakest part; the first digits are much better mixed.

Even the better die has a limit: x can only be 0 to 99, so after 100 rolls the whole list starts again. (Change range(600) to range(200) and compare rolls[:100] with rolls[100:].) Real formulas of this kind use enormous numbers in place of 100, so that the loop is far too long ever to reach.

Step 6: a picture of the pattern

A picture shows a pattern faster than reading rolls. Make each number x and the one after it into a point, x across and the next number up, on a 100 by 100 square. pixels is this page’s own module for drawing squares (on a computer you would use a library such as Pillow); 255 is white and 0 black. The second picture uses Python’s own random numbers for comparison.

import randomfrom pixels import show_grid def next_number(x):    return (21 * x + 7) % 100 def blank():    rows = []    for r in range(100):        rows.append([255] * 100)    return rows rows = blank()x = 83for i in range(100):    after = next_number(x)    rows[99 - after][x] = 0    x = aftershow_grid(rows) random.seed(1)rows = blank()x = random.randrange(100)for i in range(100):    after = random.randrange(100)    rows[99 - after][x] = 0    x = aftershow_grid(rows)

Picture

The formula’s dots stand in tidy rows, like an orchard. Real chance looks messier: clumps and gaps. Every formula of the multiply-add-remainder kind lines its points up in rows like this; good ones use such huge numbers that the rows are too close together to matter. In the 1960s a widely used formula called RANDU, on IBM computers, put its points in only 15 flat layers when three numbers in a row were drawn as a point in three dimensions. The computer scientist Donald Knuth called it “truly horrible”.

• Every seed of the middle-square rule falls into a loop, and soon: of all 10,000 four-digit seeds, none gives more than 111 different numbers (6239 is the longest), and they all end in one of just 8 loops. Nearly 2,000 seeds end stuck at 0.
• The same seed always gives the same numbers. That is a computer’s “random”: a rule and a starting number.
• A die can pass the counting test and still be bad. The multiply-add-remainder die rolled every face about equally often and never once rolled two odd numbers in a row.

So a good random number rule needs three things: a very long loop, no pattern that a picture or a clever count can find, and, where money or secrets depend on it, a seed nobody can guess.

For games and simulations, a good formula is enough. For a lottery, a bank’s one-time code or an online card game, it isn’t: if someone can guess the seed, they know everything. So computers also collect real chance from the world, things no formula decides: the exact moments keys are pressed, the tiny wobbles in the timing of signals inside the chip, electrical noise. The operating system stirs these together into a seed nobody can guess.

Other rules. Try the multiply-add-remainder rule with other numbers in place of 21, 7 and 100. Change Step 2’s program to find each rule’s loop length. Can you find a rule whose loop is all 100 numbers? One that loops after just a few? (T. E. Hull and A. R. Dobell found the exact conditions in 1962: for 100, the add number must not divide exactly by 2 or by 5, and the multiply number minus 1 must divide exactly by 4 and by 5. 21 − 1 = 20 does, and 7 is fine.)

More digits. Keep the middle 6 digits of 12 instead of 4 of 8, and try some 6-digit seeds. Are the chains longer?

An open question. No program can make truly random numbers out of nothing, only spread out randomness it was given. Can a formula be so good that no program can ever tell its numbers from real chance? Cryptographers think some can, but nobody has been able to prove it; it is tied to some of the deepest unsolved problems in computer science.

★ A coin from the formula (blocks)

The program below makes five new values of x with the multiply-add-remainder rule. Finish it so that at the end it says heads when x is less than 50 and tails otherwise. Then press Test.

★★ Find the loop (Python, from Grade 8)

Write loop(seed) that gives back the numbers of the middle-square loop that the seed falls into, in the order they come, starting with the first one met. For 2083 it gives [4100, 8100, 6100, 2100].

def middle_square(x):    return x * x // 100 % 10000 def loop(seed):    return [] print(loop(2083))

★★★ Guess the next roll (Python, from Grade 8)

A game uses the better die from Step 5: x = (21 × x + 7) % 100, then the roll is x × 6 // 100 + 1. You don’t know the seed (a number from 0 to 99), but you have seen the first few rolls. Write predict(rolls) that gives back a sorted list of every roll that could come next.

def next_number(x):    return (21 * x + 7) % 100 def predict(rolls):    return [1, 2, 3, 4, 5, 6] print(predict([4, 4, 1]))

• Grade 7, Variables and Choices: the random block, and “How random is random?”.
• Grade 7, People are bad at being random: why passwords need chance, not you.
• Grade 8, Repeating with while: the loop that runs until a number comes back.
• Grade 9, Algorithms that use chance: what random numbers are good for, and fixing the seed.
• Can you beat a computer at rock-paper-scissors? A player that finds the pattern in yours.
• How can throwing rice find π? Good random numbers put to work, and what a biased throw does.
• Math, Going Further: Which Total Comes Up Most with Two Dice? and Is This Game Fair?: what chance does once you have a fair die.
• Math, Going Further: Can You Write a Message Only a Friend Can Read? Multiply, add, keep the remainder, to hide a message.