Talk:Randomness
From Maze
Contents[hide] |
Turing and Randomness
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:
"[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 significant digits of the accumulator."
[*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]
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.
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
review by Noah 7/12/2011
-add Cage transcendental thought, transcendental/random numbers -Chance might produce? stunning poetry, breathtaking art, and uncanny music suggest: "lead to" (chance helped, but not produced) -a Million Random Digits, add ref to Dartmouth manual telling prgmrs throw away first N numbers -move properly randomized pic to top.
OK, structurally speaking, I think the section ends on a whimper (as it suggests) because the most important stuff: THE C64 AND RND got stuck at the end.
old structure "randomness is v. important. yup, c64 had it, too." suggestion: new stucture "c64 has this randomness, why? oh yeah because it's v. important."
Moved from Randomness Chapter on 6/16/2011
In C64 BASIC, a simplified means of generating a random number might look like this:
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
This program produces [insert string of random numbers generated by program]
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.
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.
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.
Although random numbers seem to against the concept of predictability, it turns out it is difficult to generate numbers that are extremely predictable.
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)
- 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
10 PRINT CHR$(205.9+RND(1));: GOTO 10
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.
Notes on Randomness from Nick, Noah, Mark and Patsy 5/7/2011
[In the salad days of home computing, approximately In my own memories from 1984 and beyond, RND was most often used to improve the quality of games. For example, in my endless clones of Breakout!, RND chose where the ball would drop into the game, how much it would wiggle through the air, and helped make the sound of the bricks exploding. It made the game a little bit different each time and more challenging -Noah]
points getting buried (Mark: I feel like the story we want to tell about randomness isn't quite drawn out yet. For me, the heart of the story is the dual role of randomness in culture, deployed as it is in both artistic expression and high-stakes predictive modeling) chronological order pre-reqs get naturally discussed nick: distinction b/t pseudorandomness, humanists have weak idea. needed to replicate studies describe case where is pseudo good-enough not good-enough nick: not moving first, but first fill-in writing in order to see connections two additional means of generating randomness ---how is the c64 compared to other machines randomness? ---is c64 is especially good at randomizing... is this an exemplary c64 program? (that would help circulate... does the c64 platform) (did someone discover, three years after released, no, cuz in prg ref guide) RND is in kernal, commodore, not microsoft, basic invokes something in the platform. 1st, get stuff out implications: ---burning question: why do computers produce random numbers!!! (-games, +computation) * use SID, reference * use ASM example, for numbers done out. typology of randomness (arithmetic approximations - which are they good for) beginning with randomness - faciliating ppl to make intelligent discussion. advantage of different types of randomness different seeds. lead to mersenne twister
The text formerly in "Randomness and Aesthetics Before Computing" was "a mix of notes and paragraphs and not draft yet." It's been moved to the Randomness in the Arts notes section.
- Another is the board used by compositors to keep type as pages are made up. what exactly is this? like something a comic book artist or newspaper layout person might use? Check http://libraries.mit.edu/get/oed -NM
- laying waste. does that mean shooting a country with missiles from the air or pooping? srsly! http://www.thefreedictionary.com/laying+waste -NM wow, my own link to the dictionary! thank you, but it still sounds odd here, perhaps because laying waste usually works with an indirect or direct object. | I changed that phrase to "devastation." I don't clearly understand why you're reading the phrase as "pooping," and neither does the dictionary, although I know that "waste" can be excrement etc. Anyway, it's easy to use a synonymous word/phrase there. -NM
- found an interesting early "pop" book on game theory that includes a random number table at the end: The Compleat Strategyst http://www.rand.org/pubs/commercial_books/CB113-1.html
//
Note for citation, use format (Montfort 2009, p. 24)
//
Notes from Skype 2 February 2011: - Historical factors and context from which "random" emerged. Certain things in time. - The meanings of what "random" means in computing vs common use in language. What does the concept of randomness mean to different people? People in computing vs. the general public.
//
Note from Noah: I have edited the first half of the randomness_in_the_arts, combined it with a few paragraphs about random music and pasted them here.
Note from Casey: I haven't put my notes into prose yet, but I have basic material here and more forthcoming here Randomness_in_the_Arts
//
After spending some hours on researching Truchet, I don't think his work fits in Random. The work he did on tiling is extraordinary and entirely relevant to 10 Print, but I can't find a single instance where Truchet himself used random values. If we move forward with a section about "grids" then I think he should go there. The article "The Tiling Patterns of Sebastien Truchet and the Topology of Structural Hierarchy" published in Leonardo has a translation of Truchet's original document.
Note from Mark: I agree with the Truchet. We were initially going to use him in the maze chapter, but it didn't fit there either. The Grids or Regularity chapter might be a good place. I've been reading up on him as well; it'll be interesting to see how our readings overlap. --MarkSample 23:56, 30 March 2011 (UTC)
//
We don't have a natural place in this document yet for the use of random values in the sciences. I've started to come across names, but haven't done any research yet: Charles Sanders Peirce, Ronald Fisher, (Frank Yates),
//
10 Print Random Chapter Notes
- Not satisfied with the opening paragraph
- Don’t quite get the opening lines of the etymology section. “chance is hap”? Though it might be useful to talk about the real root of “chance” -- late Latin cadentia falling
- The origins of “random” are quite different from the computional meaning of randomness, which is more along the lines of “chance” (versus impetuousness). Possibly play up this distinction.
- After the the discussion of Knuth and SAGA II is where the chapter’s authorial tone tapers off, switching to informal 2nd person, notes, etc.
Larger organizational questions: I wonder if the semi-chronological structure (randomness pre-computing, randomness with computing) obscures some of the salient points we want to make about aesthetic design. --MarkSample 17:19, 7 May 2011 (UTC)
//
I've moved this from the main Random chapter -- it'll probably fit in later with randomness and the C64 section.
- Parallel Audible Example
In addition to the visual arts, randomness has a place in music as well. To musicians such as Douglas Cope, who make generative music, randomness serves as an accompaniment to the structure of a piece. To keep things simple, we have constructed an audible clone of 10 PRINT which interested readers may like to type in and try out. It takes many more lines than 10 PRINT because the C64 was never endowed with specific BASIC commands for making sound and graphics. The heart of this program is lines 35-75. RND(1) is used to select whether a C or F# note is played. After entering the program and typing RUN, the listener will hear a sequence of evenly-spaced alternating notes, similar to how 10 PRINT displays evenly-spaced alternating / and \ symbols. Of course, the stream of audio does not have a "wrap" function like the terminal does, so there is no means for a "maze" to appear. Readers can judge for themselves, however, what kind of equivalences there are between the visual and audible version of the program.
10 poke 54296,15:poke 54277,190:poke 54278,248 31 a(0)=17:a(1)=37:a(2)=21:a(3)=76 35 q=int(.3+rnd(1)*1):print q 40 poke 54273,a(q*2):poke 54272, a(q*2+1) 50 poke 54276,17:for t=1to15:next 70 poke 54276,16:for t=1to15:next 75 goto 35
--MarkSample 20:26, 15 May 2011 (UTC)
The broken RND implementation
It might be worth mentioning that there are some real mixed reviews on the behavior of the Commodore 64 RND. Essentially, Microsoft got fancy with adding "improvements" on top of the RND linear congruent generator, and in doing so dramatically broke it, introducing behaviors that dramatically shorten how many different numbers it generates in sequence before the entire sequence repeats. In studying the first 1000 seeds that could be set by RND(-X), Afflerbach discovered that the vast majority (958) would fall into a short repeating sequence of just 13,379 numbers, a far cry from the ~100,000,000,000 non-repeating numbers that could be possible.
In the case of 10 PRINT, this means that, with 25x40=1000 characters making up a page, most random seeds will fall into a cycle of just 13 printed pages appearing in endless repetition. This "repetition" is complicated slightly by the fact that the cycle "starts over" mid-line. The result is a form of partial repetition -- the same alignment of maze walls scroll by, but shifted along the x axis so as to appear partially wrapped across the screen. [NEED TO TEST THIS, possibly screen cap it.]
Afflerbach, Lothar. Algorithms: The pseudo-random number generators iCommodore and Apple microcomputers. Statistische Hefte (Statistical Papers) 26, 321-333. Springer-Verlag, 1985.
Bowman, Richard L. "Evaluating Pseudo-Random Number Generators." Comput. & Graphics, Vol. 19, No. 2, pp. 315-324, 1995. [In 1995, by contrast, Bowman finds the C64 BASIC RND output to perform at least as well as much more contemporary professional implementations such as Mathematica -- although I'm not sure if this is based on some different (much later) implementation of Commodore BASIC, or if the paper is not competent.]
--JeremyDouglass 07:01, 12 July 2011 (UTC)
Patsy's Edit Notes
1. Commodore Free -- needs a footnote ad a bib entry.
2. "by the very appropriately-named RAND Corporation" suggests that that is why it was so named; but that is inaccurate. I recall its having to do with "research and development." So something like "in hindsight aptly-named RAND" might minimize the risk of misinforming readers accidentally, as it were.
3. Both "(see, for example, Rotenberg's work in the late fifties)" and "(see Green et al.'s work at MIT, with joint support of the U.S. Army, Navy, and Air Force)" ought to be relegated to notes.
4. Shouldn't "Each figure, named after a real person, is placed randomly on the page and given a random status: dead, wounded, or missing." read "Each figure, named after a real person, is placed randomly on the page and randomly given a status: dead, wounded, or missing."?
5. in "...processes, but than again, full exploitation of its unique talents..." I corrected Than to then -- but is it sic instead? Who captured this sentence? It needs a footnote-- is it from the 1962 or the 1970 work--or some other--work?
6. Please correct the tautology in "A regular password would allow for a password, URL, or distorted word that could be predicted."
7. I think the "Computers using Ethernet" paragraph ought to be simplified and reduced. The central point is that message collisions and jamming are dealt with by processes of randomness. If we want to provide the detail the paragraph provides, it can still be stated much more effectively. For example: "a sending computer that detects the problem, sending a jamming signal and trying to restart the transmission" is muddled. Should it be "the computer that detects the problem sends a jamming signal and tries to restart the transmission."? Still too weird (and maybe wrong?) How about: "a computer detecting the problem tries to restart the transmission but chooses at random to wait or restart immediately." [which dispenses with the next belabored sentence.] -- Can someone take this paragraph? I would, save that I might get it wrong!
