Algoritme van Euclides

Uit Wikipedia, de vrije encyclopedie

Ga naar: navigatie, zoeken

Het algoritme van Euclides, genoemd naar de Griekse wiskundige Euclides, is een algoritme (rekenwijze) voor het bepalen van de grootste gemene deler (hierna: ggd) van twee positieve gehele getallen. Er is ook een uitgebreidere variant op dit algoritme. Het algoritme berust erop dat de ggd van twee getallen ook de ggd is van de kleinste van de twee en de rest bij deling van de grootste door de kleinste. Zo ontstaat een aflopend iteratief proces.

Aan de hand van een voorbeeld zal het algoritme duidelijk worden.

Inhoud

[bewerk] Voorbeeld

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

Deling van 1140 door 900 levert:

1140 = 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\,.

[bewerk] Het algoritme

  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.
  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.

[bewerk] Geschiedenis

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 Eudoxos van Knidos (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.

[bewerk] Uitbreiding

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.

[bewerk] Implementatie

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))))
 
Persoonlijke instellingen