Randomness
From Maze
(Difference between revisions)
(→Randomness in Contemporary Computing) | (Worked this section into draft text) | ||
| Line 105: | Line 105: | ||
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 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. | ||
| − | [NOTE: THE FOLLOWING PARAGRAPHS OF THIS SECTION ARE NOT YET IN DRAFT TEXT FORM:] An important feature of computing is the opposite of randomness, regularity. Computer chips differ greatly from the outer world in their orderliness. Unlike our beaches or the bumpy landmasses with weather on which we build our houses, the world inside chips is meticulously fabricated, symmetrical, isolated and predictable. In fact, its basis is one massive crystal grown from purified silicon. It is so perfect that it is difficult to create unanticipated behavior. | + | 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. In C64 BASIC, a simplified means of generating a random number might look like this: |
| − | As randomness in the home computer market transitioned from being a mere source of artificial surprise into practical security applications, computer chips were designed with modules designed to encourage random amounts of heat energy to influence their silicon junctions to hasten the creation of unpredictable data. To those who believe all security is security through obscurity, this is part of the essence of encryption - the production of obscurata. | + | <pre> |
| + | 5 rem simplified random number generator | ||
| + | 6 a = 1 | ||
| + | 10 a = a*2 | ||
| + | 20 if a >= 256 then goto 30 | ||
| + | 25 | ||
| + | 30 random = a: print random: goto 10 | ||
| + | </pre> | ||
| − | Patterns in these data are way behind the abilities of humans to predict in our heads, and are even difficult for many computers to suss out. | + | This program produces [insert string of random numbers generated by program] |
| − | * How the number is actually generated | + | 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. |
| − | But normally, digital orderliness is the rule. It is at least true for the chip (MOS6510) running the Commodore 64’s BASIC interpreter, as well as the chip running the original BASIC interpreter at Dartmouth. The next section will talk about the harnessing of randomness. | + | [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?] |
| − | Reliability of the randomness. Point out that pseudo-randomness is not bad or inferior. | + | 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?] |
| − | Although random numbers seem to against the concept of predictability, it turns out it is difficult to generate numbers that are extremely predictable. The Commodore 64 included three ways of making random numbers out of the box. The RND function in BASIC supplies two official means, the sound chip, provides one. Programmers have been writing their own randomization algorithms. | + | Finally, it is possible to generate random number on the Commodore 64 without using either RND function, relying instead upon the Sound Interface Device (SID) chip to produce random "noise." Reading the SID from register 27 (in decimal format) returns the current value of oscillator 3. If it's set to noise, the SID doubles as a random number generator. [IT'S UNCLEAR HOW THIS WORKS...MORE EXPLANATION NEEDED FOR NON-PROGRAMMING READERS] |
| − | On the Commodore 64, when RND(1) is called. It produces a deterministic sequence of random numbers. | + | [SUGGESTION: INTRODUCE THE FOLLOWING PROGRAMS BY DESCRIBING THE FUNCTION OF THE PEEK AND POKE AND WALKING READER THROUGH THE WAY THIS PROGRAMS CALL UPON THE SID] |
| − | The algorithm used to do this a linear congruential generator with some extra byte-swapping taking place. | ||
| − | The linear congruential generator (LCG) was proposed by Lehmer in 1949. It 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. | ||
| − | |||
| − | Commodore inherited this from Dartmouth BASIC? | ||
| − | |||
| − | Dartmouth | ||
| − | |||
| − | The original BASIC manual shows that Dartmouth Basic (the first BASIC), had a similar specification for the RND(x) function. It generated a single stream of pseudorandom numbers. Interestingly, it recommends throwing away the first "115" or so numbers. (reference: BASIC_Oct64.pdf, page 45 of PDF, page -39- of original document) | ||
| − | |||
| − | LCGs have some interesting properties. One of them is repeatability. | ||
| − | |||
| − | The C64 allows offered another way of doing it: RND(0). This uses the timer as a random number generator. | ||
| − | |||
| − | * How Randomness Works, what it's good for | ||
| − | |||
| − | Inside the home computer, similar to its function in the arts, randomness adds unpredictability to otherwise repetitive processes. | ||
| − | |||
| − | Early definitions of randomness suggested urgency or fear and predate widespread computation. Their grounding in external events stood ground alongside the spread of Cartesian thought. | ||
| − | |||
| − | So now that randomness starts to become a controllable, recognizable pattern to millions of home computer users, it can be used to help interpret the world. Randomness also helps explain concepts like lotteries, insurance. It can explain the concept of bias, which is part of processes like polls, lotteries and elections. | ||
| − | |||
| − | With a large percentage of the natural world governed by events which can be characterized and in some times predicted, the use of randomness can also serve as a means of interpretation of the world. For example, in scientific pursuits, such as Van Neuman's design of atomic bomb, randomness is used to characterize nature, specifically to predict the interactions of high-energy particles. | ||
| − | |||
| − | Van Neuman's early use of computer-generated random number generation has steadily extended into electronic devices which today generate random series with measurably improved characteristics. | ||
| − | |||
| − | Techniques have improved since the time of Neumann. | ||
| − | |||
| − | |||
| − | * Alternative methods of finding randomness within the C64. | ||
| − | * Use multiple seeds, then SID register random | ||
| − | |||
| − | SID Noise | ||
| − | |||
| − | It was possible on the C64 to get random values from the Sound Interface Device (SID) chip. Reading from register 27 (decimal) returns the current value of oscillator 3. If it's set to noise, you get a random number generator. | ||
<pre> | <pre> | ||
| Line 174: | Line 147: | ||
</pre> | </pre> | ||
| − | + | In addition to these methods of generating a random number in BASIC, it is possible to generate a random number on the C64 in assembly language: | |
| − | Assembly routine (Ian) | ||
<pre> | <pre> | ||
| Line 187: | Line 159: | ||
</pre> | </pre> | ||
| − | |||
| − | <pre> | ||
| − | 5 rem simplified random number generator | ||
| − | 6 a = 1 | ||
| − | 10 a = a*2 | ||
| − | 20 if a >= 256 then goto 30 | ||
| − | 25 | ||
| − | 30 random = a: print radnom: goto 10 | ||
| − | </pre> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | * Develop three or four one-liners | ||
| − | * User/programmer side | ||
| − | |||
| − | |||
| − | * How it could be used to teach someone randomness/probability | ||
| − | * Prg in User guide demo of biasing randomness | ||
| − | |||
| − | Above, it was suggested to the reader to try out the program | ||
| − | |||
| − | <blockquote> | ||
| − | 10 PRINT CHR$(205.9+RND(1));: GOTO 10 | ||
| − | </blockquote> | ||
| − | |||
| − | Structurally, it's identical to 10 PRINT. Internally, one number has changed. Changing the bias makes the program more likely to print out / than \. This disrupts the subtle equilibrium needed to produce a convincing maze output. | ||
| − | |||
| − | This lesson was not documented here first. It is from the Commodore 64 User's Guide, a spiral-bound volume the size of a paperback which came with every store-bought Commodore 64. It gives try-as-you-go examples which teach the reader how to use the Commodore 64, with ample space devoted to BASIC programming. This is especially significant, considering that Commodore, a tightly-run company provided such thorough documentation, when minimal resources were dedicated toward the improvement of BASIC from previous version. | ||
| − | |||
| − | |||
| − | We also synthesize some of the previous sections, and discuss the aesthetic qualities of the 10 PRINT pattern in terms of randomness. | ||
=== Works Cited === | === Works Cited === | ||
