ON THE EUCLIDEAN ALGORITHM: RHYTHM WITHOUT RECURSION

Abstract

A modified form of Euclid’s algorithm has gained popularity among musical composers following Toussaint’s 2005 survey of so-called Euclidean rhythms in world music. We offer a method to easily calculate Euclid’s algorithm by hand as a modification of Bresenham’s line-drawing algorithm. Notably, this modified algorithm is a nonrecursive matrix construction, using only modular arithmetic and combinatorics. This construction does not outperform the traditional divide-with-remainder method; it is presented for combinatorial interest and ease of hand computation.

1 Introduction

In 2005, Godfried Toussaint described a method of producing musical rhythms via the Euclidean algorithm. These are called Euclidean rhythms. As commonly taught, Euclid’s algorithm calculates the greatest common divisor of two integers k and N using integer division and recursion. Toussaint’s application generates a rhythm consisting of k notes distributed over N pulses. Euclid’s algorithm most often appears in number theory, and more broadly the study of integral domains. So, it may come as a surprise that Euclid’s work has a practical application to musical composition.

There is a recurring problem of distributing k objects or events as evenly as possible in a discrete space of size N, particularly when $\gcd (k, N) = 1$ . This is a task which musicians and composers have already been approaching intuitively; the fruits of their labour may be found across many musical traditions. In rhythm theory, Toussaint’s main object of study, the problem is to distribute k notes over N pulses as evenly as possible. A second application occurs in scale theory—selecting k pitches from a set of N as evenly as possible. A more thorough investigation of these connections may be found in the work of Demaine et al. [3].

Of course, arguing for the aesthetic value of Euclidean rhythms is outside the scope of this work. However, it is worth noting that Toussaint was able to catalogue a large number of Euclidean rhythms where they already exist in music traditions across many disparate world cultures. A few examples of extant rhythms which the Euclidean algorithm reproduces include traditional rhythms from Cuba, Persia, South Africa and Turkey [9]. A broader catalogue of these rhythms featuring deeper analysis is given by Demaine et al. [3].

In the fifteen years following Toussaint’s publication, the concept of Euclidean rhythms has become popular among music theorists and composers. It is particularly popular among electronic and experimental composers; many companies now produce Euclidean rhythm generators as commercial hardware and software, or incorporate these capabilities into other multi-function products. One example is XronoMorph, a free software application which generates rhythmic and melodic loops [8]. It may be downloaded at https://www.dynamictonality.com/xronomorph.htm.

For our purposes, a binary rhythm—more succinctly a rhythm—is a finite sequence whose elements are taken from a set of two distinct symbols. The symbols are arbitrary, but assumed to be opposites; they may be taken from sets such as $\{0,1\}$ , $\{<,>\}$ or $\{\mathrm{O}{\scriptstyle\mathrm{FF}}, \mathrm{O}{\scriptstyle\mathrm{N}}\}$ . We choose the symbol set , in keeping with the context of Toussaint’s work. Each rhythm has a length, and each symbol occurring in the rhythm is either a note or a rest . Rhythms are treated cyclically; for example, is equivalent to [3, 4].

Toussaint uses Eric Bjorklund’s algorithm as the method for generating Euclidean rhythms. This algorithm originates in the theory of discrete-time control systems [2]. Bjorklund’s algorithm produces a rhythm of length N which contains k Ons spaced as evenly as possible among $(N-k)$ Offs [1]. This is achieved by recursively concatenating rhythms of shorter length according to back-substitution. At a conceptual level, Bjorklund’s algorithm resembles Euclid’s, with subsequences and symbol replacement taking the place of integer division and back-substitution [4]. These two algorithms are in fact equivalent [3].

Other applications of Euclid’s algorithm outside number theory include calculation of leap years and, in particular, Bresenham’s line drawing algorithm [7]. The latter was developed for drawing line segments on digital matrix displays. We propose a variant of Bresenham’s algorithm which constructs what we call the Euclidean array $E(k,N)$ . This array contains $\gcd (k,N)$ as a minimal element. In practical terms, $E(k,N)$ records the intermediate results of Bresenham’s subtract-and-carry loop. It is intended for ease of hand computation, using a written array in place of dynamic computer memory.

Figure 1 The Euclidean array $E(3, 7)$ . Three descents occur along the bottom row.

Figure 2 The Euclidean array $E(2, 4)$ . Its ascents and descents are marked along the bottom row.

Of course, Euclid’s algorithm has another important application beyond finding $\gcd (k, N)$ . The extended Euclidean algorithm calculates solutions to the Diophantine equation

(1.1) $$ \begin{align} ak + bN = \gcd(k, N) \end{align} $$

via back-substitution. Our nonrecursive algorithm solves (1.1) in three steps:

1. (1) construct $E(k, N)$ ;

2. (2) locate the least positive entry on the third row of $E(k, N)$ ;

3. (3) calculate a and b using the explicit formulae in Theorem 3.2.

Two methods to construct the arrays $E(k, N)$ appear in Section 2. We sketch the proof of the algorithm’s correctness in Section 3. Section 4 presents a method for determining Euclidean rhythms from $E(k,N)$ . This method involves classifying the ascents and descents of the array, as is done for integer permutations. Finally, Section 5 closes with some practical use-cases.

2 Euclidean arrays

Given $0 \leq k \leq N$ , the Euclidean array $E(k,N)$ is a $3 \times (N+1)$ array constructed as follows. Row one is the arithmetic progression $-1, 0, 1, \ldots , (N-1)$ of length $N+1$ . It is easily written down by hand. The entries of row two are each equal to k times the corresponding entry from row one. This row may be constructed either via multiplication of the entries on row one by k, or by repeated addition of k to $-k$ . The entries of row three are each equal to the corresponding entry from row two, reduced modulo N to its representative in the set $\{0, 1, \ldots , (N-1)\}$ . When calculating by hand, one can take advantage of the fact that exactly one of the numbers $(m+k)$ and $(m - (N-k))$ appear in the residue set $\{0, 1, \ldots , (N-1)\}$ if m is already such a residue.

We refer to the rows of $E(k, N)$ as the index row, integer row and residue row, respectively. An example is given in Figure 1.

Some explanation regarding this construction is necessary. We choose to start indexing at $-1$ so that the corresponding Euclidean rhythm begins with a note. Also, we deliberately avoid treating the indices cyclically. While doing so would allow the omission of one column, we consider it to be an oversimplification. Instead, we intend Euclidean arrays to be marked with the symbols $>$ and $<$ , as in Figure 2, for identifying descents during hand computation. This is further discussed in Section 4.

3 Elementary results

Consider a Euclidean array $E(k,N)$ with $0 \leq k \leq N$ . The following results are easily proven using elementary number theory.

Lemma 3.1. Given $E(k, N)$ , the least positive entry on the residue row is equal to $\gcd (k, N)$ . The greatest positive entry on the residue row is equal to $N - \gcd (k, N)$ .

Theorem 3.2. Given $E(k, N)$ , if $[a_{1}, a_{2}, a_{3}]^{T}$ is a column vector such that $a_{3} = \gcd (k,N)$ , then $a_{1} k + b N = \gcd (k, N)$ , where

$$ \begin{align*} b = \frac{a_{3} - a_{2}}{N}. \end{align*} $$

Proof. These claims are vacuously true when $k = 0, N$ , as the residue row contains no positive entries.

Consider the case $0 < k < N$ . Let $[a_{1}, a_{2}, a_{3}]^{T}$ be a column vector with $a_{3}$ minimal and positive. By construction, a ₂ ≡ a ₃ modulo N. Then

$$ \begin{align*} a_{3} - a_{2} = bN \end{align*} $$

for some $b \in \mathbb {Z}$ . By adding a ₂ = a ₁ k to this equation, we have

$$ \begin{align*} a_{3} = a_{1} k + bN. \end{align*} $$

This gives a solution to the Diaphantine equation

$$ \begin{align*} x k + y N = a_{3}, \end{align*} $$

so $\gcd (k, N) \mid a_{3}$ . By minimality of $a_{3}$ , we see that $\gcd (k, N) = a_{3}$ .

Further, $b_{3} = N - \gcd (k, N) = N - a_{3}$ occurs in the column vector $[b_{1}, b_{2}, b_{3}]^{T}$ where $b_{1} \equiv N - a_{1}$ modulo N. A standard contradiction argument shows that $b_{3}$ is a maximal element of the residue row.

Theorem 3.2 occasionally gives solutions to the Diophantine equation (1.1) that are true, but inelegant. For example, the array in Figure 1 produces the equation

$$ \begin{align*} 5 \cdot 3 - 2 \cdot 7 = 1, \end{align*} $$

rather than the more obvious

$$ \begin{align*} 1 \cdot 7 - 2 \cdot 3 = 1. \end{align*} $$

An alternative solution can sometimes overcome this blemish.

Corollary 3.3. Given $E(k, N)$ , if $[b_{1}, b_{2}, b_{3}]^{T}$ is a column vector and if $b_3$ is such that $b_{3} = N - \gcd (k,N)$ , then $aN - b_{1} k = \gcd (k, N)$ , where

$$ \begin{align*} a = 1 - \frac{b_{2} - b_{3}}{N}. \end{align*} $$

Figure 3 The reduced Euclidean array $\hat {E}(4, 6)$ .

We pause at the threshold to Section 4 to optimise our construction. To construct a reduced Euclidean array $\hat {E}(k,N)$ , proceed by completing columns, not rows. Terminate the array after the first repeated entry on the residue row, regardless of the number of columns. An example is given in Figure 3.

There is a further optimisation if one is only concerned with $\gcd (k, N)$ and not the corresponding Euclidean rhythm. The final row may be omitted. More notably, during the construction, if either of the residues $1$ or $(N-1)$ occur, as in Figure 1, then the construction may be immediately interrupted in favour of applying Lemma 3.1, as in both cases, $\gcd (k,N) = 1$ .

4 Determining Euclidean rhythms

Consider the residue row $[n_{-1}, n_{0}, \ldots , n_{N-1}]$ of a Euclidean array $E(k,N)$ . Each pair of adjacent entries $(n_{i}, n_{i+1})$ is called an ascent if $n_{i} < n_{i+1}$ , and a descent if $n_{i}> n_{i+1}$ . Ascents and descents appear in the study of permutations, notably in the definition of the Eulerian numbers [6].

We construct the Euclidean rhythm corresponding to $E(k, N)$ as follows. The ith entry of the Euclidean rhythm is if the pair $(n_{i-1}, n_{i})$ is a descent, and otherwise. The Euclidean rhythm corresponding to Figure 1 is . There is one exceptional case. The residue row of $E(N,N)$ is identical to that of $E(0,N)$ , so we define the Euclidean rhythm corresponding to $E(N, N)$ to be N notes, .

This procedure may also be performed on the reduced array $\hat {E}(k, N)$ , with the observation that Euclidean rhythms are periodic with minimal period length $N/\gcd (k,N)$ . The Euclidean rhythm corresponding to Figure 3 is .

We now prove the following lemma.

Lemma 4.1. If $0 < k < N$ , then the Euclidean rhythm corresponding to $E(k, N)$ contains exactly k notes.

Proof. Consider a line segment in the Cartesian plane with endpoints $(-1, -k)$ and $(N-1, Nk - k)$ . This segment interpolates the first two rows of the Euclidean array $E(k,N)$ , with the index row giving the x-coordinates, and the integer row giving the y-coordinates.

A descent appears on the residue row of $E(k,N)$ between columns $i-1$ and i if and only if the line segment intersects a horizontal line of the form $y = Nt$ with $t \in \mathbb {Z}$ on the x-interval $(i-1, i]$ . The line segment crosses k such lines, whose formulae are $y = 0, N, 2N, \ldots , (k-1)N$ .

We close the section with two smaller results. The first allows computation of $\gcd (k, N)$ from a Euclidean rhythm without reference to $E(k, N)$ .

Corollary 4.2. Given a Euclidean rhythm R of length N which contains k notes, $\gcd (k, N)$ is equal to the number of occurrences of the minimal period of R.

For example, the Euclidean rhythm has two occurrences of its minimal period . This demonstrates that $\gcd (6, 8) = 2$ . Our final result shows that the set of all Euclidean rhythms is invariant under the involution .

Lemma 4.3. For $0<k<N$ , constructing the rhythm corresponding to $E(k, N)$ , but instead assigning notes to ascents and rests to descents, is equivalent to constructing the rhythm corresponding to $E(N-k, N)$ via the ordinary method.

In other words, Euclidean rhythms distribute their rests in the same manner as their notes. We refer the curious reader to Bjorklund’s work for the proof of Euclidean rhythms’ equal-distribution properties [1]. Many other theoretical properties of Euclidean rhythms have been described by Gomez-Martin et al. [5].

5 Discussion

We have now explored Euclid’s algorithm outside mathematics and returned with some mementos. Namely, there is a connection between the Euclidean algorithm, musical rhythms, sequences of residues and combinatorics. We hope to entertain students of number theory and discrete mathematics at all levels.

One imagines a novice asking ‘How many times do I repeat the division step in Euclid’s algorithm?’ and not being satisfied with the response ‘About $\log N$ times, you’ll know when you’re done.’ I appreciate the definiteness of saying instead ‘Calculate N residues, then look for the smallest’, despite this being worse in terms of computational complexity. In light of the $\hat {E}(k, N)$ , ‘Maybe you’ll get lucky and finish quicker.’

Constructing Euclidean arrays by hand avoids the common pitfalls of Euclid’s algorithm—keeping track of three different sequences of integers (the quotients, divisors and remainders) and arranging them correctly during back-substitution. Perhaps the $E(k,N)$ will find a home in maths pedagogy. Further, a musical composer who wishes to apply Euclidean rhythms may find it easier to work with the array $E(k, N)$ by hand compared to Bjorklund’s algorithm under the same circumstance.

It remains an open and subjective question whether classifying descents in other integer sequences would produce musically interesting rhythms.