Randomness

Revision as of 22:23, 12 July 2011 (view source)

Nickm (Talk | contribs)

(→The Commodore 64's RND Function)

← Older edit

Revision as of 22:45, 12 July 2011 (view source)

Nickm (Talk | contribs)

(Removed info about the 1950s and edited the end)

Newer edit →

Line 126:

This aesthetic issue extends to both the appearance of the final output and the code. While it is possible to implement one's own pseudo-random number generator in a BASIC program, it would have lengthened and complicated 10 PRINT considerably if someone had added such code to it. It would certainly not have been a concise and elegant one-liner that fit into the MAGIC section of ''RUN.''

−

==== The History of RND ====

+

In 10 PRINT, random numbers are provided through RND, one of ten mathematical functions available in BASIC since the earliest version of the language. As described the original Dartmouth BASIC manual (1964), RND produces a "new and different random number" between 0 and 1 "each time it is used in a program" (39). Thus, calling RND(1) might return 0.185564016 the first time, 0.0468986348 the second, and 0.827743801 the third, with no apparent pattern between one number and the next. These numbers could then be used to drive unpredictable processes, as in fact they do drive the coin-toss decision between diagonal lines in 10 PRINT output. A similar process might also determine the direction changes of ghosts in ''Ms. Pac-Man,'' an arcade game that introduced randomness after the deterministic ''Pac Mac.''

−

Since the 1950s, most computer systems have offered a function to generate random numbers. One of the earliest examples is the world’s first commercial general-purpose computer, the Ferranti Mark I, whose /W function was used by Christopher Strachey in his 1952 love letter generator program. The instruction was added directly due to the work of Alan Turing, and in the 1951 documentation, Turing wrote that:

+

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

−

<blockquote>"[T]he principle that the state of the machine at one completion signal determines the state at the next is abandoned if instructions with function symbol /W are used. The behaviour of the machine is then to be described as a ‘stochastic’ (i.e. chance-controlled) process and is suitable for calculations concerned with stochastic processes. The instruction /W actually puts random digits into the twenty least signiﬁcant digits of the accumulator."</blockquote>

+

RND is, like most computational sources of randomness, a pseudorandom number generator. 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: 0.185564016. The next invocation will also be the same, no matter what Commodore 64 is used or how long the system has been on. The next invocation -- and all others -- will also be the same. Since the sequence is deterministic, the pattern produced by the 10 PRINT program on startup is always the same, on every computer or well-functioning emulator.

−

[*NOTE*: The following paragraph may be too technical, and may also need to cut this down if it is too much of an aside. Need to fact-check the assertion that *for Turing* adding the /W instruction was related to Mersenne research, perhaps in: Lavington, Simon (1998), A History of Manchester Computers (2 ed.), Swindon: The British Computer Society. See also Brian Napper, The Mathematics Department and the Mark 1. http://www.computer50.org/mark1/maths.html]

+

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 the computer was powered on 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.

−

Turing's addition of a built-in random function (not present in the Manchester prototype) may have grown out of his research interests in the search for large prime numbers, in particular his early work with Newman on using the early Manchester machines to search for Mersenne primes (i.e. primes amounting to one less than a power of two). Turing's 1949 prime search was implemented following the approach of Derrick Lehmer, who had developed the Lucas–Lehmer primality test. Turing's computational application of Lehmer's approach was later successfully applied by Lehmer's colleague Raphael Mitchel Robinson in 1952 in discovering the next five Mersenne primes (521, 607, 1279, 2203, 2281), and indeed has been used in all 30 discoveries of Mersenne primes since then, and is still used today in the distributed computing efforts of the Great Internet Prime Search. Lehmer, in turn, proposed in 1949 the linear congruential model for random number generation, a model which depended on relative primes in general and Mersenne primes in particular to generate long sequences of pseudorandom numbers. Both linear congruential generators (LCGs) in general and Lehmer random number generators (LRNGs) specifically would later be used in a variety of programming languages and computing platforms, including Dartmouth BASIC, the ZX Spectrum, and (in heavily modified form) in the 6502 Microsoft BASIC that became the core of Commodore BASIC in the Commodore PET, VIC-20, and 64.

+

The third mode for RND applies when any negative number is called. A call to RND(-17) stores -17 as the seed value for the random number generator, directly, and produces a new number. 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; that program would output the same diagonal again and again. 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 highly useful in hashing, since they allow data to be distributed widely but also placed in known locations. Similarly, they are useful in cryptography, where it is vital that sequences be repeatable if (and only if) the initial conditions are known.

−

Lehmer, D. H. (1949). "Mathematical methods in large-scale computing units". Proceedings of a Second Symposium on Large-Scale Digital Calculating Machinery: 141–146. MR0044899. (journal version: Annals of the Computation Laboratory of Harvard University, Vol. 26 (1951)).

−

http://www.reginaldtiangha.com/cpsc509/ferranti.htm

−

http://www.alpha60.de/research/muc/

−

http://www.alpha60.de/research/muc/Link_MustBeAnAngel_2006.pdf

−

</blockquote>

−

In 10 PRINT, random numbers are provided through RND, one of ten mathematical functions available in BASIC since the earliest version of the language. As described the original Dartmouth BASIC manual (1964), RND produces a "new and different random number" between 0 and 1 "each time it is used in a program" (39). Thus, calling RND(1) might return 0.185564016 the first time, 0.0468986348 the second, and 0.827743801 the third, with no apparent pattern between one number and the next. These numbers could then be used to drive unpredictable processes, such as coin-toss decision between diagonal lines in 10 PRINT output, or the direction changes of ghosts in Ms. Pac-Man.

+

The ''Commodore 64 Users Guide'' introduces the concept of randomness using an example that sidesteps the origins of randomness in computing. There is no mention of the hydrogen bomb, 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" (p. 48). This example that takes us back to pre-industrial notions of randomness. Yet, centuries ago, Sir Walter Raliegh wrote of a throw of the dice as apocalyptic -- long before Mallarmé assured us that it would not abolish chance: "Dead bones shall then be tumbled up and down, / In every city and in every town." Fortune's wheel and what Paul Auster called ''The Music of Chance'' has long been considered a life and death matter. As 10 PRINT scrolls its playful, pleasing maze pattern upon the screen, there may be the faintest echo of the dead bones of the dice and the random simulation of the hydrogen bomb. And perhaps, as well, there is the transformation of this grim, military use of randomness into a thing of beauty.

−

[Note: this reference to Ms. Pac-Man is meant to reconnect to the examples above, but might be slightly misleading?, as the most popular C64 version of Ms. Pac-Man certainly wasn't implemented in BASIC. What do other think -- use a different second example?]

−

==== RND by Startup, Stopwatch, or Seed ====

−

[[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: 0.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. PNRGs are also highly useful in hashing, since they allow data to be distributed widely but also placed in known locations, as well as in cryptography, where it is vital that sequences be repeatable if (and only if) the initial conditions are known.

−

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.

=== Works Cited ===

From Maze

Revision as of 22:45, 12 July 2011

Views

Personal tools

Navigation

Search

Toolbox

@@ Line 126: / Line 126: @@
 This aesthetic issue extends to both the appearance of the final output and the code. While it is possible to implement one's own pseudo-random number generator in a BASIC program, it would have lengthened and complicated 10 PRINT considerably if someone had added such code to it. It would certainly not have been a concise and elegant one-liner that fit into the MAGIC section of ''RUN.''
-==== The History of RND ====
+In 10 PRINT, random numbers are provided through RND, one of ten mathematical functions available in BASIC since the earliest version of the language. As described the original Dartmouth BASIC manual (1964), RND produces a "new and different random number" between 0 and 1 "each time it is used in a program" (39). Thus, calling RND(1) might return 0.185564016 the first time, 0.0468986348 the second, and 0.827743801 the third, with no apparent pattern between one number and the next. These numbers could then be used to drive unpredictable processes, as in fact they do drive the coin-toss decision between diagonal lines in 10 PRINT output. A similar process might also determine the direction changes of ghosts in ''Ms. Pac-Man,'' an arcade game that introduced randomness after the deterministic ''Pac Mac.''
-Since the 1950s, most computer systems have offered a function to generate random numbers. One of the earliest examples is the world’s first commercial general-purpose computer, the Ferranti Mark I, whose /W function was used by Christopher Strachey in his 1952 love letter generator program. The instruction was added directly due to the work of Alan Turing, and in the 1951 documentation, Turing wrote that:
+[[Image:10print-startup-canonical.png|160px|thumb|The first page of output from 10 PRINT when run immediately after startup.]]
-<blockquote>"[T]he principle that the state of the machine at one completion signal determines the state at the next is abandoned if instructions with function symbol /W are used. The behaviour of the machine is then to be described as a ‘stochastic’ (i.e. chance-controlled) process and is suitable for calculations concerned with stochastic processes. The instruction /W actually puts random digits into the twenty least signiﬁcant digits of the accumulator."</blockquote>
+RND is, like most computational sources of randomness, a pseudorandom number generator. 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: 0.185564016. The next invocation will also be the same, no matter what Commodore 64 is used or how long the system has been on. The next invocation -- and all others -- will also be the same. Since the sequence is deterministic, the pattern produced by the 10 PRINT program on startup is always the same, on every computer or well-functioning emulator.
-[*NOTE*: The following paragraph may be too technical, and may also need to cut this down if it is too much of an aside. Need to fact-check the assertion that *for Turing* adding the /W instruction was related to Mersenne research, perhaps in: Lavington, Simon (1998), A History of Manchester Computers (2 ed.), Swindon: The British Computer Society. See also Brian Napper, The Mathematics Department and the Mark 1. http://www.computer50.org/mark1/maths.html]
+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 the computer was powered on 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.
-Turing's addition of a built-in random function (not present in the Manchester prototype) may have grown out of his research interests in the search for large prime numbers, in particular his early work with Newman on using the early Manchester machines to search for Mersenne primes (i.e. primes amounting to one less than a power of two). Turing's 1949 prime search was implemented following the approach of Derrick Lehmer, who had developed the Lucas–Lehmer primality test. Turing's computational application of Lehmer's approach was later successfully applied by Lehmer's colleague Raphael Mitchel Robinson in 1952 in discovering the next five Mersenne primes (521, 607, 1279, 2203, 2281), and indeed has been used in all 30 discoveries of Mersenne primes since then, and is still used today in the distributed computing efforts of the Great Internet Prime Search. Lehmer, in turn, proposed in 1949 the linear congruential model for random number generation, a model which depended on relative primes in general and Mersenne primes in particular to generate long sequences of pseudorandom numbers. Both linear congruential generators (LCGs) in general and Lehmer random number generators (LRNGs) specifically would later be used in a variety of programming languages and computing platforms, including Dartmouth BASIC, the ZX Spectrum, and (in heavily modified form) in the 6502 Microsoft BASIC that became the core of Commodore BASIC in the Commodore PET, VIC-20, and 64.
+The third mode for RND applies when any negative number is called. A call to RND(-17) stores -17 as the seed value for the random number generator, directly, and produces a new number. 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; that program would output the same diagonal again and again. 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.
-<blockquote>
+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 highly useful in hashing, since they allow data to be distributed widely but also placed in known locations. Similarly, they are useful in cryptography, where it is vital that sequences be repeatable if (and only if) the initial conditions are known.
-Lehmer, D. H. (1949). "Mathematical methods in large-scale computing units". Proceedings of a Second Symposium on Large-Scale Digital Calculating Machinery: 141–146. MR0044899. (journal version: Annals of the Computation Laboratory of Harvard University, Vol. 26 (1951)).
-http://www.reginaldtiangha.com/cpsc509/ferranti.htm
-http://www.alpha60.de/research/muc/
-http://www.alpha60.de/research/muc/Link_MustBeAnAngel_2006.pdf
-</blockquote>
-In 10 PRINT, random numbers are provided through RND, one of ten mathematical functions available in BASIC since the earliest version of the language. As described the original Dartmouth BASIC manual (1964), RND produces a "new and different random number" between 0 and 1 "each time it is used in a program" (39). Thus, calling RND(1) might return 0.185564016 the first time, 0.0468986348 the second, and 0.827743801 the third, with no apparent pattern between one number and the next. These numbers could then be used to drive unpredictable processes, such as coin-toss decision between diagonal lines in 10 PRINT output, or the direction changes of ghosts in Ms. Pac-Man.
+The ''Commodore 64 Users Guide'' introduces the concept of randomness using an example that sidesteps the origins of randomness in computing. There is no mention of the hydrogen bomb, 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" (p. 48). This example that takes us back to pre-industrial notions of randomness. Yet, centuries ago, Sir Walter Raliegh wrote of a throw of the dice as apocalyptic -- long before Mallarmé assured us that it would not abolish chance: "Dead bones shall then be tumbled up and down, / In every city and in every town." Fortune's wheel and what Paul Auster called ''The Music of Chance'' has long been considered a life and death matter. As 10 PRINT scrolls its playful, pleasing maze pattern upon the screen, there may be the faintest echo of the dead bones of the dice and the random simulation of the hydrogen bomb. And perhaps, as well, there is the transformation of this grim, military use of randomness into a thing of beauty.
-[Note: this reference to Ms. Pac-Man is meant to reconnect to the examples above, but might be slightly misleading?, as the most popular C64 version of Ms. Pac-Man certainly wasn't implemented in BASIC. What do other think -- use a different second example?]
-==== RND by Startup, Stopwatch, or Seed ====
-[[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: 0.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. PNRGs are also highly useful in hashing, since they allow data to be distributed widely but also placed in known locations, as well as in cryptography, where it is vital that sequences be repeatable if (and only if) the initial conditions are known.
-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.
 === Works Cited ===