Euclidische ritmes

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 Euclides

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.

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$ , …].

Voorbeelden van dit soort getallen zijn de Gulden Snede $\phi$ en $\sqrt(2)$ .
$goldenrationfraction$

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

← Previous: Sfeerverslag VESTING Ouderdag Next: Portret: Paul Erdős →

The Sausage Catastrophe

by Bart Koopmans | Sep 20, 2023 | Mathematics

Introduction Contrary to what you might expect, this article is not actually about sausages. It is not even about food at all. Instead, the sausage catastrophe is a mathematical phenomenon that occurs when studying the theory of finite sphere packing. Finite...

The Seven Bridges of Königsberg

by Otis de Waal | Jun 13, 2023 | Mathematics, Operations Research

Imagine you are taking a stroll around the 18th century Prussian city of Königsberg (currently Kaliningrad, Russia). The river Pregel runs through Königsberg and there are two large islands in this river. The islands are connected to each other and to the mainland by...

Why you haven’t found love yet – the Math edition

by Deirdre Westenbrink | May 16, 2023 | Mathematics, Psychology, Society

Have you ever wondered how many people are out there for you? How many people tick all your boxes? Many of us are searching for ‘the one’, but haven’t found them yet. We are all searching for love, as feeling loved makes us feel less pressure, less alone, less...

« Older Entries

Mathematics | Music

March 15, 2016

Share this article:

Written by Jorrit Visser

Euclides

Het algoritme van Euclides

Reële en rationele getallen