The other day I was listening to AT’s “Selected Ambient Works Vol. 2″ and track #2 off the first disc got me thinking. In case you’ve never heard of R.D. James (aka Aphex Twin), he is an electronic musician. Occasionally he does something nerdy and/or snarky which cracks me up. For example his 1999 single Windowlicker had several images embedded as sonograms inside the audio. Much of his music sounds meticulously edited, but occasionally there are melodies or modulation parameters or something that sound algorithmic. For fun I decided to try and ‘cover’ track #2 algorithmically with no editing. To construct the melody and modulation data I used a bit-reversal algorithm on an ascending harmonic scale.
Bit-reversal (pictured above as appiled to an 8-element array) is, as the name suggests, an operation (permutation actually) wherein you take an array of data and map each element to the unique address whose binary digits are the mirror image of those in its current address. It is a low-level primitive that comes up surprisingly often in computational harmonic analysis. The most prominent example is the FFT of course, but there are several other interesting transforms (such as the sequency ordered Walsh-Hadamard transform) that make similar use of it. Bit-reversal is plenty interesting on its own however. It can be done in-place and in O(n) time and can be profitably parallelized on SIMD architectures (such as GPU’s). To create my data I used a recursive version (written in Python):
from numpy import *
def bit_reverse_traverse(a):
n = a.shape[0]
if n == 1:
yield a[0]
else:
even_index = arange(n/2)*2
odd_index = arange(n/2)*2 + 1
for even in bit_reverse_traverse(a[even_index]):
yield even
for odd in bit_reverse_traverse(a[odd_index]):
yield odd
return
def get_bit_reversed_list(l):
n = len(l)
index = arange(n)
b = []
for i in bit_reverse_traverse(index):
b.append(l[i])
return b
The first function bit_reverse_traverse is a generator, which is a sortof functor (by which I mean function with internal state, not the category-theoretic kind) that behaves like an iterator. However instead of creating the entire array in memory and feeding it out one element at a time, generators rely on internal state (using the yield statement, which acts like a stack frame freezer) to synthesize a new element each time their next method is called. Hence they are much more efficient than normal iterators (at the cost of not being random access) and enable one to do things like bit-reverse a 65,536 element array on a laptop reasonably quickly. This generator works a bit like merge-sort: by recursively iterating over copies of itself applied to 2 sub-arrays of even and odd-numbered elements (accessible using numpy syntax a[even_index]) until the arrays are of size 1, then it just returns the element. The second function get_bit_reversed_list actually performs the bit-reversal on a list by iterating over the list using the generator and appending each array element returned by the yield statements.
One can do all sorts of interesting things with generators- usually with some kindof explicit recursion (indeed they are conceptually quite similar to basic streams in Scheme), but not always. For example you can easily phrase the Sieve of Erastosthenes algorithm for generating prime numbers as a generator:
from numpy import any
def primes():
n = 2
p = []
while True:
if not any( n % f == 0 for f in p ):
yield n
p.append( n )
n += 1
As you can see the code isn’t recursive.
Anyways, after creating some lists this way I converted them into MIDI data and played them on a sampling synthesizer. Here is the result.
Perhaps you werent aware that there is a 