Euclidische ritmes

March 15, 2016

Share this article:

De hedendaagse wiskunde kent tal van algoritmes die worden gebruikt om probleemsituaties te optimaliseren. Door middel van iteraties wordt er naar de optimale oplossing toegewerkt. Algoritmes zijn al eeuwenoud. In de oudheid werden de algoritmes al beschreven door de wiskundigen uit die tijd. Zo werd ook het Euclidische algoritme destijds voor het eerst opgetekend. Het algoritme kent ook zijn toepassingen in de praktijk. Zo kan het onder meer gebruikt worden om traditionele muzikale ritmes van over de hele wereld te genereren.

Euclides

Euclides, ook wel de vader van de meetkunde (Oudgrieks:\gamma\epsilon\omega\mu\epsilon\tau\rho\iota\alpha) genoemd, was een Griekse wiskundige uit Alexandrië van rond 300 v.Chr. Ondanks dat er weinig over hem bekend en overgeleverd is, wordt aangenomen dat hij de auteur van het boek Elementen is. Dit boek beschrijft onder meer meetkundige vormen, elementaire getaltheorie en het bewijs dat er oneindig veel priemgetallen zijn. Ook vermeldt het boek het algoritme hoe je van twee getallen de grootste gemene deler berekent. Later zou dit algoritme bekend komen te staan als het algoritme van Euclides.

Het algoritme van EuclidesEuclidean_algorithm_252_105_animation_flipped

Dit algoritme om de grootste gemene deler, in het Engels greatest common divisor (gcd), te bepalen berust op het feit dat de gcd van twee gehele getallen ook de gcd is van het kleinste getal en het getal dat je overhoudt als je de twee initiële getallen van elkaar aftrekt. Door dit herhaaldelijk te doen ontstaat er een iteratief proces, ook wel een algoritme genoemd. In het kort ziet het algoritme er als volgt uit:

– Het grootste getal is X, het andere getal is Y.
– Trek Y zo vaak mogelijk van X af totdat er of 0 overblijft of een getal kleiner dan Y. Het getal dat overblijft is de restterm.
– Indien er 0 overblijft, is Y de gcd van zowel X als Y.
– Indien er niet 0 overblijft, worden stappen 1 en 2 herhaald met de restterm en Y. Vanzelfsprekend is Y nu groter dan de restterm.

Omgeschreven naar wiskunde ziet het algoritme er als volgt uit:

X = a_0 \times Y + r_0
Y = a_1 \times r_0 + r_1
r_0 = a_2 \times r_1 + r_2

r_N = a_{(N+2)} \times r_{(N+1)} + r_{(N+2)}
r_{(N+1)} = a_{(N+3)} \times r_{(N+2)} + 0

De stappen worden herhaald totdat de restterm 0 wordt. De laatste restterm die niet 0 is, is dan de grootste gemene deler. In het bovenstaande geval is dat dus r_{(N+2)}.
 

Reële en rationele getallen

Naast gehele getallen is het algoritme ook te generaliseren naar de reële getallen. Het doel van het algoritme is dan om een reëel getal g te vinden die de volgende relatie beschrijft tussen de reële getallen X en Y:

X = ng en Y = mg, waar m en n integere getallen zijn.

Het algoritme van Euclides werkt net iets anders met reële getallen dan met gehele getallen. De resttermen zijn in dit geval namelijk reële getallen in plaats van gehele getallen. De getallen a_k zijn echter nog steeds wel integer.
Het algoritme vindt nu echter niet altijd een eindige oplossing. In het geval dat het dit wel doet, stel in N stappen, dan kan de breuk \frac{X}{Y} geschreven worden als een eindige continue breuk: [q_0, q_1, …, q_N]. Als de verhouding \frac{X}{Y} een eindige continue breuk is, is het getal \frac{X}{Y} een rationeel getal.
eindige continue breuk
Het kan echter ook zo zijn dat de restterm nooit nul wordt. Het aantal stappen N gaat dan naar oneindig en de breuk \frac{X}{Y} blijkt dan een irrationeel getal te zijn. Dit betekent dat de breuk kan worden geschreven als een oneindige continue breuk: [q_0, q_1, …].
oneindige continue breuk
Voorbeelden van dit soort getallen zijn de Gulden Snede \phi en \sqrt(2).
goldenrationfractionwortel2

Euclidische ritmes

Zoals in het voorgaande valt te lezen, is de werking van het algoritme relatief simpel. Zeker in het geval dat X en Y integere getallen zijn. Godfried Toussaint van de McGill University in Montréal beschrijft in zijn paper ‘The Euclidian Algorithm Generates Traditional Musical Rhythms’ hoe het algoritme kan worden toegepast op het muzikale vlak.
Een manier om ritmes weer te geven is door middel van binaire sequenties. In deze sequenties staat een 1 voor een tijdseenheid (bijvoorbeeld een zestiende noot) en een 0 voor een stilte. Een voorbeeld van een 13-bits sequentie is bijvoorbeeld [1001010010100]. De notatie hiervoor is E(5,13), een 13-bits sequentie met vijf tijdseenheden. In de literatuur van de muziek worden enen en nullen doorgaans vervangen door respectievelijk ‘x’ en ‘.’. E(5,13) wordt dan dus [x . . x . x . . x . x . .]. Maar hoe komt het algoritme in dit geval tot deze sequentie?
Bij deze toepassing werkt het algoritme iets anders dan in het eerdere getallenvoorbeeld. De beginsituatie van E(5,13) schetsen we als volgt: [x x x x x . . . . . . . .]. De eerste stap om de tijdseenheden over de 13-bits sequentie zo goed mogelijk te verdelen is om achter elk ‘x’ een ‘.’ te plaatsen: [x .] [x .] [x .] [x .] [x .] [.] [.] [.]. De volgende stap is om de resulterende stiltes te verdelen over de vijf [x .]. Dit resulteert in [x . .] [x . .] [x . .] [x .] [x .]. Nu is het zaak om de twee [x .] te verdelen over de eerste drie sequenties. Dit resulteert in [x . . x .] [x . . x .] [x . .]. Samenvoegend komt dit uit op [x . . x . x . . x . x . .], de beste verdeling van E(5,13). Het algoritme ziet er dan als volgt uit:

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

Elvis

Zoals eerder vermeld, is het mogelijk om aan de hand van het bovenstaande algoritme ritmes van veel traditionele muziekstijlen te genereren. Als voorbeeld kunnen we het nummer Hound Dog van Elvis Presley gebruiken. De sequentie E(3,8) geeft het volgende resultaat:

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

Dit patroon is te horen in de vroege rock-’n-roll. Zo is het te horen in de baslijn van Hound Dog van Elvis Presley. Een ander ritme gehoord in dit nummer is E(5,8):

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

Dit ritme is te horen in het patroon van het handgeklap in het nummer van Elvis. Luister zelf of je beide ritmes kunt ontdekken:


Euclides had vast niet kunnen bevroeden dat decennia later zijn algoritme zou kunnen worden toegepast op nummers van onder meer The King of Rock and Roll.


Dit artikel is geschreven door Jorrit Visser

jorritvisser

Read more

The moving sofa problem

The moving sofa problem

Mathematics is undeniably beautiful in a certain way, providing us answers to many of life’s complex issues. It finds itself in all aspects of society, and has played a major role for thousands of years. However, despite our deep understanding, there are still many...

The Four-Color Theorem

The Four-Color Theorem

The Four-Color Theorem is a theorem that has its roots in graph theory. The theorem states that any planar graph can be colored properly with four colors. Here properly colored means that no two vertices of the graph that are connected are colored using the same...