Randomness

Revision as of 19:00, 11 July 2011 (view source)

JeremyDouglass (Talk | contribs)

(→The C64 and the RND Function: added sub-section headers)

← Older edit

Revision as of 22:20, 11 July 2011 (view source)

JeremyDouglass (Talk | contribs)

(→The History of RND)

Newer edit →

Line 130:

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

−

...

+

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:

+

<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>

+

[*NOTE*: The following paragraph could be a sidebar. May also need to cut this down if it is too much of an aside. Need to fact-check the assertion that /W instruction relates 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]

+

+

Turing's addition of a built-in random function (not present in the Manchester prototype) may have been specifically motivated by 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, and 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 modified form) in the 6502 Microsoft BASIC that became the core of Commodore BASIC in the Commodore PET, VIC-20, and 64.

+

+

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>

+

</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.

+

[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 ====

From Maze

Revision as of 22:20, 11 July 2011

Views

Personal tools

Navigation

Search

Toolbox

@@ Line 130: / Line 130: @@
 ==== The History of RND ====
-...
+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:
+<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>
+[*NOTE*: The following paragraph could be a sidebar. May also need to cut this down if it is too much of an aside. Need to fact-check the assertion that /W instruction relates 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]
+<blockquote>
+Turing's addition of a built-in random function (not present in the Manchester prototype) may have been specifically motivated by 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, and 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 modified form) in the 6502 Microsoft BASIC that became the core of Commodore BASIC in the Commodore PET, VIC-20, and 64.
+<blockquote>
+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>
+</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.
+[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 ====