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

Why your Dobble cards always match

Why your Dobble cards always match

Dobble: a game played by kids, but still very popular among adults. In the game, you have to draw two random cards and place them face-up on the table between all the players. Then, you have to look for the identical symbol between the two cards. Between every two...

Gabriel’s Horn Paradox

Gabriel’s Horn Paradox

Some people just die too soon. One such person was Evangelista Torricelli, an Italian mathematician who died at the age of 39 in the year of 1647. Had Torricelli lived longer, he just might have discovered calculus, before Sir Isaac Newton and Gottfried Leibniz....

Why do we count in base 10?

Why do we count in base 10?

What is two plus two? The realist will say four, the computer will say 100, and the cynic will say 5 – but which is correct? The reason we count in base 10 stems from the simplest fact: humans have 10 fingers. Understandable and logical, as this seems to be nature’s...