Ive just finished reading Godfried Toussaint’s excellent paper ‘The Euclidean Algorithm Generates Traditional Musical Rhythms’. As the title suggests, Toussaint explores the applications of Euclid’s famous algorithm for computing the GCD of two integers to algorithmic rhythm generation. It turns out that if you take a templated version of the algorithm and apply it to list types in place of integers with a certain mix operation in place of subtraction, and you feed it lists of the type [1,1,1.....,0,0....,0], you get a procedure that tries to distribute the zeros amongst the ones with maximal uniformity. For example, applying the procedure to the list [1,1,1,1,0,0,0,0] returns [1, 0, 1, 0, 1, 0, 1, 0] as you might expect. Things get more interesting when you introduce some non-uniformity however. Applying it to [1,1,1,0,0,0,0,0] returns [1, 0, 0, 1, 0, 1, 0, 0], a common clave known as tresillo.
The procedure I’ve just described was first applied to pulse timing in spallation neutron source (SNS) accelerators by Eric Bjorklund, but the basic premise of trying to spread stuff out as much as possible subject to certain constraints pops up everywhere in mathematics, from the distribution of zeros of the zeta function to the eigenvalues of a Gaussian ensemble (the two are actually related, a fact famously discovered in the cafeteria of the Institute for Advanced Study) to Ornstein-Uhlenbeck processes (O-U processes, incidentally, are the continuous-time version of what you get when you feed pure white noise into a certain kind of IIR filter). Not to mention various elementary physics phenomena such as the diffusion equation and magnetism. This stuff is still an active area of research in mathematics. If youre interested I suggest checking out Terry Tao’s blog on the subject for starters.
Anyways, this is incredible and I could go on and on about it, but its much more fun to just implement Bjorklund and start messing around. I find scripting languages in general and Python in particular to be a good tool for this sort of thing. The remainder of the post is a sortof walk-through of my python code, so fire up your Python interpreter and read on.
For reference, here is a subtractive version of the EA:
def gcd(a,b):
if a==0: return b
while b!=0:
if a>b: a = a-b
else: b = b-a
return a
To morph EA land into Bjorklund we need a analogs of the integers a and b, >, and -. In Bjorklund a and b are lists and are at times glued together into one list. So we need a way of splitting a list into two components a and b. The split works by separating out the largest homogeneous chuck of the tail of the list. I did this in a tail recursive style:
def split(a,b=[]):
b.insert(0,a.pop())
if not a or b[0] != a[-1]: return a,b
else: return split(a,b)
So for example in my python interpreter:
In [64]: a = [[1],[1],[1],[0],[0],[0],[0],[0]]
In [65]: split(a)
Out[65]: ([[1], [1], [1]], [[0], [0], [0], [0], [0]])
In [66]: a = [[1, 0], [1, 0], [1, 0], [1, 0]]
In [67]: split(a)
Out[67]: ([], [[1, 0], [1, 0], [1, 0], [1, 0]])
In the latter case the entire list is homogeneous so split returns an empty list and the original list. This will be our base case (ie the Bjorklund version of b==0).
The analog of subtraction is mix.
def mix(a,b):
m = min(len(a),len(b))
if len(a) > m:
return [a[i]+b[i] for i in range(m)] + a[m:]
else:
return [a[i]+b[i] for i in range(m)] + b[m:]
Mix takes two lists and concatenates them element-wise, then concatenates the result with whatever is left over. For example:
In [72]: a = [[1],[1],[1],[0],[0],[0],[0],[0]]
In [73]: b = [[1],[1],[1],[1],[1],[0],[0]]
In [74]: mix(a,b)
Out[74]: [[1, 1], [1, 1], [1, 1], [0, 1], [0, 1], [0, 0], [0, 0], [0]]
Now the morphed EA looks like this:
def foo(a):
x,y = split(a)
while len(x) != 1 and len(x) != 0:
x,y = split(mix(x,y))
return [x,y]
One final primitive we need is a function to flatten out the result:
def flatten(x):
result = []
for el in x:
if hasattr(el, "__iter__") and not isinstance(el, basestring):
result.extend(flatten(el))
else:
result.append(el)
return result
Finally, the Bjorklund algorithm can be written succintly as:
def bjorklund(a):
return flatten(foo(a))
So for example to create a tresillo clave and its ‘mirror image’:
In [78]: a = [[1],[1],[1],[0],[0],[0],[0],[0]]
In [79]: bjorklund(a)
Out[79]: [1, 0, 0, 1, 0, 1, 0, 0]
In [80]: b = [[1],[1],[1],[1],[1],[0],[0],[0]]
In [81]: bjorklund(b)
Out[81]: [1, 0, 1, 1, 0, 1, 0, 1]
Of course this is just the tip of the iceberg. As a white rabbit, observe that the operator is contravariant (i.e. bjorklund(a+b) = bjorklund(b) + bjorklund(a) where + here denotes list concatenation):
In [82]: a = [[1],[1],[1],[0],[0],[0],[0],[0]]
In [83]: b = [[1],[1],[1],[1],[1],[0],[0],[0]]
In [84]: bjorklund(a+b)
Out[84]: [1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1]
Addendum: If Python isnt your thing, there are a few other implementations of Bjorklund out there in Ruby and Lisp.