Randomness

Revision as of 23:15, 11 July 2011 (view source)

JeremyDouglass (Talk | contribs)

(→The History of RND: refined connection between primes-pseudorandomness and Lehmer-Turing)

← Older edit

Revision as of 00:53, 12 July 2011 (view source)

JeremyDouglass (Talk | contribs)

(→RND by Startup, Stopwatch, or Seed)

Newer edit →

Line 153:

[[Image:10print-startup-canonical.png|160px|thumb|The first page of "canonical" 10 PRINT output when run immediately after startup.]]

−

RND is, like most computational sources of randomness, a pseudorandom number generator (PRNG). While there may be no apparent pattern between any two numbers, each number is generated based on the previous one using a deterministic process. When the first number is the same, the entire sequence will be the same, every time. In the case of the C64, this is particularly important because the same first number is set, at startup, on almost every C64 system. This means that, when RND(1) is invoked immediately after startup, or before any other invocation of RND, it will always produce the same result: .185564016. The next invocation will also be the same, no matter what the time or which Commodore 64 is used, and the next. Since the sequence is deterministic, the pattern produced by the 10 PRINT program, when run before any other invocation of RND, is always the same, on any C64. [NOTE: last two sentences cribbed from early annotation, need to rephrase, think about repetition issue].

+

RND is, like most computational sources of randomness, a pseudorandom number generator (PRNG). While there may be no apparent pattern between any two numbers, each number is generated based on the previous one using a deterministic process. When the first number is the same, the entire sequence will be the same, every time. In the case of the C64, this is particularly important because the same first number is set, at startup, on almost every C64 system. This means that, when RND(1) is invoked immediately after startup, or before any other invocation of RND, it will always produce the same result: .185564016. The next invocation will also be the same, no matter what the time or which Commodore 64 is used, and the next. Since the sequence is deterministic, the pattern produced by the 10 PRINT program on startup is always the same, on any C64. [NOTE: last two sentences cribbed from early annotation, need to rephrase, think about repetition issue].

+

When called on *any* positive number, RND produces the next number in this sequence. This is the case when 10 PRINT calls RND(1). However, RND has two other modes. The second is stopwatch-based: when RND(0) is called, the clock time since startup is used in generating a new seed, meaning that each timing of running 10 PRINT should generate a different output. After a single call to RND(0), subsequent calls to RND(1) will continue generating numbers in that new sequence.

+

The third mode for RND applies when any negative number is called. This stores that seed directly, and produces a new number. However, this negative seeding must be followed by positive RND(1) calls in order to provide a useful sequence. Because negative calls replace the seed directly rather than iterating it, calling RND(-0.123) repeatedly will always return 0.544630526, no matter how ofter it is called. For this reason, 10 PRINT could not be a single-line loop that calls a negative RND value, as it would always produce pages of the same diagonal. However, a single call to any negative number, followed by running the normal 10 PRINT program, will generate a unique (and repeatable) 10 PRINT 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. Pseudo-random number generators are also 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 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 inﬁnite 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 ====

From Maze

Revision as of 00:53, 12 July 2011

Views

Personal tools

Navigation

Search

Toolbox

@@ Line 153: / Line 153: @@
 [[Image:10print-startup-canonical.png|160px|thumb|The first page of "canonical" 10 PRINT output when run immediately after startup.]]
-RND is, like most computational sources of randomness, a pseudorandom number generator (PRNG). While there may be no apparent pattern between any two numbers, each number is generated based on the previous one using a deterministic process. When the first number is the same, the entire sequence will be the same, every time. In the case of the C64, this is particularly important because the same first number is set, at startup, on almost every C64 system. This means that, when RND(1) is invoked immediately after startup, or before any other invocation of RND, it will always produce the same result: .185564016. The next invocation will also be the same, no matter what the time or which Commodore 64 is used, and the next. Since the sequence is deterministic, the pattern produced by the 10 PRINT program, when run before any other invocation of RND, is always the same, on any C64. [NOTE: last two sentences cribbed from early annotation, need to rephrase, think about repetition issue].
+RND is, like most computational sources of randomness, a pseudorandom number generator (PRNG). While there may be no apparent pattern between any two numbers, each number is generated based on the previous one using a deterministic process. When the first number is the same, the entire sequence will be the same, every time. In the case of the C64, this is particularly important because the same first number is set, at startup, on almost every C64 system. This means that, when RND(1) is invoked immediately after startup, or before any other invocation of RND, it will always produce the same result: .185564016. The next invocation will also be the same, no matter what the time or which Commodore 64 is used, and the next. Since the sequence is deterministic, the pattern produced by the 10 PRINT program on startup is always the same, on any C64. [NOTE: last two sentences cribbed from early annotation, need to rephrase, think about repetition issue].
+When called on *any* positive number, RND produces the next number in this sequence. This is the case when 10 PRINT calls RND(1). However, RND has two other modes. The second is stopwatch-based: when RND(0) is called, the clock time since startup is used in generating a new seed, meaning that each timing of running 10 PRINT should generate a different output. After a single call to RND(0), subsequent calls to RND(1) will continue generating numbers in that new sequence.
+The third mode for RND applies when any negative number is called. This stores that seed directly, and produces a new number. However, this negative seeding must be followed by positive RND(1) calls in order to provide a useful sequence. Because negative calls replace the seed directly rather than iterating it, calling RND(-0.123) repeatedly will always return 0.544630526, no matter how ofter it is called. For this reason, 10 PRINT could not be a single-line loop that calls a negative RND value, as it would always produce pages of the same diagonal. However, a single call to any negative number, followed by running the normal 10 PRINT program, will generate a unique (and repeatable) 10 PRINT 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. Pseudo-random number generators are also 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 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 inﬁnite 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 ====