Tuesday 3 January 2017

Programming Euclidean Rhythms

I heard about Euclidean rhythms a few months ago when I saw Charlie Roberts perform at the International Conference on Live Coding (where I was also playing) in Hamilton, Canada. He was live coding using Gibberwocky; an extension to the Javascript-based live coding language, Gibber, that allows you to live code a digital audio workstation. It's an amazing piece of software and I suggest you Google it after reading this. Anyway, he created a drum beat by playing a kick drum and using a function "Euclid(3, 8)" and it sounded funky so I asked him what it was. He told me it was a Euclidean rhythm and that a couple of other live coding languages, such as TidalCycles, use them as well. He told me to read a paper by Godfried Toussaint called "The Euclidean Algorithm Generates Traditional Musical Rhythms", which explained the method to create these rhythms. I really wanted to include this simple and terse means of describing rhythms in my own Live Coding environment, FoxDot, but I did not get any useful information on how to actually program the algorithm described in the paper. I put off implementing the algorithm until I had some down-time recently and felt that I should put the code on the internet for anyone else interested.

What is a Euclidean Rhythm?


The idea of a Euclidean rhythm is to divide a number of steps, k, such that a smaller number of pulses, n, in a way that separates each pulse as equally as possible. For example, if you want three pulses over eight steps (n=3, k=8) then the algorithm returns [1,0,0,1,0,0,1,0] where a 1 represents a pulse and a 0 is the absence of a pulse. These rhythms are used in a whole host of musical genres and can create some even more interesting rhythmic patterns when used together. The algorithm is described best in the original paper mentioned above but the general idea is as follows:

1. Start with a list of n ones (pulses) and k-n zeros (non-pulses). So if n=5, k=13 and your starting list is as follows:

1111100000000

2. Take the last n number of trailing zeros from the end of the list and group each one with the first n values (all ones at this point) in turn e.g.

1111100000000   ->  11111000
                    00000

3. This is repeated until non-pulses are grouped with pulses, like so:

11111000      11111
00000     ->  00000
              000

4. In this example there are now two groups smaller than the others. Let's call these "spare" columns/groups. We do as we did previously, adding the trailing columns to the leading columns until we only have 1 or 0 "spare" columns

111    1 1 1
000    0 0 0
000 -> 0 0 0 -> 1001010010100
11     1 1
00     0 0

Programming a Euclidean Rhythm


The function below is written Python and returns the Euclidean Rhythm for any value of n and k (it returns k number of ones when n > k). I hope this is of use to some people. If you think the algorithm isn't quite right (I had to do a lot of figuring it out myself) or you think it can be made more efficient - please do let me know in the comments!

def Euclid(n, k):

    data = [[1 if i < n else 0] for i in range(k)]
    
    while True:
        
        k = k - n

        if k <= 1:
            break

        elif k < n:
            n, k = k, n

        for i in range(n):
            data[i] += data[-1]
            del data[-1]
    
    return [x for y in data for x in y]