During my research for my thesis on Algorithmically Generated Tonal Music, I was fortunate to run across the research from McGill University, called “The Euclidean Algorithm Generates Traditional Musical Rhythms“, that uses a modified version of the Euclidean Algorithm called the Bjorklund algorithm. The Euclidean Algorithm is one of the oldest algorithms in existence and was proposed by Euclid in his “Elements” Books VII and X. This algorithm is used to find the Greatest Common Divisor of two numbers.
The Euclidean Algorithm is relatively simple to program. Below is an implementation of the Euclidean Algorithm in Java.
public int Euclid(int m, int k) { if(k==0) return m; else return this.Euclid(k, m%k); } |
The Bjorklund algorithm uses a similar concept to the Euclidean algorithm, but is used to distribute the zeros in a binary set evenly. The simplest, visual way of thinking about the Bjorklund can be described as thinking of a binary set as columns. The example below shows a Euclidean set of (4, 6) which we can describe as four 1s and six 0s. We therefore can create the initial binary set of “1111000000″. From here we choose the smallest of the two numbers and move that number of zeros at the end of the set to the first 1 to n columns. We update the numbers using the Euclidean Algorithm and continue this step until we are left with 0 or 1 column left, then we concatenate the remaining columns into a new set. A visual example of the (4,6) version of the Bjorklund algorithm is found below.
1111000000 111100 0000 1111 0000 00 11 00 00 11 00 1001010010
This algorithm was originally used with the operation of the components on the spallation neutron source (SNS) accelerators in nuclear physics. However, if we say that every one is associated with an accented note and the zeroes are unaccented, or rests, we can use this to generate the general rhythms and various world music rhythms. For this reason, the Bjorklund algorithm is a unique and powerful algorithm in any music generator. Below is an example Bjorklund algorithm implemented in Java (Special Thanks to Douglas Ferguson for catching some issues in the code and helping to resolve those issues):
- Caption : Generating Rhythms: Bjorklund
Description : Java Implementation of the Bjorklund Algorithm for generating Rhythms
import java.util.*; public class Bjorklund { private ArrayList<Boolean> rhythm = new ArrayList<Boolean>(); int pauses, per_pulse, remainder, steps, pulses, noskip, skipXTime; boolean switcher; public Bjorklund(int pulses, int steps) { this.steps = steps; this.pulses = pulses; this.pauses = steps - pulses; this.switcher = false; if (this.pulses > this.pauses) { this.switcher = true; // XOR swap pauses and pulses this.pauses ^= this.pulses; this.pulses ^= this.pauses; this.pauses ^= this.pulses; } this.per_pulse = (int) Math.floor(this.pauses / this.pulses); this.remainder = this.pauses % this.pulses; this.noskip = (this.remainder == 0) ? 0 : (int) Math.floor(this.pulses / this.remainder); this.skipXTime = (this.noskip == 0) ? 0 : (int)Math.floor((this.pulses - this.remainder)/this.noskip); this.buildRhythm(); if(this.switcher) { // XOR swap pauses and pulses this.pauses ^= this.pulses; this.pulses ^= this.pauses; this.pauses ^= this.pulses; } } public Bjorklund(int pulses, int steps, String expected) { this(pulses, steps); autorotate(expected); } private void buildRhythm() { int count = 0; int skipper = 0; for (int i = 1; i <= this.steps; i++) { if (count == 0) { this.rhythm.add(!this.switcher); count = this.per_pulse; if (this.remainder > 0 && skipper == 0) { count++; this.remainder--; skipper = (this.skipXTime > 0) ? this.noskip : 0; this.skipXTime--; } else { skipper--; } } else { this.rhythm.add(this.switcher); count--; } } } public ArrayList<Boolean> getRhythm() { return this.rhythm; } public int getRhythmSize() { return this.rhythm.size(); } public void autorotate(String expected) { boolean verified = false; int size = this.rhythm.size(); int rotate = 1; this.rotateRightByPulses(0); String found = this.getRhythmString(); while(!found.equals(expected) || rotate < this.pulses) { this.rotateRightByPulses(1); found = this.getRhythmString(); if(found.equals(expected)){ verified = true; break; } } if(!verified) { System.err.println("Rhythmic string passed cannot be generated from E("+this.pulses+","+this.steps+")"); } } public void rotateRightByBits(int numBits) { Collections.rotate(this.rhythm, numBits); } public void rotateRightByPulses(int numPulses) { for (int i = 0; i < numPulses; i++) { int rotater = this.rhythm.size() - 1; int count = 1; while (this.rhythm.get(rotater) == false) { rotater--; count++; } this.rotateRightByBits(count); } } private String getRhythmString(){ Iterator<Boolean> iterator = this.rhythm.iterator(); StringBuffer buffer = new StringBuffer(); while(iterator.hasNext()){ buffer.append(iterator.next() ? "x" : "."); if(iterator.hasNext()){ buffer.append(" "); } } return buffer.toString(); } private void print() { System.out.println(this.pulses + ":" + this.steps +" -> "); System.out.print(this.getRhythmString()); System.out.println(); } public void autoverify(String expected) { boolean verified = false; int size = this.rhythm.size(); int rotate = 1; this.rotateRightByBits(0); String found = this.getRhythmString(); while(!found.equals(expected) || rotate < size) { this.rotateRightByBits(1); found = this.getRhythmString(); if(found.equals(expected)){ System.out.println("E("+this.pulses+","+this.steps+") verified for <<" + found + ">> by rotating bits right "+rotate+" times"); verified = true; break; } rotate++; } if(verified == false) { System.err.println("missed E("+this.pulses+","+this.steps+") expected: <<"+ expected + ">> but found: <<"+found+">>"); } } } |
An example of how to call this class:
import java.util.*; public class test { public static void main(String[] args) { Bjorklund b = new Bjorklund(5,9); b.rotateRightByPulses(1); ArrayList r = b.getRhythm(); System.out.println(Arrays.toString(r.toArray())); } } |
Pingback: Euclidean rhythms
THANKS, It was interesting, but didnt give me much info relating the formulas to rythm generation.
I do alot of tonal music maths research, I would have been interested to hear how you mathematically relate different bars of melody, tonal rules for melody, ways for making them into seperate melodic components similar to how the mind actually thinks.
the code was complicated, there was no example of variations upon rythmic themes, and rules for keeping variations related.
cheers!
This post was strictly related to rhythms, and I didn’t go into melodic applications because it was outside of the scope of the discussion for the post. However, It could be extended using genetic algorithms to give rhythmic variations by measuring similarity through use of Hamming Distances. This would be a very blackbox method but would give a metaheuristic approach for solving that problem.
Melodies are trickier as there’s a lot that can go into a melody. First you have to have an understanding of the underlying chord progression, which I have done a little research on using Markov Decision Processes and Bayesian Networks. That research of course lacked any temporal aspects and one would have to create a decision process to take time into consideration. With that though, one could approach the melody as a bitonic sort of random musical pitches with a probability of mutation (again it would be a sort of metaheuristic approach). One might be able to find a way to tie Markov Decision Processes to the melody as well, which would make the melody less random.
None of this would of course guarantee that your music would come out pretty, but you would get a quasi-random tonal composition.