Generating african rhythms using the euclidean algorithm
Generating african rhythms using the euclidean algorithm24.10.2008 12:55:43
Last week, I stumbled upon the amazing paper by Godfried Toussaint called The Euclidean Algorithm Generates Traditional Musical Rhythms, which shows how the euclidean algorithm used for example for timing systems in neutron accelerators can generate most of the traditional european and african rhythms. It is about distributing a set amount of pulses (which Godfried calls n) over a discrete amount of timing intervals (called k). The goal is to distribute these pulses most equidistantly, for example, 3 over 8 would give the pattern X . . X . . X . (with X being a pulse, and . being none). Those of you listening to ragga or rocknroll or playing djembe will recognize that rhythm immediately, it is called the "tresillo" and is used in almost every dance music :) It sounds like this (using Ableton simpler, I added a bassdrum for the standard techno pulse).
You can do the same with for example distributing 5 over 8, giving X . X X . X X . It sounds like this:
You can then go over to more complicated rhythms, for example distributing 6 over 9, and using different sounds for it, which creates the following pattern:
The thing I really enjoy about these patterns is that they sound very "natural" due to being equidistant (the paper gives more mathematical explanations about that), but having them interact creates very complex shifting grooves, which joins my "theories" about techno and how to create friction (reading james butler's book "Unlocking the groove" is very interesting as well). I haven't done much research into using this way of creating patterns in my techno yet, but I'm very very excited about all the possibilities, and will post a MachineDrum Notes #2 showing what I have discovered. In the next few paragraphs, I am going to show how I implemented the algorithm described in Godfried's paper in Lisp and played with it. It is very easy to go through the algorithm by hand, and Godfried shows a very simple way to execute it on paper, so you don't need a computer to do it.
I represent rhythms in Lisp using a list of numbers, with "1" representing a pulse and "0" representing a pause. So for example the son clave, the bembe rhythm and the shiko rhythms are represented by:
(defparameter *clave-son* '(1 0 0 1 0 0 1 0 0 0 1 0 1 0 0 0)) (defparameter *bembe* '(1 0 1 0 1 1 0 1 0 1 0 1)) (defparameter *shiko* '(1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0))
The way the algorithm works is to first create a list with all the pulse at the front, and all the pauses at the end. So the first step of generating the (3, 8) rhythm (3 pulse for 8 timing intervals) is to create the following list: ((1) (1) (1) (0) (0) (0) (0) (0)) . Then the 0s at the end are distributed to behind the ones to give the list : ((1 0) (1 0) (1 0) (0) (0)) . In the next iteration, the remainder (the 0s at the end are again distributed to the end of the first elements to give the list: ((1 0 0) (1 0 0) (1 0)) . At this point, no further processing is required because the remainder (1 0) has the length 1. This is the same procedure as computing the greatest common divisor of two numbers by using the euclidean algorithm, except that instead of using subtraction and working on numbers, we use lists and concatenation.
The first routine we need is a routine to computer the remainder of a list of pulses. The code is quite hackish, but it works :) It looks at the last element of the list, and collects all that are equal to it into the remainder (so if the last element is (0), it is going to collect all the (0) into the remainder and other elements into the denominator):
(defun seq-split-remainder (seq)
(let* ((last (first (last seq)))
(remainders (remove-if-not #'(lambda (x) (equal x last)) seq))
(real (remove-if #'(lambda (x) (equal x last)) seq)))
(if (= (length remainders) (length seq))
(values seq nil)
(values real remainders))))
CL-USER> (SEQ-SPLIT-REMAINDER '((1) (1) (1) (0) (0) (0) (0) (0)))
((1) (1) (1))
((0) (0) (0) (0) (0))
CL-USER> (SEQ-SPLIT-REMAINDER '((1 0 0) (1 0 0) (1 0)))
((1 0 0) (1 0 0))
((1 0))
The next function we need is the distribution function which interleaves the remainder into the denominator (what would be subtraction in the numerical euclidean algorithm). Again the code is quite hackish :) We iterate over both denominator and remainder, and concatenate them together. What is left over is just added at the end. I used the DO construct in Lisp which I find a bit hard to read, and there is probably a neater way to do it. But this is exploratory programming :)
(defun interleave-seqs (list1 list2)
(let ((res))
(do ((l1 list1 (cdr l1))
(l2 list2 (cdr l2)))
((and (null l1)
(null l2))
(nreverse res))
(let ((e1 (car l1))
(e2 (car l2)))
(push (append e1 e2) res)))))
CL-USER> (INTERLEAVE-SEQS '((1) (1) (1))' ((0) (0) (0) (0) (0)))
((1 0) (1 0) (1 0) (0) (0))
Finally the last step is just to build the iteration until the remainder is empty or of length 1, and I did by using standard recursion, like you would program it in scheme. The algorithm is called bjorklund because it was devised by Bjorklund for the timing generation in neutron accelerators (doesn't that sound like crazy rocket science??). I added a helper function so I would be able to just input n and k to create a rhythm.
(defun bjorklund (list)
(multiple-value-bind (real remainder) (seq-split-remainder list)
(if (<= (length remainder) 1)
(return-from bjorklund (apply #'append (append real remainder)))
(bjorklund (interleave-seqs real remainder)))))
(defun euclidian-rhythm (k n)
(bjorklund (append (make-list k :initial-element '(1))
(make-list (- n k) :initial-element '(0)))))
We can now finally create our tresillo pattern (I added tracing on intermediary functions so you can see how the algorithm works).
CL-USER> (euclidian-rhythm 3 8)
0: (BJORKLUND ((1) (1) (1) (0) (0) (0) (0) (0)))
1: (SEQ-SPLIT-REMAINDER ((1) (1) (1) (0) (0) (0) (0) (0)))
1: SEQ-SPLIT-REMAINDER returned ((1) (1) (1)) ((0) (0) (0) (0) (0))
1: (INTERLEAVE-SEQS ((1) (1) (1)) ((0) (0) (0) (0) (0)))
1: INTERLEAVE-SEQS returned ((1 0) (1 0) (1 0) (0) (0))
1: (BJORKLUND ((1 0) (1 0) (1 0) (0) (0)))
2: (SEQ-SPLIT-REMAINDER ((1 0) (1 0) (1 0) (0) (0)))
2: SEQ-SPLIT-REMAINDER returned ((1 0) (1 0) (1 0)) ((0) (0))
2: (INTERLEAVE-SEQS ((1 0) (1 0) (1 0)) ((0) (0)))
2: INTERLEAVE-SEQS returned ((1 0 0) (1 0 0) (1 0))
2: (BJORKLUND ((1 0 0) (1 0 0) (1 0)))
3: (SEQ-SPLIT-REMAINDER ((1 0 0) (1 0 0) (1 0)))
3: SEQ-SPLIT-REMAINDER returned ((1 0 0) (1 0 0)) ((1 0))
2: BJORKLUND returned (1 0 0 1 0 0 1 0)
1: BJORKLUND returned (1 0 0 1 0 0 1 0)
0: BJORKLUND returned (1 0 0 1 0 0 1 0)
(1 0 0 1 0 0 1 0)
This is a really really really interesting approach to rhythm creation, because it formulates mathematically what I had been doing intuitively on the machinedrum, and it is going something I'm going to do much research in. Hope you had fun and that this will inspire you as well!
