Euclidean rhythm

Last updated August 10, 2024

The Euclidean rhythm in music was discovered by Godfried Toussaint in 2004 and is described in a 2005 paper "The Euclidean Algorithm Generates Traditional Musical Rhythms".^[1] The greatest common divisor of two numbers is used rhythmically giving the number of beats and silences, generating almost all of the most important world music rhythms,^[2] except some Indian talas.^[3] The beats in the resulting rhythms are as equidistant as possible; the same results can be obtained from the Bresenham algorithm.

Summary of algorithm

In Toussaint's paper^[3] the task of distributing $k$ beats within $n$ time steps is considered. It is given that $k<n$ , so there are fewer beats than steps. The question arises of how to distribute these beats such that they are as equidistant as possible. This is easy when $n$ is divisible by $k$ —in this case we distribute the beats such that they are $n/k$ steps away from their neighbour. As an example, below is a euclidean rhythm for $n=16$ and $k=4$ . These beats are 4 steps away from each other because $n/k=16/4=4$ .

[ x . . . x . . . x . . . x . . . ]

Here "x" represents a beat and "." represents a silence.

The problem becomes more complicated when $k$ does not divide $n$ . In this case the formula $n/k$ doesn't produce an integer, so some beats must be slightly closer to one neighbour than the other. Because of this the beats are no longer perfectly equidistant. As an example, take the case when $n=13$ and $k=5$ . A naive algorithm may place the beats like this:

[ x . x . x . . x . . x . . ]

Although the beats are technically distributed with ideal spacing between the beats—they are either two steps apart or three—we still have a problem where the beats are "clumped" at the start and spaced out at the end. A more concrete definition of "equidistant" might ask that these spacings ("x ." and "x . .") are also distributed evenly.

Toussaint's observation is that Euclid's algorithm can be used to systematically find a solution for any $k$ and $n$ that minimizes "clumping". Taking the previous example where $n=13$ and $k=5$ we perform Euclid's algorithm:

{\begin{aligned}&&n=13,\ k=5\\n&=q_{0}k+r_{0}\implies &q_{0}=2,\ r_{0}=3\\k&=q_{1}r_{0}+r_{1}\implies &q_{1}=1,\ r_{1}=2\\r_{0}&=q_{2}r_{1}+r_{2}\implies &q_{2}=1,\ r_{2}=1\\r_{1}&=q_{3}r_{2}+r_{3}\implies &q_{3}=2,\ r_{3}=0\\\end{aligned}}

Toussaint's algorithm first constructs the following rhythm.

[ x x x x x . . . . . . . . ]

Then, using the sequence $t=k,r_{0},r_{1},r_{2},...$ we iteratively take $t_{n}$ columns off the right of the sequence and place them at the bottom. Starting with $t_{0}=k=5$ , we get

[ x x x x x . . .   . . . . .       ]

Next is $t_{1}=r_{0}=3$ :

[ x x x x x   . . . . .   . . .     ]

Next is $t_{2}=r_{1}=2$ :

[ x x x   . . .   . . .   x x   . .   ]

The process stops here because $t_{3}<2$ , i.e. there is only one column to move. The final beat pattern is read out from top to bottom, left to right:

[ x . . x . x . . x . x . . ]

Other uses of Euclid's algorithm in music

In the 17th century Conrad Henfling writing to Leibniz about music theory and the tuning of musical instruments makes use of the Euclidean algorithm in his reasoning.^[4] Viggo Brun ^[5] investigated the use of Euclidean Algorithm in terms of constructing scales up to 4 different size intervals. Erv Wilson explored both using^[6] ratios and^[7] scale steps of which Kraig Grady applied to^[8] rhythms within long meters.

Related Research Articles

In mathematics, Bézout's identity, named after Étienne Bézout who proved it for polynomials, is the following theorem:

In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime.

In mathematics, more specifically in ring theory, a Euclidean domain is an integral domain that can be endowed with a Euclidean function which allows a suitable generalization of the Euclidean division of integers. This generalized Euclidean algorithm can be put to many of the same uses as Euclid's original algorithm in the ring of integers: in any Euclidean domain, one can apply the Euclidean algorithm to compute the greatest common divisor of any two elements. In particular, the greatest common divisor of any two elements exists and can be written as a linear combination of them. Also every ideal in a Euclidean domain is principal, which implies a suitable generalization of the fundamental theorem of arithmetic: every Euclidean domain is a unique factorization domain.

In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers (numbers), the largest number that divides them both without a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in his Elements . It is an example of an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules, and is one of the oldest algorithms in common use. It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic and cryptographic calculations.

In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers $x$ , $y$ , the greatest common divisor of $x$ and $y$ is denoted $. For example, the GCD of 8 and 12 is 4, that is, gcd(8, 12) = 4 .$

Reed–Solomon codes are a group of error-correcting codes that were introduced by Irving S. Reed and Gustave Solomon in 1960. They have many applications, including consumer technologies such as MiniDiscs, CDs, DVDs, Blu-ray discs, QR codes, Data Matrix, data transmission technologies such as DSL and WiMAX, broadcast systems such as satellite communications, DVB and ATSC, and storage systems such as RAID 6.

In number theory, a Gaussian integer is a complex number whose real and imaginary parts are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as $or$

In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest common divisor (gcd) of integers a and b, also the coefficients of Bézout's identity, which are integers x and y such that

Euclidean is an adjective derived from the name of Euclid, an ancient Greek mathematician. It is the name of:

In mathematics, a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. It can be classified also as a tessellation. In the simplest case, these objects are just finitely many points in the plane. For each seed there is a corresponding region, called a Voronoi cell, consisting of all points of the plane closer to that seed than to any other. The Voronoi diagram of a set of points is dual to that set's Delaunay triangulation.

In mathematics, the conformal group of an inner product space is the group of transformations from the space to itself that preserve angles. More formally, it is the group of transformations that preserve the conformal geometry of the space.

In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring formed from the set of polynomials in one or more indeterminates with coefficients in another ring, often a field.

In geometry, parallel lines are coplanar infinite straight lines that do not intersect at any point. Parallel planes are planes in the same three-dimensional space that never meet. Parallel curves are curves that do not touch each other or intersect and keep a fixed minimum distance. In three-dimensional Euclidean space, a line and a plane that do not share a point are also said to be parallel. However, two noncoplanar lines are called skew lines. Line segments and Euclidean vectors are parallel if they have the same direction.

In arithmetic, Euclidean division – or division with remainder – is the process of dividing one integer by another, in a way that produces an integer quotient and a natural number remainder strictly smaller than the absolute value of the divisor. A fundamental property is that the quotient and the remainder exist and are unique, under some conditions. Because of this uniqueness, Euclidean division is often considered without referring to any method of computation, and without explicitly computing the quotient and the remainder. The methods of computation are called integer division algorithms, the best known of which being long division.

A division algorithm is an algorithm which, given two integers N and D, computes their quotient and/or remainder, the result of Euclidean division. Some are applied by hand, while others are employed by digital circuit designs and software.

In mathematical optimization, the ellipsoid method is an iterative method for minimizing convex functions over convex sets. The ellipsoid method generates a sequence of ellipsoids whose volume uniformly decreases at every step, thus enclosing a minimizer of a convex function.

In algebra, the greatest common divisor of two polynomials is a polynomial, of the highest possible degree, that is a factor of both the two original polynomials. This concept is analogous to the greatest common divisor of two integers.

In algebra, the content of a nonzero polynomial with integer coefficients is the greatest common divisor of its coefficients. The primitive part of such a polynomial is the quotient of the polynomial by its content. Thus a polynomial is the product of its primitive part and its content, and this factorization is unique up to the multiplication of the content by a unit of the ring of the coefficients.

In computational geometry, the relative neighborhood graph (RNG) is an undirected graph defined on a set of points in the Euclidean plane by connecting two points $and by an edge whenever there does not exist a third point that is closer to both and than they are to each other. This graph was proposed by Godfried Toussaint in 1980 as a way of defining a structure from a set of points that would match human perceptions of the shape of the set.$

References

↑ The Euclidean algorithm generates traditional musical rhythms by G. T. Toussaint, Proceedings of BRIDGES: Mathematical Connections in Art, Music, and Science, Banff, Alberta, Canada, July 31 to August 3, 2005, pp. 47–56.
↑ Comparative Musicology – Musical Rhythm and Mathematics
1 2 The Euclidean Algorithm Generates Traditional Musical Rhythms, by Godfried Toussaint, Extended version of the paper that appeared in the Proceedings of BRIDGES: Mathematical Connections in Art, Music and Science, Banff, Alberta, Canada, July 31–August 3, 2005, pp. 47–56.
↑ Musical pitch and Euclid's algorithm
↑ https://anaphoria.com/brun-euclideanalgo.pdf Euclidean Algorithms and Musical Theory
↑ https://anaphoria.com/viggo3.pdf A sequence of Constant Structures
↑ https://anaphoria.com/viggo2.pdf Viggo's Brun's algorithm applied
↑ https://anaphoria.com/ViggoRhythm.pdf Applying Viggo Brun's Algorithm to Rhythm

External links

G. T. Toussaint, The Euclidean algorithm generates traditional musical rhythms, Proceedings of BRIDGES: Mathematical Connections in Art, Music, and Science, Banff, Alberta, Canada, July 31 to August 3, 2005, pp. 47–56.
Phil Baljeu and Manuel Odendahl (Ruin & Wesen). "Generating African rhythms using the euclidean algorithm". Archived from the original on 2013-11-14.
Benjamin Wardhaugh (1 September 2006). "Music and Euclid's algorithm".
Links to videos about and a Flash app for experimenting with Euclidean rhythms
Euclidean rhythm demo — interactive browser-based tool for experimenting with Euclidean rhythms
A tutorial on The Euclidean Algorithm Generates Traditional Musical Rhythms by Derek Rivait
SoundHelix is a free software for algorithmic random music composition that supports Euclidean rhythms
Euclidian rhythms list - a list of all Euclidian rhythms E(i,2 to 32), indicating if they are Winograd-deep, Erdős-deep, Authentic Aksak, Quasi-Aksak or Pseudo-Aksak
XiiixxiQ : Roundels is a unique, and free, Euclidean sequencer that employs summed on the subject of Euclidian algorithm it is often stated that its functions to find the most equal divisions of a cycle, yet i cannot find that in any of the historical papers on he subject. it seems to be nothing more how a certain number of intervals divide a cycle. It is unclear where this modern assumption come from. rhythms to drive a non-linear step sequencer
https://anaphoria.com/journal.html#rhythm Papers of Kraig Grady on Brun's Euclidian Algorithm and related MOS patterns applied to rhythm.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[gtpdf-1] The Euclidean algorithm generates traditional musical rhythms by G. T. Toussaint, Proceedings of BRIDGES: Mathematical Connections in Art, Music, and Science, Banff, Alberta, Canada, July 31 to August 3, 2005, pp. 47–56.

[gtweb-2] Comparative Musicology – Musical Rhythm and Mathematics

[extv-3] 1 2 The Euclidean Algorithm Generates Traditional Musical Rhythms, by Godfried Toussaint, Extended version of the paper that appeared in the Proceedings of BRIDGES: Mathematical Connections in Art, Music and Science, Banff, Alberta, Canada, July 31–August 3, 2005, pp. 47–56.

[plusmaths-4] Musical pitch and Euclid's algorithm

[5] ttps://anaphoria.com/brun-euclideanalgo.pdf Euclidean Algorithms and Musical Theory

[6] ttps://anaphoria.com/viggo3.pdf A sequence of Constant Structures

[7] ttps://anaphoria.com/viggo2.pdf Viggo's Brun's algorithm applied

[8] ttps://anaphoria.com/ViggoRhythm.pdf Applying Viggo Brun's Algorithm to Rhythm

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]