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):
[attachments label=doctitle fields=caption,description]
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