kReese.net

Generating Musical Rhythms

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:

import java.util.*;
 
public class Rhythm
{
    private Vector<Boolean> rhythm = new Vector<Boolean>();
    private Vector<Integer> colSizes = new Vector<Integer>();
 
    public Rhythm(int accented, int total)
    {
        boolean bool = true;
        for(int i=0;i<total;i++)
        {
            if(i>=accented) bool = false;
            this.rhythm.addElement(bool);
            this.colSizes.addElement(1);
        }
 
        this.Bjorklund(total, accented);
    }
 
    public int Bjorklund(int m, int k)
    {
 
        if(k==0)
            return m;
        else if(k==1)
            return this.Bjorklund(k, m%k);
        else
        {
            int location=0;
            int searcher = (m-k < k) ? m-k: k;
 
            for(int i=0;i<searcher;i++)
            {
                int newColSize = this.colSizes.elementAt(i) + this.colSizes.lastElement();
                int oldLastSize = this.colSizes.lastElement();
                location += newColSize;
                this.colSizes.remove(i);
                this.colSizes.remove(this.colSizes.size()-1);
                this.colSizes.insertElementAt(newColSize, i);
 
                for(int j=0;j < oldLastSize;j++)
                {
                    this.rhythm.insertElementAt(this.rhythm.lastElement(), location-oldLastSize);
                    this.rhythm.remove(this.rhythm.size()-1);
                }
            }
            return this.Bjorklund(k, m%k);
        }
    }
 
    public Vector<Boolean> getRhythm()
    {
        return this.rhythm;
    }
}