What is the optimal (and computationally simplest) way to calculate the “largest common duration”?

Question

Edit: To clarify, I am interested in dealing with multiple simultaneous tempos (polytempo). Pieces where all voices are in the same tempo at any given time (with exceptions to account for polyrhythms) are not difficult to deal with.

Note that the idea discussed in this post is commonly used to teach polyrhythms like 7:8 (draw fifty-six lines, mark off every seven on the top and every eight on the bottom, etc.).

---

Consider the problem of laying out the rhythm of a piece of music on a grid. The idea is that each note value can be expressed in an integer multiple of one unit. Let's name the largest possible grid unit the largest common duration, abbreviated LCD. We want the largest possible unit because it is the simplest to work with.

If the music uses only binary rhythmic subdivisions, then the LCD is usually the shortest note value present. For example, a piece of music that consists entirely of quarter notes and eighth notes has a LCD of an eighth note. If a piece of music consists of quarter notes and dotted quarter notes, the LCD is still an eighth note, but this is less obvious.

Things get much more interesting when other subdivisions are involved; the shortest note value may not be the LCD. For instance, if we were to add an eighth note triplet to the previous example, the LCD becomes a “triplet sixteenth note” or twenty-fourth note.

---

I am interested in a method of computing the LCD for any piece of music with any rhythmic values. In the following, I will describe a way that appears to work, but it seems suboptimal, needlessly complicated, and problematic. My main question: Is there a cleaner way to do it (while retaining the generality)?

---

We will be treating tuplets and tempo changes identically, for the most part, and we will express both of them using ratios. For example, the common triplet can be thought of as a temporary increase in speed at a 3:2 ratio; a note “within” the triplet is 2/3 as long as the same note “outside” the triplet. The exact same thing happens if a piece changes tempo from 60 bpm to 90 bpm. A change from 90 bpm to 100 bpm causes notes to become 9/10 as long as they previously were.

Step 1. First, normalize all tempos that occur in the music so that they are expressed in terms of the same note value. This is a major problem of this method, since it essentially requires finding the LCD in order to find the LCD! Most of the time, tempos are given using binary rhythms, but it is not inconceivable that we might want to say that there are 120 sixth notes in a minute (e.g., if the music makes heavy use of meters that aren't based on powers of two).

For example, if we have a piece of music that changes from 4/4 at 𝅘𝅥  = 100 to 6/8 (i.e., 2/𝅘𝅥𝅭  ) at 𝅘𝅥𝅭   = 111, then we'll treat the tempos as 𝅘𝅥𝅮   = 200 and 𝅘𝅥𝅮   = 333.

Tuplets will be dealt with at a later stage; for now, ignore them.

Step 2. Choose one tempo as the “base” and convert the other tempos to ratios based on note values in the base tempo.

For example, say we have a piece of music with tempos 𝅘𝅥  = 90, 𝅘𝅥  = 95, 𝅘𝅥  = 98. If we set 𝅘𝅥  = 90 as the base, then the other two tempos are related to the base by ratios of 19:18 and 49:45.

Step 3. Next we will eliminate tuplets. Take all tuplet ratios (reduced to lowest terms) and multiply them by the ratio of the tempo in which they occur.

For example, say we have the piece of music in the previous example (with tempos related to the base by 19:18 and 49:45). If a triplet occurs in the 19:18 tempo, then we'll obtain a new tempo related to the base by (3:2)×(19:18) = 19:12.

As long as the two terms of the tuplet ratio refer to the same note value, we needn't worry about anything besides the ratio. Thus 5:4𝅘𝅥  , 5:4𝅘𝅥𝅮  , and indeed 10:8𝅘𝅥   are equivalent. But the full generality of the tuplet ratio notation is troublesome and again seems to require finding the LCD, because we have to normalize the note values.

For example, what if we want to fit eight fifth notes in the time of seven sixth notes? I'm pretty sure that this relationship is equivalent to 18:7, but figuring it out is tricky. With binary divisions (e.g., three eighth notes in the time of two quarter notes), normalization is not too bad.

Step 4. Now we have a collection of tempo ratios corresponding to the tempos that appear in the piece of music. Match each tempo ratio to the shortest note value occurring in the music at that tempo.

For example, Conlon Nancarrow's Study no. 36 for player piano is a canon in four voices, related by a 20:19:18:17 tempo ratio; that is, voice 2 is 18/17 faster than voice 1, voice 3 is 19/17 faster than voice 1, and voice 4 is 20/17 faster than voice 1. Because it is a canon, all four voices have the same shortest note value, a sixty-fourth note.

Step 5. Our current goal is to equalize the second terms of all the ratios. We care only about ratios that aren't expressed in terms of powers of two; we'll call such ratios “defective”. If there are no defective ratios, skip to Step 6.

Repeat Steps 5a–5e for each tempo ratio p = a:b. Let V be the associated note value.

Step 5a. Convert p to a fraction f. If a < b, let f be 2a/b and divide V in half.

Step 5b. Find the closest fraction to f that has the form c/d, where c > d and d is a power of two; call this fraction g. For example, if f is 7/5, then g will be 7/4.

Step 5c. Let t = f/g. This will be a fraction m/n where m is a power of two and m < n.

Step 5d. Construct a c:d tuplet made up of V's. Divide each of the c notes into m parts.

Step 5e. Use g instead of p for the current tempo ratio, and use V×m instead of V for the associated note value.

For example, let's return to Nancarrow, with the ratios 18:17, 19:17, and 20:17, where the shortest note value in each tempo is a sixty-fourth note. First f is 18/17, g is 18/16 = 9/8, and t is 16/17. We make a 9:8 sixty-fourth note tuplet, divide each sixty-fourth note into sixteen 1024th notes, and group together seventeen of those 1024th notes. Instead of 18:17 we use 9:8, and instead of a sixty-fourth note we use seventeen 1024th notes. Proceeding similarly for the other voices gives us new ratios of 19:16 and 5:4, both of which have the same associated duration of seventeen 1024th notes.

Step 6. Now we have only non-defective tempo ratios. Multiply the ratios by powers of two until the second terms are all the same. If the first term of any ratio exceeds the second term, then double the first term and double the corresponding duration before scaling. We also find the “binary” LCD using the expressions of the durations associated with the ratios so that they are all in terms of the same note value. All of this is done for the base ratio of 1:1 as well.

Continuing with the Nancarrow example, we will adjust 1:1 to be 16:16 and 9:8 to be 18:16 and 5:4 to be 20:16; 19:16 stays the same. The sixty-fourth note associated with 1:1 gets scaled to sixteen 1024th notes.

Step 7. Find the least common multiple of the first terms of the ratios. This is the LCD of the entire piece of music and represents the duration of the binary LCD found in Step 6, at the base tempo.

In the Nancarrow piece, this is lcm(16, 18, 19, 20) = 13680. Thus 13680 units make up one 1024th note at the base tempo, and 218880 units make up one sixty-fourth note at the base tempo; 12160 units make up one 1024th note at the 18:16 tempo, and 206720 units make up one sixty-fourth note at the original 18:17 tempo ratio; 11520 units make up one 1024th note at the 19:16 tempo, and 195840 units make up one sixty-fourth note at the original 19:17 tempo ratio; 10944 units make up one 1024th note at the 20:16 tempo ratio, and 186048 units make up one sixty-fourth note at the original 20:17 tempo ratio. I believe that one of these grid units is a 224133120th note, in relation to the base tempo.

Answer 1

The simplest algorithm is:

1. Lay out all of the notated durations (notes and rests) in each voice in
   a single stream, including any tempo change indications.1
2. Let qi=0 = the starting basic duration.
3. Go to the first notation.
4. Repeat {
5.   If there's a new tempo, adjust qi proportionally.
6.   If the current notation is a fraction of the current qi
7.     calculate the new qi=i+1.
8. } Until no more durations.


1 Whether tempi are simultaneous or not does not affect
  their relative durations. So, for conceptual ease, just lay out
  everything in a single line.

This would automatically account for all tuplets, tempo changes, etc. By the end of the piece, you would have the unit value being sought.

---

Example

This example is based on excerpts from "A Question, A Rose" (2018) for solo violin by Benjamin Boretz.²

1. Starting duration/tempo is quarter-note = q₀ = 25 bpm = 60/25 sec. = 2.4 sec.
2. First duration = quarter rest. ( = 1 * q₀)
3. Next duration = dotted half-note. ( = 3 * q₀)
4. Next duration = eighth-note. So q₁ = q₀/2 = 1.2 sec.
5. Next duration = triplet eighth-note. So q₂ = q₁/3 = q₀/6 = .4 sec.
6. Next duration = triplet quarter-note. ( = 2 * q₁)
7. Next duration = quarter note. ( = 3 * q₁)
8. New tempo: quarter-note = 24 bpm. So ratio to previous tempo = 25/24; thus, q₃ = 25q₂/24 = 25(q₀/6)/24 = 25q₀/(6*24) = 25q₀/144 = 0.416666... sec.
9. Next duration = sixteenth rest.³ So q₄ = q₃/2 = (25q₀/144)/2 = 25q₀/288 = 0.208333... sec.
10. Next duration = eighth note. ( = 2 * q₄)
11. Next duration = sixteenth as 2/3 of triplet. q₅ = (2/3)q₄ = (2/3)(25q₀/288) = 50q₀/864 = 0.1388888... sec.
12. Next duration = 32-note triplet = q₅/2 = 25q₀/288 = 0.0694444... sec. ~ 864 bpm

So the GCD is 288, and the tempo is 25/288th-note ~ 864 bpm or each grid division = .0694444... seconds.

---

² _{Benjamin Boretz, "A Question, A Rose: for violin alone", Perspectives of New Music 57/1-2 (Winter/Summer 2019): 251-54. https://www.jstor.org/stable/10.7757/persnewmusi.57.1-2.0251 (accessed 22 Jan 2021).}

³ _{Technically there is a triplet here, but I'm treating as a regular sixteenth rest for variety of rhythmic values.}

Answer 2

After prolonged discussion I think I finally understand that you want to:

1. type in a music notation that may include polytempo, polyrhythmic and/or polymetric structures
2. visualise it in a piano roll that preserves lengths of the notes
3. play it back accurately

Concerning 1. I'm not sure if there is software allowing you to type in polytempo scores, and polymetric is already challenging – but maybe I'm wrong. Googling "polytempo" yields some results, perhaps you should research that.

A workaround possible with most music notation software would be to create separate score files containing sections in different tempi. Important: make sure you count the length of leading empty measures in each file, so that they can be merged together.

Another workaround that most music notation can accept is to use tuplets, but there are limitations of this approach. Also music notation software typically doesn't display note positions preserving rhythm proportions anyway.

If you want to write your own music notation program (good luck, that might be a huge project!) you still don't need "least common duration". Instead, let the program operate in music terms for each voice. Computer can then calculate the positions in time for each note.

Example: voice one has a measure in meter a/b=4/4 at tempo T=97BPM filled with 16th notes, followed by a measure a/b=in 3/4 at T=103BPM filled with eight-note triplets.

Duration of a 16th note in the first measure is:

d1_16 = 1/16 × b × 60/T = 1/16 × 4 × 60/97 [s]

Start time t of ith 16th note in the first measure is:

t1_16(i) = (i-1) × d1_16

Full duration of the first measure is

d1 = 4 × 60/97 [s]

Duration of a 8th note triplet (or 1/12th note) in the second measure is:

d2_12 = 1/12 × b × 60/T = 1/12 × 4 × 60/103 [s]

Time of each ith triplet eight-note in the second measure is

t2_12(i) = d1 + (i-1) × d2_12

Full duration of the second measure is

d2 = 3 × 60/103 [s]

You can then add a second voice with completely different tempo, meter and rhythm. I hope these example formulae are sufficient to exemplify how to calculate the time.

Concerning 2. and 3. maybe there is software that allows you to do it. For 3., you can render music from separate files and mix them together.

For visualisation, make sure you apply some antialiasing, as even with perfect calculations aliasing can produce visible artifacts when objects are displayed on computer monitor pixel grid.

Answer 3

Algorithm: Take the length of the first note or rest (expressed as a fraction reduced to its lowest terms) as the initial value of the LCD. Then, for each note or rest, divide the note duration by the LCD, reduce this fraction to its lowest terms, and then divide the LCD by the denominator of this fraction.

Example:

Note/rest durations: 3/4 ; 1/1 ; 1/8 ; 3/8 ; 5/16 ; 1/2 ; 7/24 ; 3/10  

3/4  → LCD is 3/4  
1/1  → 1/1 ÷ 3/4 = 4/3 → LCD is 3/4 ÷ 3 = 1/4  
1/8  → 1/8 ÷ 1/4 = 1/2 → LCD is 1/4 ÷ 2 = 1/8  
3/8  → 3/8 ÷ 1/8 = 3/1 → LCD remains 1/8  
5/16 → 5/16 ÷ 1/8 = 5/2 → LCD is 1/8 ÷ 2 = 1/16  
1/2  → 1/2 ÷ 1/16 = 8/1 → LCD remains 1/16  
7/24 → 7/24 ÷ 1/16 = 14/3 → LCD is 1/16 ÷ 3 = 1/48  
3/10 → 3/10 ÷ 1/48 = 72/5 → LCD is 1/16 ÷ 5 = 1/240  

Largest Common Duration is 1/240

When turning this into code, you can simplify these steps, avoid a lot of the fraction reductions, and skip a lot of notes or rests (e.g. all duplicate durations can be skipped), but keep in mind that the numerator of the LCD may not be 1 at the start (although once it changes to 1, that is permanent from there on).