Randomness
From Maze
(Difference between revisions)
(Edited first paragraph) | (Removed SID section, moving it to Remarks: thread) | ||
| Line 164: | Line 164: | ||
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 or prime numbers. Randomness comes into play in the shape of a game, when it is 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. Perhaps it is not the area of application, but the mechanism that needs to be wrapped in a comfortable physical metaphor. In his Mark 1 manual, Turing gives as a sample application "a man in New York" who navigates four-way intersections "by twice tossing a coin." The rolled die and the tossed coin are comfortable (if inaccurate) physical analogies to sequences of prime-number driven modulo arithmetic. By contrast, the hypothetical New Yorker randomly wandering "an infinite rectangular lattice of streets and avenues" is not an immediately familiar scenario -- unless, from our historical vantage, we count the image of a ghost wandering the mazes of Ms. Pac-Man. | 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 or prime numbers. Randomness comes into play in the shape of a game, when it is 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. Perhaps it is not the area of application, but the mechanism that needs to be wrapped in a comfortable physical metaphor. In his Mark 1 manual, Turing gives as a sample application "a man in New York" who navigates four-way intersections "by twice tossing a coin." The rolled die and the tossed coin are comfortable (if inaccurate) physical analogies to sequences of prime-number driven modulo arithmetic. By contrast, the hypothetical New Yorker randomly wandering "an infinite rectangular lattice of streets and avenues" is not an immediately familiar scenario -- unless, from our historical vantage, we count the image of a ghost wandering the mazes of Ms. Pac-Man. | ||
| − | ==== The SID: Sound as a second stochastic source ==== | ||
| − | |||
| − | While its predecessors such as the Commodore PET were able to generate random numbers, the Commodore 64 added another separate source of randomness, the MOS Technology 6581 Sound Interface Device (SID) chip. The SID was inspired by professional synthesizer electronics, and featured among other things the ability to produce square waves, sawtooth waves, triangle waves, and pseudo-random "noise." | ||
| − | |||
| − | By setting oscillator 3 on the SID chip to generate noise, then reading a noise output value in from register 27, a C64 BASIC or assembly program can draw on a second source of random numbers that changed constantly at the currently set speed of the oscillator. Because the SID is a mixed-signal integrated circuit (with digital control ports and analog output ports), a common misconception about the SID has been that it is a source of "true" or "high-quality" hardware-based random number generation, producing analog noise that was somehow the result of an analog process -- perhaps thermal noise, shot noise, or some other physical measurement of quantum indeterminacy. | ||
| − | |||
| − | However, this is not the case. SID noise is digitally generated by a 23-bit linear feedback shift register (LFSR), another common form of deterministically generating pseudorandom numbers. In an LFSR, a few selected bits are used to calculate one additional bit, then all old bits are shifted over one, with the new bit added to the top, and the process is repeated. In the SID, the result is something like a continuously running RND(1). | ||
| − | |||
| − | [NOTE: This really ends with a whimper right now. I'm not sure how to end on the SID and then bring this chapter home -- perhaps the SID section should be an aside in the previous section, and not its own.] | ||
| − | |||
| − | |||
| − | ---- | ||
| − | <blockquote>[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] | ||
| − | [Jeremy: On review, I'm not totally convinced of the value of working through complex textbook examples of using the SID with BASIC peek-poke (as below) -- particularly because use of the SID is already quite removed from the RND(1) method of how 10 Print does randomness, with RND(-x) and RND(0) / RND(TI) being closer. If we haven't introduced peek and poke already, it seems like a stretch to do it here. I'm more inclined to tersely summarize this material as one or two examples maximum, perhaps with direct reference to "Random Numbers In Machine Language For Commodore 64" (Neil Boyle) | ||
| − | http://www.atarimagazines.com/compute/issue72/random_numbers.php | ||
| − | ...also, I believe that some of the below is pseudocode, unless 'osc3read' is something that just doesn't work on the Power64 emulator. | ||
| − | ] | ||
| − | <pre> | ||
| − | 5 s=54272:poke s+15,100:pokes+18,128 | ||
| − | 10 print peek(s+27):goto 10 | ||
| − | </pre> | ||
| − | |||
| − | <pre> | ||
| − | 10 s=54272:pokes+15,100:pokes+18,128:printchr$(205.5+(peek(s+27)and1));:goto10 | ||
| − | </pre> | ||
| − | |||
| − | <pre> | ||
| − | 5 s=54272:pokes+15,100:pokes+18,128 | ||
| − | 10 print chr$(205.5+(peek(s+27)and1));:goto10 | ||
| − | </pre> | ||
| − | |||
| − | <pre> | ||
| − | 6 poke 54272+wave, noise | ||
| − | 10 print chr$(205.5+peek(54272+osc3read));goto 10 | ||
| − | </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: | ||
| − | |||
| − | <pre> | ||
| − | Rand8 | ||
| − | lda random ; get seed (must be non-zero) | ||
| − | asl ; shift byte | ||
| − | bcc Rand8.no_eor ; branch if carry flag not set after left shift | ||
| − | eor #$CF ; otherwise EOR with literal $CF | ||
| − | Rand8.no_eor | ||
| − | sta random ; save number as next seed | ||
| − | |||
| − | </pre> | ||
| − | </blockquote> | ||
| − | ---- | ||
| − | |||
=== Works Cited === | === Works Cited === | ||
