I thought I’d write up a non-technical explanation of what the Euclidean pattern generator is doing. I’ve put the topic in the Analog Rytm category because that’s the first Elektron machine to get it, but we all expect more developments. One doesn’t have to know what AR is doing precisely in order to use it to good effect, but it’s always nice to understand things. I won’t talk about the two sequences and Boolean combinations in the AR implementation, only about one sequence.
I’ll use the example of putting five trigs into a pattern of length thirteen. Euclidean patterns are “on the grid”, that is, no microtiming. It would be possible to space the trigs out exactly, but that’s a different idea. In the papers that described the algorithm, they used the word “pulses” for the trigs. It’s handy to have a concise notation, and I’ll use a 1 for a pulse and 0 for the absence of a pulse. So [1000100010001000] represents the standard four-on-the-floor beat, just as one might program it on the AR.
So, five pulses in thirteen slots, so that they are spaced out as evenly as possible while remaining on the grid. We could try to do it just by instinct. There isn’t enough space to put three empty slots between pulses, so we could try two. That gets us [1001001001001] (the square brackets are part of a more general notation I’ll describe in the next paragraph). But remember that the sequence loops (maybe wedges of a pie would be a better visualization, but I don’t want to draw diagrams), so there are two consecutive 1’s in a row. Putting only one empty slot between pulses gets us [1010101010000] and now there is that big run of four zeros. We can adjust, and get to something that looks reasonable. But how to do this systematically?
It’s helpful to think about partial sequences, which I’ll call “chunks”. [1] is a chunk, as is [001] and [10110]. The algorithm starts by putting each 1 into its own chunk, and each 0. So we have two collections of chunks. We can represent the situation like this:
[1] [1] [1] [1] [1] [0] [0] [0] [0] [0] [0] [0] [0]
What we want to do is distribute the [0] chunks evenly among the [1] chunks. We can do this by appending a [0] to each [1], resulting in five [10] chunks and three [0] chunks left over.
[10] [10] [10] [10] [10] [0] [0] [0]
Since we still have [0] chunks, we can keep going, but we don’t have enough for each [10] chunk to get another zero. What we end up with is this:
[100] [100] [100] [10] [10]
What we have here is two collections of chunks: three [100] chunks, and two [10] chunks. So we can write it like this:
[100] [100] [100] [10] [10]
We have made progress! This is a smaller problem of the same kind we started with, except we have fewer chunks and each chunk is larger. On the left, each chunk is a good distribution of one pulse into three slots; on the right, each chunk is a good distribution of one pulse into two slots. We just need to distribute the right-hand chunks among the left-hand ones.
[10010] [10010] [100]
And now there is only one chunk remaining on the right. Since our sequence is cyclic, that chunk can go anywhere. If we put it at the end of the left-hand chunks, and merge them all, we get:
[1001010010100]
This is better than our earlier intuitive attempts. The two runs of 101 are as far apart as they can get without messing up something else.
It could happen that we are left with no chunks on the right, as in the above example of four pulses into sixteen slots. We start with
[1] [1] [1] [1] [0] [0] [0] [0] [0] [0] [0] [0] [0] [0] [0] [0]
and end up with
[1000] [1000] [1000] [1000]
which gets us
[1000100010001000]
as expected.
That’s just a couple of examples, but I hope you can see how it can work in general. We maintain a left chunk, number of left chunks, right chunk, number of right chunks, and then adjust these as above, making the chunks larger and number of chunks smaller, until we have our answer.
Why is this called a Euclidean rhythm?
The example I gave above was used by Bjorklund in an internal note for Los Alamos National Laboratory in 2003. His application was not musical, but had to do with timing of intermittent components of a particle accelerator. Toussaint, a McGill mathematician and computer scientist with an interest in world music, realized in 2005 that many standard rhythms are formed by this kind of even on-grid distribution, and he was the one who called them “Euclidean”. (He also used the same example, so I have continued in the tradition.)
Euclid was a classical Greek mathematician. He is known for his study of geometry, but he also described what we now consider the first algorithm, to compute the greatest common divisor (GCD) of two numbers. The GCD of 21 and 15 is 3, because 3 divides each of them evenly, and no larger number does. Euclid’s algorithm tries to divide the larger number by the smaller one: 21 divided by 15 is 1, with remainder 6. Euclid observed that the GCD of 21 and 15 is the same as the GCD of 15 and 6. Repeating, 15 divided by 6 is 2, with remainder 3. We must compute the GCD of 6 and 3. 3 goes evenly into 6, so the GCD is 3, and that is the GCD of 21 and 15 as well.
If you do this with 5 and 13, the intermediate pairs you get will be exactly the number of chunks on left and right. Dividing the smaller number into the larger one is like distributing the chunks; the remainder is the number of chunks left over. So Euclid’s algorithm is hidden in the process of even distribution of pulses, and it makes sense to call this a Euclidean rhythm.
If you’re still reading, I hope you found this interesting.