Randomness

...

----

Ever since the 1950s, a function to generate a random number has been built into most computer systems. The earliest version of BASIC included such a function, the familiar RND command. As the manual for the first Dartmouth version of BASIC describes the function, RND(X) produced a "new and different random number" between 0 and 1 "each time it is used in a program" (39). As noted by the manual, however, each time a program was run, "the same sequence" of random numbers is generated. If a BASIC program generated a string of random digits such as 9, 0, 4, 1, 6, 4, it would produce the exact same numbers the next time the program ran. This lack of variation is an extreme example of what mathematicians call "pseudo-randomness"--a process or algorithm that appears to be random, but which, if left running long enough, will reveal itself to be a pattern. While the "pseudo" prefix would seem to denigrate this type of randomness as "not really" random, pseudo-randomness is generally acceptable, and in fact, desirable in many situations. For example, engineers running a computer simulation often need random variables, but they need those random variables ''to be the same'' with every run of the simulation; otherwise it is impossible to narrow down what process is actually being modeled in the simulation. Pseudo-random number generators are the only kind that are useful in hashing, since they allow data to be distributed widely but also placed in known locations.

The C64 User's Guide introduces the concept of randomness using an example that sidesteps the origins of randomness in computing. There's no mention of nuclear fission or computer-generated literature. Randomness comes into play in the shape of a game, when it's necessary to, as the manual puts it, "simulate the throw of dice" (48)--an example that takes us back to pre-industrial notions of randomness.

The MOS6510 chip powering the Commodore 64 featured three ways of generating random numbers. The RND function in BASIC supplies two official means, while the sound chip provides another route. In addition to these out of the box methods, programmers could also write their own randomization algorithms, similar to the way Von Neumann or Knuth attempted to generate random numbers through mathematical functions.

Of course, it's inefficient to need an entire routine such as this to generate random numbers. This is where the C64's RND function comes into play. As described above, when RND(1) is called on the Commodore 64, a deterministic sequence of random numbers is produced. The precise algorithm is called a linear congruential generator (LCG), first proposed by Lehmer in 1949, though the C64 version includes additional byte-swapping. The LCG begins with a common seed, and nearly every C64 in the world will respond the same way to the maze program because they all rely on this mode of random number generation.

[INCLUDE MORE ABOUT LEHMER AND A EASY-TO-FOLLOW SUMMARY OF HOW LCG WORKS. IN ADDITION TO REPEATABILITY, ARE THERE OTHER IMPORTANT PROPERTIES WORTH GOING INTO?]

Another way of using the Commodore 64's built-in random number generation begins by using RND(0)--as opposed to RND(1). This method uses the MOS6510 chip's timer as a random number generator. [HOW, EXACTLY?] [AND WHY WOULD A PROGRAM USE RND(1) OVER RND(0)? WHAT ARE ADVANTAGES AND DISADVANTAGES OF EITHER METHOD? ALSO, WHAT ABOUT RND(-1)?]