Randomness
From Maze
Contents[hide] |
An essential element of 10 PRINT CHR$(205.5+RND(1));: GOTO 10 is randomness; the program could not have anything like the same effect without it. The program uses randomness that is built in to the Commodore 64's BASIC programming language via the RND function. And the RND function is not special to the Commodore 64; it was present in the original Dartmouth BASIC. Furthermore, it's not just Commodore 64 BASIC that supplies random numbers. There are capabilities for generating random numbers that are provided by the built-in operating system, the KERNAL (the source of randomness that is used by BASIC) and by the sound chip, the SID. It's randomness all the way down. Producing randomness is a standard capability of the Commodore 64, provided by several different techniques. Randomness is just as important to other forms of modern computing.
This chapter explains what random numbers are, explaining certain different types of randomness. Then, it looks at the historical inception of functions for generating random numbers and some of the ways these random numbers have been used. The chapter considers how and why randomness is used in the arts. Through a nuanced discussion of randomness, the chapter argues that the maze pattern which 10 PRINT produces is entwined with a history of aesthetic and utilitarian coin flips and random processes.
Since chance is hap, the root of happy, it would seem that randomness, a type of chance, might have a happy etymology. Not so. Likely ancestors of the word "random" are found in Anglo-Norman, Old French, and Middle French and include randoun, raundun, raundoun, randon, randun, and rendon -- words indicating speed, impulsiveness, and violence. These predecessor words are found beginning around the 12th century and probably derive from randir, to run fast or gallop. Bumper stickers implore drivers to "practice random acts of kindness," but only because people in our culture fear random acts of violence so much that another phrase has become so ingrained that it can be punned upon -- and at a deeper level, perhaps, because the speed and violence of other vehicles are to be feared. While today it might be harmless for us to encounter "a random" (a person unknown to us, according to the Jargon File) sitting in the computer lab exploring a system at random, a "random encounter" centuries ago was much more likely to resemble a violent random encounter in Dungeons & Dragons. For instance, it could have been a figure on horseback hurtling through a village, trampling and slaughtering whoever he can reach.
In centuries past, before the age of enlightenment, randomness was a nightmare. Throughout its history, the word "random" has had some interesting meanings that became obsolete before the scientific and mathematical meaning became primary. One of these is the degree of elevation of a gun that can be used to maximize the range. Another is a board used by compositors to store type as pages are made up during the printing process. These particular randoms, used properly, both kill opponents and facilitate the process of textual composition. The RND found in 10 PRINT operates more in the compositional mode, selecting one of two character graphics for display on the screen via the PRINT command, which was originally made for putting ink on paper. But the very existence of RND in the Commodore 64 does have certain connections to speed, violence, the military, and devastation.
Random elements have played a role through millennia of culture in games of chance and divination. The roll of a die and toss of coin have long foretold the fortunes of men. The birth and proliferation of science was imagined, initially, to engender a more rational world view. Through Aristotle to Galileo to Newton, classical mechanics defined the universe as a defined system without random actions. Communications theory redefined noise as a random signal of measurable bounds which can be characterized and filtered out. While Einstein declared that "God does not play dice," probability and statistics has been extremely important to our scientific understanding of the world from the 20th century on. And, in 1897, poet Stephane Mallarme declared, in French, that "a throw of the dice does not abolish chance" -- presaging the importance than randomness and chance operations would have in the next century and beyond.
Randomness and Aesthetics Before Computing
Within the visual arts, the word chance is used more than our term random. The meaning of chance in this context is more general and covers a wider range of work. In his text Chance Imagery, the conceptual artist George Brecht clarifies between two types of chance operations, “one where the origin of images is unknown because it lies in deeper-than-conscious levels of the mind, and the second where images derive from mechanical processes not under the artist’s control.” The first definition describes the work of the surrealists and abstract expressionists who allow subconscious processes to dictate the work. The second definition correlates to how we define randomness; it describes the work of the artists most relevant to our interest in 10 PRINT.
In 1913, the French artist Marcel Duchamp made a strong statement with Three Standard Stoppages. He dropped three meter-long pieces of string from the height of one meter and let gravity and wind dictate the paths of the twisting string downward. He then adhered the string and recorded the shape by cutting it out of wood to make a new measurement. This act challenged the meter as a standard measurement and allowed Duchamp to construct his own standards as a parody of rational science and to undermine the authority of the meter. He wrote about the piece in 1914 that the falling thread distorts “itself as it pleases” and the “3 standard stoppages are the meter diminished.” On his use of randomness, Duchamp said, “Pure chance interested me as a way of going agains logical reality.” Duchamp was active within the Dada, and arts movement that reacted to the horrors of World War I with satire and absurdity. In the words of the Dada musician Gabrielle Buffet-Picabia, “Dada wished to destroy the reasonable frauds of men and recover the natural, unreasonable order. Dada wished to replace the logical nonsense of the men of today with an illogical nonsense.” To Jean (Hans) Arp, a Dada artist, individual authorship was synonymous to authoritarianism and random elements were used to liberate the work.
- 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 10Print 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
Continuing on with the musical interpretations, it is important to mention John Cage. Within the twentieth century, John Cage is most responsible for promoting random processes within the arts. Cage was strongly influenced by Duchamp. From Cage's point of view, random elements can remove individual bias from creation; they may be used to go beyond the limitations of the taste and bias through “chance operations”. In additional to his work as a composer following these ideas, Cage influenced generations of artists through his writing, lectures, and classes. In this text “Experimental Music”, Cage wrote, “Those involved with the composition of experimental music find ways and means to remove themselves from the activities of the sounds they make. Some employ chance operations, derived form sources as ancient as the Chinese Books of Changes, or as modern as the tables of random numbers used also by physicists in research.” [Cage 66, p. 10] [Note: Earle Brown used the following random sampling number tables: "M.G. Kendall and B. Babington Smith, A Table of Random Sampling Numbers. Tracts for Computers no. 24. (Cambridge, UK: Cambridge University Press, 1939)."] Cage's style of random composition was to create a system of parameters, then leave the results to circumstance. Cage explained, “This means that each performance of such a piece of music is unique, as interesting to its composer as to others listening. It is easy to see again the parallel with nature, for even with leaves of the same tree, no two are exactly alike.” [Cage 66, p. 11] Random components are used to transform a single composition into a space of potential compositions. Over the decades, Cage used an array of techniques to insert unexpected elements into this compositions. He defines the range of techniques used by himself and his contemporaries in the 1958 lectures “Composition as Process”. There are generally two methods for utilizing random values – using them at the time of composition to define the work, or to allow for variation while the work is performed. This second category of is most similar to 10 Print, where the random decisions are made during the programs execution, or to say it a different way, while the instructions are performed by the C64 operating system.
Within two-dimensional visual art, mechanical random processes were explored for the reasons championed by Cage. The eminent contemporary painter Gerhard Richter provides a simple answer to why this is beneficial, “I'm often astonished to find how much better chance is than I am.” There's precedent for chance used within visual works dating back to collage works by Jean (Hans) Arp from 1916, but the two most relevant early works to 10 Print are the Spectrum of Colors Arranged by Chance collage series (1951) by Ellsworth Kelly and Random Distribution of 40,000 Squares Using the Odd and Even Numbers of a Telephone Directory (1961) by François Morellet. Both of these works start with an even grid and proceed to fill the grid carefully with elements based on the algorithms developed by the artists. Kelly used squares of colored paper and placed according to a system he designed. He assigned a number to each color and then plotted the numbers on the grid according the a pseudo-mathematical system. [Malone 2009 p. 133] Morellet employed the more strict system by reading a series of numbers from the telephone book. He made a grid of 200 vertical and horizontal lines and if the assigned number was even, he painted the square blue; if the number was odd, he painted the square red. In both systems and in 10 Print, the structure of the grid makes it possible to focus on the variability created through the random operations.
The Emergence of Randomness in Computing
The RND command acts as the algorithmic heart of 10 PRINT, its flip-flopping beat powering the construction of the maze. It is also a paradox. The function of the RND token in 10 PRINT is immediately known yet its output is entirely unknown. Unpredictable. A cipher, the manifestation of a much deeper latent content, operating underneath the surface of the machine.
An obvious question to ask about randomness is why bother at all? Why have the ability in the first place to generate random numbers? Computers are supposed to calculate with exactitude. Computers are supposed to order the world. Computers are supposed to sift through reams of data and model possible outcomes, possible futures. Yet a function to create random numbers was present in the first Dartmouth BASIC. Every version of BASIC since then has had one or more ways to create random numbers. Finally, nearly every contemporary programming language, including Python, Perl, Java, Javascript and C++, has a way to generate randomness. It turns out to be impossible to model any kind of process without taking into account randomness. It is a defining feature of life—and the universe for that matter.
Quite simply, randomness is required for any statistical endeavor needing random sampling or tests of probability. And one or two random numbers are not enough. Large-scale statistical calculations or simulations require large batches of random numbers. In her history of humans’ quest for randomness--which Bennett suggests goes as far back as ancient Babylonia (17)--Bennett highlights one the early and largest set of random numbers, the RAND Corporation’s A Million Random Digits with 100,000 Normal Deviates (135). Generated in 1955 “by random frequency pulses of an electronic roulette wheel,” the RAND’s set of random numbers was an important contribution to any study of probability and is still in use today. As the forward to the undated online edition of the table notes:
The tables of random numbers in the book have become a standard reference in engineering and econometrics textbooks and have been widely used in gaming and simulations that employ Monte Carlo trials. Still the largest known source of random digits and normal deviates, the work is routinely used by statisticians, physicists, polltakers, market analysts, lottery administrators, and quality control engineers. (RAND Corporation)
These seemingly benign uses aside, the RAND report ominously explains that its one million random numbers were originally “prepared in connection with analyses done for the United States Air Force” (RAND Corporation). Like so many other advances in computing, randomness, it turns out, is intimately linked to Cold War military strategies. In fact, most of the early work on computer-based random number generation was performed under the auspices of the U.S. Atomic Energy Commission (see, for example, Rotenberg’s work in the late fifties) or the U.S military (such as Green et al’s work at MIT, with joint support of the U.S. Army, Navy, and Air Force).
As Donald Knuth relates in The Art of Computer Programming, John von Neumann was the first to propose the idea of harnessing a computer to generate random numbers (Knuth 3). It was around 1946 and von Neumann was fresh off the Manhattan Project and soon to begin his lead work on the hydrogen bomb. Von Neumann’s solution, for which a computer was to be used, was called the middle-square method. It worked by squaring an initial random number and extracting the middle digits; this number was then squared again, and the middle digits provided a new random number. The disadvantage of this method soon became apparent: because each number is a function of the one before it, the sequence, as Knuth explains, “isn’t random, but it appears to be” (3)--a phenomenon known today as “pseudo-randomness,” which arguably describes any human or machine attempt to generate random numbers.
Knuth gamely admits that his own attempts to generate random numbers through software algorithms—using what he hoped to be a “’super random’ number generator”--failed, though it’s worth noting that he wanted his machine language program “to be so complicated that a man reading a listing of it without explanatory comments would not know what the program was doing” (Knuth 5). It does not take a leap of imagination to see in Knuth’s desire for obscure code an early version of the same kind of mystery residing in 10 PRINT.
To those interested in randomness and expressive culture, perhaps the most intriguing element of Knuth’s magisterial discussion of random number appears in a footnote. Knuth recalls a CBS television documentary in 1960 called “The Thinking Machine” which featured “two Western-style playlets” written by a computer (Knuth, 1969, 158-160). In fact, three playlets were acted out on national television that day in October, 1960, generated by a TX-0 computer housed at MIT’s Electronics Systems Laboratory. As journalist John Pfeiffer noted in a book released two years after the documentary, SAGA II, the script-writing program behind the mini-Westerns, took programmers Douglas Ross and Harrison Morse two months and fifty-five hundred instructions to develop (Pfeiffer, 1962, 130-138). The key to SAGA II were its thirty “switches,” which made “various alternative or branching paths” possible (136). "Among other things,” Pfeiffer observed, “the robber may go to the window and look out and then go to the table, or he may go to the table directly. You cannot tell in advance which one of these alternatives the program will select, because it does the equivalent of rolling a pair of dice” (136).
Today, randomness in computing retains its character of predictability yet within constraints. Its nature has been exploited for practical purposes, such as security and communication. For instance, random numbers are used in encryption processes to make login passwords more secure. Intriguingly, the algorithms used and even their source code may be fully explained and published, but the data remain secure. Why? Because the space which random numbers occupy is so mind-bogglingly large, that no human being or computer could ever traverse it completely. Imagine playing a guessing game with a friend from 1 to 10. You can guess the number pretty easily, right? But what if the range of possible numbers was as large as the number of grains of sand a beach? Could you ever try all of those possibilities? Maybe it isn't as intuitive as it could be, but after an afternoon of playing with the RND on the function in BASIC, you may find that it makes more sense than before. If you want to try it for yourself, consider this program, which is really only a modest variation of 10Print.
10 PRINT CHR$(205.6+rnd(1)*1);:GOTO 10
Or this program, a simple guessing game which gives you a feel for how large and hopeless the space of random numbers can be. Once you get the hang of it, try changing to 10 into 20 or 1000 and see how much longer it takes to win.
10 N=INT(RND(0)*10) 20 PRINT "GUESS THE NUMBER:":INPUT G: IF G=N THEN PRINT "YOU WIN!":END 30 GOTO 20
While randomness supplies some of the apparent magic behind security and modeling natural processes, its value as a tool for making *orderly* communication can also seem mystical. Pseudo Random Number Generators, which will be demonstrated further below, will illustrate this. Another good example is the protocol called Ethernet, which is familiar to us today in the form of CAT-5 cables for office computers and in wireless form from our laptops.
Carefully applied randomness helps everything run smoothly. This is necessary in an Ethernet network which operates in some ways like a dinner conversation in that every single computer on the network can potentially try to talk at once. Other network protocols ensure that each computer gets a predictable time slot to speak, but Ethernet works differently. It has a means to determine if two machines have accidentally "spoken over" each other. Much like a human conversation, this one speaker must yield to the other. In the human word, such conflicts are sometimes embarrassing, awkward, or funny, and usually some kind of social rule will decide who gets to speak. For example, perhaps the elder speaker or the loudest one gets to talk. In Ethernet, there is no such hierarchy. Instead, each computer simply flips a coin and decides randomly whether or not to try to talk again. Of course, half of the time, this will not resolve the conflict, and they will have to do it again, and the process will repeat.
Computational Randomness in Aesthetic Design
2475 × 3225 pixels
2149 × 1890 pixels
888 × 392 pixels
[Randomness in art/computing appropriates the code/hardware from engineering uses.]
[Perlin Noise]
The 1960s were a time for radical experimentation with randomness in the visual arts. Even though computers were an available tool to explore chance operations, they were used in a limited way because of problems of access to the machines and a distrust of technology within the arts. The 10 PRINT program is remarkable because it represents the time when these reasons for not using computers in the visual arts were disappearing; the C64 was relatively inexpensive and designed for home use and the image of the computer was changing from machines that support technocracies to learning and self-empowerment tools.
Before personal computers, however, calculating machines could only be found in universities and research labs and because of the cost and perceived use. They were typically used exclusively for serious work, not for creating aesthetic images. When artists did gain access to these machines it was typically through artists-in-residence programs at companies such as Bell Labs and IBM, and through infrastructure such as Experiments in Art and Technology (E.A.T) based in New York and the Los Angeles County Museum of Art's Art and Technology initiative in Los Angeles. In fact, many of the first aesthetic computer graphics were made not by artists, but by mathematicians and engineers who were curious about the potential for other uses for the machines at their labs.
Within the first years that computer images were made, random processes were explored thoroughly. The first two exhibitions of computer-generated graphics appeared in art galleries in 1965 and both shows included pieces that were created using random values. In New York, the works of A. Michael Noll and Bela Julesz, both researchers at Bell Labs, were exhibited at the Howard Wise gallery from 6-24 April under the title “Computer-Generated Pictures”. In Stuttgart, the works of Georg Nees and Frieder Nake were exhibited at the Wendelin Niedlich Gallery from 5 - 26 November under the title “Computer-Grafik Programme”
[Include footnote about Noll, random, and the patent office.]
Writing with perspective in 1970, Noll highlights randomness as an essential feature of the computer in relation to the arts, “The computer is a unique device for the arts since it can function solely as an obedient tool with vast capabilities for controlling complicated and involved processes, but than again, full exploitation of its unique talents for controlled randomness and detailed algorithms could result in an entirely new medium – a creative artistic medium.”
The C64 and the RND Function
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.
- How the number is actually generated
But normally, digital orderliness is the rule. It is at least true for the chip (MOS6510) running the Commodore 64’s BASIC interpreter, as well as the chip running the original BASIC interpreter at Dartmouth. The next section will talk about the harnessing of randomness.
Reliability of the randomness. Point out that pseudo-randomness is not bad or inferior.
Although random numbers seem to against the concept of predictability, it turns out it is difficult to generate numbers that are extremely predictable. The Commodore 64 included three ways of making random numbers out of the box. The RND function in BASIC supplies two official means, the sound chip, provides one. Programmers have been writing their own randomization algorithms.
On the Commodore 64, when RND(1) is called. It produces a deterministic sequence of random numbers. The algorithm used to do this a linear congruential generator with some extra byte-swapping taking place. The linear congruential generator (LCG) was proposed by Lehmer in 1949. It begins with a common seed, and nearly every C64 in the world will respond the same way to the maze program because they all rely on this mode of random number generation.
Commodore inherited this from Dartmouth BASIC?
Dartmouth
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)
LCGs have some interesting properties. One of them is repeatability.
The C64 allows offered another way of doing it: RND(0). This uses the timer as a random number generator.
- How Randomness Works, what it's good for
Inside the home computer, similar to its function in the arts, randomness adds unpredictability to otherwise repetitive processes.
Early definitions of randomness suggested urgency or fear and predate widespread computation. Their grounding in external events stood ground alongside the spread of Cartesian thought.
So now that randomness starts to become a controllable, recognizable pattern to millions of home computer users, it can be used to help interpret the world. Randomness also helps explain concepts like lotteries, insurance. It can explain the concept of bias, which is part of processes like polls, lotteries and elections.
With a large percentage of the natural world governed by events which can be characterized and in some times predicted, the use of randomness can also serve as a means of interpretation of the world. For example, in scientific pursuits, such as Van Neuman's design of atomic bomb, randomness is used to characterize nature, specifically to predict the interactions of high-energy particles.
Van Neuman's early use of computer-generated random number generation has steadily extended into electronic devices which today generate random series with measurably improved characteristics.
Techniques have improved since the time of Neumann.
- Alternative methods of finding randomness within the C64.
- Use multiple seeds, then SID register random
SID Noise
It was possible on the C64 to get random values from the Sound Interface Device (SID) chip. Reading from register 27 (decimal) returns the current value of oscillator 3. If it's set to noise, you get a random number generator.
5 s=54272:poke s+15,100:pokes+18,128 10 print peek(s+27):goto 10
10 s=54272:pokes+15,100:pokes+18,128:printchr$(205.5+(peek(s+27)and1));:goto10
5 s=54272:pokes+15,100:pokes+18,128 10 print chr$(205.5+(peek(s+27)and1));:goto10
6 poke 54272+wave, noise 10 print chr$(205.5+peek(54272+osc3read));goto 10
Assembly routine (Ian)
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
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 radnom: goto 10
- 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.
We also synthesize some of the previous sections, and discuss the aesthetic qualities of the 10 PRINT pattern in terms of randomness.
Works Cited
Bennett, Deborah. 1998. Randomness. Cambridge Mass.: Harvard University Press.
Ekeland, Ivar. 1996. The Broken Dice, and Other Mathematical Tales of Chance. University of Chicago Press, June 15.
Felder, H. 1968. The GPSS/360 random number generator. In Proceedings of the second conference on Applications of simulations, 21–28.
Green Jr, B. F, J. E. Smith, and L. Klem. 1959. Empirical tests of an additive random number generator. Journal of the ACM (JACM) 6, no. 4: 527–537.
Isida, Masatugu, and Hiroji Ikeda. 1956. Random number generator. Annals of the Institute of Statistical Mathematics 8, no. 1 (12): 119-126. doi:10.1007/BF02863577. http://www.springerlink.com/content/02510157q12768k4/.
Knuth, Donald E. 1969. The Art of Computer Programming. Vol. 2. Reading, Massachusetts: Addison-Wesley.
Lord, E. A., and S. Ranganathan. 2006. Truchet tilings and their generalisations. Resonance 11, no. 6 (6): 42-50. doi:10.1007/BF02838881. http://www.springerlink.com/content/w1577r5g78rx2033/.
Neumann, John von. 1961. Various Techniques Used in Connection with Random Digits. In Collected Works: Design of Computers, Theory of Automata and Numerical Analysis, ed. A.H. Taub, 5:768-769. Oxford: Pergamon Press.
Pfeiffer, John E. 1962. The thinking machine. Lippincott.
RAND Corporation. 1955. A Million Random Digits with 100,000 Normal Deviates. http://www.rand.org/pubs/monograph_reports/MR1418/index2.html.
Rotenberg, A. 1960. A new pseudo-random number generator. Journal of the ACM (JACM) 7, no. 1: 75–77.
Smith, Cyril Stanley, and Pauline Boucher. 1987. The Tiling Patterns of Sebastien Truchet and the Topology of Structural Hierarchy. Leonardo 20, no. 4: 373-385.
