Algoritme van Euclides

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Animatie van het algoritme van Euclides voor de getallen 252 en 105. De dwarsbalkjes vertegenwoordigen veelvouden van 21, de grootste gemene deler (ggd). In elke stap wordt het kleinere getal van het grotere getal afgetrokken, dit totdat een getal tot nul wordt teruggebracht. Het resterende getal noemt men de grootste gemene deler.

In de getaltheorie, een deelgebied van de wiskunde, is het algoritme van Euclides een efficiënte methode voor het berekenen van de grootste gemene deler (ggd) van twee positieve gehele getallen. Het algoritme is vernoemd naar de Oud-Griekse wiskundige Euclides van Alexandrië, die het algoritme in de boeken VII en X van zijn Elementen beschreef.[1] Het algoritme berust erop dat de ggd van twee gehele getallen ook de ggd is van zowel het kleinste- en het restgetal (bij deling van de grootste getal door de kleinste getal). Zo ontstaat er een aflopend iteratief proces. Er bestaat ook een uitgebreide variant van dit algoritme.

De grootste gemene deler van twee getallen is het grootste getal dat beide getallen zonder rest deelt. Het algoritme van Euclides is gebaseerd op het principe dat de grootste gemene deler van twee getallen niet verandert als het kleinere getal van het grotere wordt afgetrokken. 21 is bijvoorbeeld de grootste gemene deler van 252 en 105 (252 = 21 × 12, 105 = 21 × 5); aangezien de ggd van 147 (252 - 105) en de ggd van 147 en 105 ook gelijk is aan 21. Aangezien men in het algoritme nu van het grootste van de twee getallen het kleinste getal aftrekt, kan men dit proces successievelijk herhalen, totdat een van de twee getallen gelijk wordt aan nul. De grootste gemene deler is het resterende niet-nulzijnde getal. Door omkering van de stappen in het algoritme van Euclides kan de ggd worden uitgedrukt als de som van de twee originele getallen, elk vermenigvuldigd met een positief of negatief geheel getal bijvoorbeeld 21 = 5 × 105 + (-2) × 252. Deze belangrijke eigenschap staat bekend als de identiteit van Bézout.

De oudste overgeleverde beschrijving van het Euclidische algoritme vindt men in de Elementen van Euclides (ca. 300 v.Chr.), waardoor het een van de oudste numerieke algoritmen is die nog steeds worden gebruikt. Het originele algoritme werd alleen voor natuurlijke getallen en meetkundige lengtes (reële getallen) beschreven, maar in de 19e eeuw werd het algoritme veralgemeend tot andere soorten soorten getallen, zoals de gehele getallen van Gauss en veeltermen in één variabele. Dit leidde tot moderne abstracte algebraïsche begrippen zoals Euclidische domeinen. In de 20e eeuw is het algoritme van Euclides verder veralgemeend naar andere wiskundige structuren, zoals knopen en multivariate veeltermen.

Het algoritme van Euclides kent vele theoretische en praktische toepassingen. Het kan worden gebruikt voor het genereren van bijna alle belangrijkste traditionele muzikale ritmes gebruikt in verschillende culturen over de hele wereld. [2] Ook is het een belangrijk onderdeel van het RSA-algoritme, een publieke sleutel versleuteling methode, die op grote schaal in de elektronische handel wordt gebruikt. Het algoritme wordt gebruikt bij het oplossen van Diophantische vergelijkingen, zoals het vinden van getallen die aan meerdere Congruenties (Chinese reststelling) of multiplicatieve inversen van een eindig veld voldoen. Het algoritme van Euclides kan ook worden gebruikt in de constructie van kettingbreuken, in de Sturm-kettingmethode voor het vinden van reële wortels van een veelterm en in diverse moderne geheel getal factorisatie algoritmen. Ten slotte is het een fundamenteel instrument voor het bewijzen van stellingen in de moderne getaltheorie, zoals de vier-kwadratenstelling van Lagrange en de hoofdstelling van de rekenkunde (unieke factorisatie).

Voor grote getallen berekent het algoritme van Euclides de ggd op efficiënte wijze, dit omdat het algoritme nooit meer stappen vereist dan vijf keer het aantal cijfers (basis 10) van het kleinere gehele getal. Dit werd in 1844 bewezen door Gabriel Lamé. Dit bewijs markeert het begin van complexiteitstheorie. Methoden voor het verbeteren van de efficiëntie van het algoritme van Euclides werden in de 20e eeuw ontwikkeld.

Voorbeeld[bewerken]

Aan de hand van een voorbeeld wordt het algoritme van Euclides verduidelijkt.

We bepalen met het algoritme van Euclides de ggd van 900 en 1140.

Deling van 1140 door 900 levert:

1140 = 1\times 900 + 240\,

De gezochte ggd is ook de ggd van 900 en 240, zodat we verder gaan en 900 door 240 delen:

900 = 3\times 240+180\,

En zo gaan we verder:

240 = 180+60\,
180 = 3\times 60 + 0\,

Nu is de rest 0, en daarmee zijn we aan het einde gekomen. We hebben bepaald dat 60 de grootste gemene deler van 900 en 1140 is.

De berekening laat zich kort opschrijven als de rij:

1140\ \ 900\ \ 240\ \ 180\ \ 60\ \  0\,

Voor elk opvolgend drietal ...abc... in de rij geldt: a mod b = c

Op deze manier berekenen we ook:

752\ \ 372\ \ 8\ \ 4\ \ 0.\,

waaruit we concluderen:

\mathrm{ggd}(752,372) = 4\,.

Het algoritme[bewerken]

  1. Noem het grootste van de beide getallen A, het andere B.
  2. Trek B net zo vaak van A af totdat er 0 over blijft of een getal kleiner dan B. (A mod B)
  3. Wanneer er 0 over blijft zijn we klaar, en is B de ggd.
  4. Zo niet, herhaal dan het algoritme met B en wat er van A over is.

Geschiedenis[bewerken]

Het algoritme van Euclides is een schoolvoorbeeld van een algoritme en het oudst bekende. Euclides vermeldt het in Elementen (boek VII, propositie 1 en 2). Euclides beschouwde het meetkundige probleem om van twee afstanden een gemeenschappelijke "maat" te vinden. Het algoritme is vrijwel zeker niet door Euclides bedacht, maar was al zo'n 200 jaar eerder bekend, vrijwel zeker bij Eudoxus van Cnidus (ca. 375 v.Chr.). Ook Aristoteles (ca. 330 v.Chr.) wijst in zijn werk Topica (158b, 29-35) op het algoritme. Gabriel Lamé bewees, dat het algoritme ten hoogste 5k stappen nodig heeft, waarin k het aantal decimale cijfers van b voorstelt.

Uitbreiding[bewerken]

Er is een uitbreiding van het algoritme, het uitgebreide algoritme van Euclides, waarmee ook een oplossing van de Diophantische vergelijking

ax+by=\rm{ggd}(a,b)\,

wordt verkregen.

Implementatie[bewerken]

In onderstaande implementaties ontbreekt vooralsnog de eerste stap:

1. "Noem" (bepaal) het grootste van de beide getallen A, het andere B.

Niettemin gaat het goed, omdat de getallen bij de eerste recursie omgewisseld worden.

A Mod B is altijd A wanneer B > A, maar de daadwerkelijke berekening hiervan is bij controle vooraf overbodig.


C/C++/Java

Een recursieve vorm in C, C++ en Java ziet er als volgt uit:

int ggd(int a, int b)
{
  if (b == 0)
  {
    return a;
  }
  else
  {
    return ggd(b,a%b);
  }
}

Een iteratieve versie:

int ggd(int a, int b)
{
  int rest;

  while (b != 0)
  {
    rest = a % b;
    a = b;
    b = rest;
  }

  return a;
}

Scheme

Een recursieve implementatie in scheme ziet er als volgt uit:

(define (ggd a b)
  (if (= b 0)
      a
      (ggd b (remainder a b))))

VISUAL BASIC 2008

Dit is een mogelijk algoritme voor visual basic.NET (v2008).

        Dim rest As Integer
        Do
            rest = grootstegetal Mod kleinstegetal
            grootstegetal = kleinstegetal
            kleinstegetal = rest
        Loop While rest <> 0
    End Sub


Voetnoten[bewerken]

  1. (en) Thomas L. Heath, De dertien boeken van de Elementen van Euclides, 2e ed. [Facsimile. Oorspronkelijke publicatie: Cambridge University Press, 1925], 1956, Dover Publications
  2. (en) Godfried Toussaint, "The Euclidean algorithm generates traditional musical rhythms," (Het algoritme van Euclidische genereert de traditionele muzikale ritmes) Proceedings of BRIDGES: Mathematical Connections in Art, Music, and Science, Banff, Alberta, Canada, 31 juli-3 augustus 2005, pp. 47-56.