Greatest Common Divisor

GCD(8, 12) = 4

GCD(5, 8) = 1

Euclid's algorithm

function euclid(m, k) {
    if (k == 0) {
        return m;
    } else {
        return euclid(k, m % k);
    }
}

function euclid(m, k) {
    if (k == 0) {
        return m;
    } else {
        return euclid(k, m % k);
    }
}

   euclid(8, 5)     // 8 = 1 × 5 + 3
== euclid(5, 3)     // 5 = 1 × 3 + 2
== euclid(3, 2)     // 3 = 1 × 2 + 1
== euclid(2, 1)     // 2 = 1 × 1 + 0
== euclid(1, 0)
== 1

Spallation Neutron Source

E. Bjorklund

5 pulses, 13 timeslots

5 pulses, 8 gaps

■   ■   ■   ■  ■    □ □ □ □ □ □ □ □   ← euclid(8, 5) 

■□  ■□  ■□  ■□ ■□             □ □ □   ← 8 = 1 × 5 + 3

■□□ ■□□ ■□□                   ■□ ■□   ← 5 = 1 × 3 + 2

■□□■□   ■□□■□                   ■□□   ← 3 = 1 × 2 + 1

Godfried T. Toussaint

The Euclidean Algorithm Generates Traditional Musical Rhythms

E(5, 13): ■□□■□■□□■□■□□

E(3, 8): ■□□■□□■□

tresillo

E(5, 8): ■□■■□■■□

cinquillo

E(4, 7): ■□■□■□■

Rotate by 4 beats: ■□■■□■□

Demo