Tresillo (Part 3)

In maths the Greatest Common Divisor (GCD) of two numbers A and B is the largest integer that divides both A and B. The ancient Greek mathematician Euclid who lived ca 300 BC published an algorithm in his world famous work The Elements which is a technique for finding the GCD quickly. It is one of the oldest non-trivial algorithms that are still in use today and is based on the fact that the GCD of two numbers remains the same after the larger number is replaced by its difference with the smaller number. The algorithm is called Euclidean algorithm or Euclid's algorithm even though it is believed that it was actually invented centuries before Euclid put it in his collection of books on mathematical and geometrical treatise.

The formal definition of the algorithm is as follows for two positive integers x and y:

          (1) z = x mod y
          (2) if z = 0 return y 
          (3) if z ≠ 0 set x = y and set y = z then repeat from step 1

You may wonder what this has to do with music and Cuban salsa specifically. The answer lies in a discovery that Godfried Toussaint made in 2014 which he called Euclidean Rhythms. To illustrate this beautiful example of how maths relates to music let us consider an example of where we are trying to find the GCD of 8 and 5 which can be done using Euclid’s algorithm as per the following steps:

          (1) x = 8, y = 5
          (2) z = 8 mod 5 = 3
          (3) z ≠ 0 ∴ x = 5, y = 3
          (4) z = 5 mod 3 = 2
          (5) z ≠ 0 ∴ x = 3, y = 2
          (6) z = 3 mod 2 = 1
          (7) z ≠ 0 ∴ x = 2, y = 1
          (8) z = 2 mod 1 = 0
          (9) z = 0 ∴ GCD = 1

This algorithm shows that the GCD between 8 and 5 is 1 which is a rather simple example of the algorithm in practice and not very interesting mathematically. However, when we consider each step the algorithm takes (numbered 1 to 9 in the example above) we can see some surprising similarities to the problem of trying to distribute 3 onsets as evenly as possible across an 8 pulse structure. More on this to follow in the next post of the Tresillo blog series.