Random Numbers

Switch on a Commodore 64 and type PRINT RND(1). It answers .185564016. Switch it off and on and ask again: .185564016. The machine gives the same first “random” number every time it starts, and the same one after that, because RND is arithmetic, not chance. It takes a stored number, the seed, does a fixed calculation on it, and keeps the result as the next seed. Same seed in, same sequence out.

Games need dice rolls, shuffled cards and enemies that do not always turn left, so programmers had to know where their numbers came from. On the C64 there are three answers: BASIC’s RND, the hardware timers it can read instead, and the SID sound chip’s noise generator. The ZX Spectrum took a more open approach and printed its generator’s formula in the manual.

How the C64’s RND works

The seed lives in five bytes of zero page, $8B–$8F (139–143), in BASIC’s floating-point format. At switch-on BASIC copies a fixed starting value there from ROM: the bytes 128, 79, 199, 82 and 88, which is about 0.8116. What RND then does depends only on the sign of its argument. The Programmer’s Reference Guide says the argument “is a dummy, except for its sign”.

The byte shuffle is what Mapping the Commodore 64 calls “scrambling the resulting bytes”: after the multiply and add, the routine swaps the first and last bytes of the number’s mantissa, and the two middle ones, before tidying the result back into the range 0 to 1. Neither the Programmer’s Reference Guide nor Mapping the Commodore 64 gives the length of the sequence before it repeats. Leemon only says that “so many numbers can be produced in this way before the sequence begins to repeat that it can be considered random”.

Run from a cold start, this program prints the same three numbers on any C64:

10 PRINT RND(1)
20 PRINT RND(1)
30 PRINT RND(1)

 .185564016
 .0468986348
 .827743801

RND(0) and the clock that never runs

The Programmer’s Reference Guide says that with an argument of zero RND “generates a number directly from a free-running hardware clock (the system ‘jiffy clock’)”. The ROM does something else. It reads the low and high bytes of the CIA’s timer A and the tenths and seconds registers of its time-of-day clock, packs them into a number, and makes that the new seed. So RND(0) does change what RND(1) gives next.

Mapping the Commodore 64 found two faults in it. The time-of-day clock “does not start running until you write to the tenth of second register”, and the operating system never does, so two of the four bytes “always have a value of 0”. And the timer’s high byte only runs from 0 to 66, “so that certain numbers are never chosen”. Leemon’s verdict was that RND(0) “doesn’t really work right on the 64”, which is why Commodore programmers seeded from the jiffy clock instead.

Seeding from the clock

TI is BASIC’s jiffy clock, a count that the system interrupt adds one to every sixtieth of a second from switch-on. The Programmer’s Reference Guide calls it a “1/60 second interval timer”, and it counts sixtieths on PAL machines too: in an emulated PAL C64, a loop waiting for TI to advance by 600 finished in 500 frames, ten seconds. A negative argument makes RND take its seed from that number, so RND(-TI) starts the sequence somewhere that depends on when it ran. Leemon calls it “the traditional Commodore method of selecting a random seed”, and suggests RND(-RND(0)) as an alternative.

A title screen makes a good source of timing, because nobody presses a key at exactly the same moment twice:

10 PRINT "PRESS ANY KEY TO START"
20 GET K$:IF K$="" THEN 20
30 X=RND(-TI)
40 PRINT INT(RND(1)*6)+1

The opposite is just as useful. RND(-1) always sets the same seed, so a program that starts with it gets the same numbers every run. That is the repeatability the Programmer’s Reference Guide recommends “in testing programs”:

10 X=RND(-1)
20 FOR I=1 TO 3:PRINT RND(1):NEXT

This prints .328780872, .978964086 and .895758909 every time.

Turning RND into dice

RND gives a fraction. Games want whole numbers in a range, so multiply by how many values there are, take the whole-number part with INT, and add the first value:

Forgetting the +1 on a die gives 0 to 5. The Programmer’s Reference Guide’s own example, X=INT(RND(1)*6)+INT(RND(1)*6)+2, rolls two dice separately and adds them, which is not the same as INT(RND(1)*11)+2: with two dice a total of 7 comes up six times as often as 2 or 12, as it does at a real table.

Fast enough?

RND is slow. On an emulated PAL C64 this program took 6.85 seconds for a thousand calls, against 2.8 seconds for the same loop without RND, so each call costs about 4 milliseconds:

10 T=TI:FOR I=1 TO 1000:X=RND(1):NEXT:A=TI-T
20 T=TI:FOR I=1 TO 1000:X=1:NEXT:B=TI-T
30 PRINT A/60;"SECONDS";B/60;"SECONDS"

A PAL frame lasts 20 milliseconds, so a BASIC game that wants several random numbers each frame spends a large part of the frame making them. One answer is to make them in advance, while the title screen is up, and step through a table during play:

100 DIM R(127)
110 FOR I=0 TO 127:R(I)=INT(RND(1)*40):NEXT
...
1000 F=(F+1)AND 127:X=R(F)

The table repeats every 128 uses, which is rarely noticeable in a game.

Useful patterns

Weighted choices. Fill a table with the outcomes in the proportions you want, then pick from it. Here half the drops are item 1, 30% item 2 and 20% item 3:

100 DIM L(99)
110 FOR I=0 TO 49:L(I)=1:NEXT
120 FOR I=50 TO 79:L(I)=2:NEXT
130 FOR I=80 TO 99:L(I)=3:NEXT
140 D=L(INT(RND(1)*100))
150 PRINT "ITEM";D

Shuffling. To deal cards, or to visit spawn points without repeats, shuffle a list once and read it in order. The Fisher–Yates shuffle walks down the list, swapping each position with a randomly chosen one at or below it:

100 DIM D(51)
110 FOR I=0 TO 51:D(I)=I:NEXT
120 FOR I=51 TO 1 STEP -1
130 J=INT(RND(1)*(I+1))
140 T=D(I):D(I)=D(J):D(J)=T
150 NEXT
160 FOR I=0 TO 51:PRINT D(I);:NEXT

Every number from 0 to 51 appears exactly once. The shuffle gives every order an equal chance only if each pick is equally likely, so it is only as good as the generator behind it.

The same level every time. A negative seed makes a level number into a landscape. Level 3 always draws the same skyline, whenever the player types it in. The level must be 1 or more, because RND(-0) is RND(0) and reads the timers:

10 INPUT "LEVEL";L
20 PRINT CHR$(147):X=RND(-L)
30 FOR C=0 TO 39
40 H=INT(RND(1)*20)+5
50 FOR Y=24-H TO 24:POKE 1024+Y*40+C,160:NEXT
60 NEXT
70 GOTO 70

A random walk. Keep the position on the screen, or the POKE will soon land outside screen memory and overwrite something else:

10 PRINT CHR$(147):X=20:Y=12
20 D=INT(RND(1)*4)
30 IF D=0 AND X>0 THEN X=X-1
40 IF D=1 AND X<39 THEN X=X+1
50 IF D=2 AND Y>0 THEN Y=Y-1
60 IF D=3 AND Y<24 THEN Y=Y+1
70 POKE 1024+Y*40+X,81
80 GOTO 20

The SID’s noise

The C64 has a second generator in its sound chip. A program can read the top eight bits of voice 3’s oscillator at $D41B (54299), and the data sheet says that with the noise waveform selected it “will produce a series of random numbers, therefore, this register can be used as a random number generator for games”. The Programmer’s Reference Guide adds that the register “is not affected in any way by the envelope”, so the voice can stay silent with its gate off. In BASIC:

10 POKE 54286,255:POKE 54287,255
20 POKE 54290,128
30 FOR I=1 TO 8:PRINT PEEK(54299);:NEXT

Lines 10 and 20 set voice 3’s frequency to its maximum and select noise with the gate off. In machine code the read is a single instruction, far faster than RND:

init    lda #$ff
        sta $d40e       ; voice 3 frequency, low byte
        sta $d40f       ; voice 3 frequency, high byte
        lda #$80
        sta $d412       ; voice 3: noise waveform, gate off
        rts

random  lda $d41b       ; upper 8 bits of oscillator 3
        rts

This is not true randomness either. The noise comes from a 23-bit shift register, which reSID’s source code describes as “clocked by bit 19 of the accumulator”, so at the top frequency it moves on about every 16 cycles. Its eight output bits are taken from the same register, so reads made close together are related: in an emulated C64, sixteen reads about 60 cycles apart began 252, 248, 192, 129, 6, 24, with bit patterns visibly sliding from one value to the next. Space the reads out, or mix the noise with another source, when it matters.

The ZX Spectrum’s RND

Sinclair’s manual for the ZX Spectrum was candid: “RND is not truly random, because it follows a fixed sequence of 65536 numbers.” Its exercises, written for “mathematicians only”, give the rule: the Spectrum “uses p=65537 and a=75”. The ROM keeps a 16-bit seed in the system variable SEED. Each RND adds 1 to it, multiplies by 75, takes the remainder after dividing by 65,537, subtracts 1, and stores that as the new seed; the result is the seed divided by 65,536. Because 75 is a primitive root of the prime 65,537, which the manual invites the reader to prove, the sequence visits all 65,536 values before it repeats.

RANDOMIZE n sets the seed, so the manual can promise that after RANDOMIZE 1 “the RND sequence starts off again with 0.0022735596”: (1 + 1) × 75 = 150, minus 1 is 149, and 149 ÷ 65,536 = 0.0022735596. RANDOMIZE on its own, or RANDOMIZE 0, seeds from the time since the computer was switched on, the Spectrum’s version of RND(-TI). The manual warns against calling it repeatedly in a loop: the time “has gone up by the same amount each time”, so the numbers that follow are “not very random”.

See also

• Commodore BASIC V2
• SID chip
• Variables and memory
• Screen memory
• Procedural generation
• Sinclair BASIC
• Commodore 64 Programmer’s Reference Guide
• The Complete Spectrum ROM Disassembly