Listen to Computer Science Algorithms

Judy Franklin
Computer Science Department
Smith College
Northampton, MA 01063
Student Collaborators: Liz Laverty, Veronica Morales, Shana Negin

Computer generated music can be useful in introductory programming courses as the theme for programming projects as well as a method for demonstrating algorithms. In particular algorithmic granular synthesis combined with computer science algorithms can generate interesting sounds and can demonstrate the algorithms.Algorithmic granular synthesis is a method in which computer algorithms manipulate small "grains" of sound. These grains can vary in duration from the shortest duration that can be distinguished by the human ear to 1 second. The techniques discussed here use grains that have a uniform duration of 0.1 seconds. Many many grains combined make up a new sound wave or a song. Grains may be separated by silence or may overlap to a small or large degree. Granular synthesis is a broad term within its narrow field of computer music in that a variety of techniques are used to achieve it. Some techniques manipulate sound in the time domain and others manipulate it in the frequency domain. At present we use time domain techniques based largely on algorithms that are used in programming projects in our introductory course for computer science majors. We have used the bubble sort, the quick sort and the binary search.

Generating Grains using Sinusoids

In order to generate grains using a sorting algorithm, a list of numbers is generated randomly. The list is typically from 1000 to 10000 numbers in length. This list is sorted. Recall that the bubble sort works by comparing two consecutive numbers in a list and swapping them if the first is larger than the second (sorting in increasing order). This causes the largest (heaviest) value to sink to the bottom of the list and the other values bubble up to the top. Once a value reaches the bottom, that part of the list is no longer sorted, but another pass is made to the remaining part of the list in the same manner. When we use the bubble sort, each time there is a swap, the index of the larger of the two numbers is recorded in a second array. So the actual values being sorted are irrelevant. It is only the index values that are important and that reflect the mechanics of the sort. After the sort, a 0.1 second long sinusoid with frequency scaled by one of these index values, is generated; one grain is generated for each index value that was stored in the second array. The grains are placed side by side to create one long sound wave that demonstrates the algorithm.

Click here to hear the result.

Quick Sort

The quick sort is another algorithm that we used to generate grains of sound in order to form a composite sound wave. Recall that the quick sort is a recursive algorithm that first finds the midpoint value of the list. Then it starts at the endpoints and moves toward the center. Whenever an element on the left is greater than the center, it is swapped with an element on the right that is less than the center in value. The result is a list that is composed of two unsorted sub-lists, but each element in the first sub-list is less than each element in the second sub-list. Quick sort is then called recursively on each sub-list. As the quick sort is sorting our randomly generated list, whenever two values are swapped, the indices of both values are stored in a second array, in a manner similar to that described above for the bubble sort.

Once again, the actual values being sorted are irrelevant. It is only the index values that are important and that reflect the mechanics of the quick sort. As before, after the sort, a 0.1 second long sinusoid with frequency scaled by an index value, is generated; one grain is generated for each index value in the second array. The grains are again placed side by side to create one long sound wave that demonstrates the algorithm.

It is possible to manipulate the grains further, such as by adding harmonics to the sinusoid, or by passing the grain through an amplitude envelope (amplitude corresponds to volume). Here is a sound wave generated by the quick sort grains. Here two levels of harmonics have been added and the grain is passed through an envelope that simply ramps up linearly with a slope of 1 and then ramps down with the same slope.

Binary Search

Once a list of values is sorted, it can be searched by the binary search. We performed the binary search and when the midpoint of each sub-list being searched was calculated, we saved this midpoint index value in a second array. These index values were then used as frequencies for sine waves as before and grains generated. This time the grains are separated by space so they are heard as "blips" with silence in between.

Listen to the grains generated by the binary search. The frequencies change quite a bit in the beginning, but at the end they are very similar, as the search narrows.

Generating Grains using Musical Recordings

Please increase your volume before listening to the following songs.

We also used the three algorithms above to choose grains of sound from digitized recordings of people playing instruments. We were able to use the resulting sound waves in our own musical compositions. One of the people recorded was a senior who pays the guitar (Shana Negin); using a recording of another student should be inspiring to first year students. We made a recording of her improvising on guitar so that the composition would be original. We use the same array of index values obtained from the binary search. This time however, these indices are used as locations in the digital sound wave that represents the recording and a sample that is 0.1 seconds in duration is taken from that location. In other words a grain is generated. These grains are placed in sequence as before with space in between.

Notice that the grains are quite distinguishable in the beginning but are difficult if not impossible to distinguish by the end. The midpoints of the binary search are so close as the search is narrowed that they are used to choose samples that are highly overlapping and start at nearly the same location in the sound wave.

Finally, a recording was also made of a flute improvisation (by the author) and the list of indices resulting from a bubble sort were used in the same way to take out granular samples of the improvisation, using each index as a location in the original sound wave. While it is difficult to see the result in a visual representation of a clip of the composed sound wave, it can be seen in Listen to the varied but repetitive structure that is a result of the bubble sort

Tthe new sound wave is complex enough to be used in a musical composition created as computer music. Indeed, it has been.

Generating Grains using a Program Compiler's Mechanics

A compiler is a large computer program that translates another program, written in a language such as C/C++ or Java, for example, into machine usable form. Compilers have to understand the syntax of the computer language that they are translating, and check to see that programs follow the syntax by doing a syntactic analysis. For example, language features such as loops or an if-then-else statement can be used as long as the programmer follows a very particular form. Computer languages also have semantic rules that require certain language forms to be embedded in a certain context. For example, some operators require both numbers they use to be the same type; perhaps both numbers need to be integers. Some languages require that every identifier, such as the name of a variable, must be declared in the program and the type of value that may be stored in that variable must be stated. Therefore, the compiler must also perform a semantic analysis of the program. After all of this checking is done, and some translation has taken place, the compiler must then complete the translation, into the form required by the target machine (platform) on which the program is to be run, or executed [Watt and Brown 2000]. Generally the form that is usable by the machine (the executable machine code) is at a monumentally lower level than the original language. The third part, or pass, is called code generation.

We are using an educational compiler that makes one pass through the program it is compiling for each of the three steps described above (also written by [Watt and Brown 2000]) and shown in Figure 5. The compiler is written in the Java programming language, an object-oriented language that, when used with good software-engineering practices, results in a large group of small subprogram modules called methods. We simply associate a number with each of the methods in the compiler program. When the compiler, a program itself, is run in order to compile some program (in this case in an educational language called Triangle), many of these methods are called and run, and their associated numbers are recorded in a file. A different set of numbers will be recorded for each different user program that is compiled. Various schemes could be used to choose the numbers. We simply use the method name. For example, "ParseIdentifier" has associated with it the number 9 (I is the 9th letter in the alphabet). ParseSingleCommand is 193: 19 for the S, and 3 for the C. There are many method names that start with the word "Parse" because the syntactic analyzer is also called the parser. So we ignored the "P" and used the rest of the method. A separate program, written in RTcmix, converts these numbers into frequencies to be used with a software oscillator to generate a pitch. Here is the result (Caution, large 8MB wav file)
We have also experimented with using the same values as parameters to filters to that manipulate samples from the Triangle song.
Here is a sample (this one is a 3MB wav file)

Watt, D. A. and Brown, D. F. 2000. Programming Language Processors in JAVA, Prentice-Hall (Pearson Education), Harlow England.