Algoritme van Euclides: verschil tussen versies

Verwijderde inhoud Toegevoegde inhoud
JRB (overleg | bijdragen)
Aantal implementaties in diverse programmeertalen verwijderd.
Richardw (overleg | bijdragen)
zie op
Regel 1:
[[Bestand:Euclidean algorithm 252 105 animation flipped.gif|thumb|Animatie van het algoritme van Euclides voor de getallen 252 en 105. De dwarsbalkjes vertegenwoordigen [[Veelvoud (wiskunde)|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 [[natuurlijk getal|positieve gehele getallen]]. Het algoritme is vernoemd naar de [[Hellenisme|Oud-Griekse]] [[wiskundige]] [[Euclides van Alexandrië]], die het algoritme in de boeken VII en X van zijn ''[[Elementen van Euclides|Elementen]]'' beschreef.<ref>{{en}} {{aut|[[Thomas Heath|Thomas L. Heath]]}}, ''De dertien boeken van de Elementen van Euclides'', 2e ed. [Facsimile. Oorspronkelijke publicatie: Cambridge University Press, 1925], 1956, [[Dover Publications]]</ref> 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 [[Uitgebreid algoritme van Euclides|uitgebreide]] variant van dit algoritme.
 
Het algoritme is vernoemd naar de [[Hellenisme|Oud-Griekse]] [[wiskundige]] [[Euclides van Alexandrië]], die het algoritme in de boeken VII en X van zijn ''[[Elementen van Euclides|Elementen]]'' beschreef.<ref>{{en}} {{aut|[[Thomas Heath|Thomas L. Heath]]}}, ''De dertien boeken van de Elementen van Euclides'', 2e ed. [Facsimile. Oorspronkelijke publicatie: Cambridge University Press, 1925], 1956, [[Dover Publications]]</ref> Het algoritme berust erop dat de ggd van twee gehele getallen ook de ggd is van zowel het kleinste getal als van de rest die overblijft bij deling van het grootste getal door het kleinste. Zo ontstaat er een aflopend [[iteratie]]f proces. Er bestaat ook een [[Uitgebreid algoritme van Euclides|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 [[uitgebreid algoritme van Euclides|omkering van de stappen in het algoritme van Euclides]] kan de ggd worden uitgedrukt als de [[lineaire combinatie|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 [[Stelling van Bachet-Bézout|identiteit van Bézout]].
 
== Achtergrond ==
De oudste overgeleverde beschrijving van het Euclidische algoritme vindt men in de ''[[Elementen van Euclides|Elementen]]'' van [[Euclides van Alexandrië|Euclides]] (ca. 300 v.Chr.), waardoor het een van de oudste numerieke [[algoritme]]n is die nog steeds worden gebruikt. Het originele algoritme werd alleen voor natuurlijke getallen en meetkundige lengtes ([[reëel getal|reële getal]]len) beschreven, maar in de 19e eeuw werd het algoritme veralgemeend tot andere soorten soorten getallen, zoals de [[Geheel getal van Gauss|gehele getallen van Gauss]] en [[veelterm]]en in één variabele. Dit leidde tot moderne [[abstracte algebra]]ïsche begrippen zoals [[Euclidisch domein|Euclidische domein]]en. In de 20e eeuw is het algoritme van Euclides verder veralgemeend naar andere [[wiskundige structuur|wiskundige structuren]], zoals [[knoop (wiskunde)| knopen]] en [[veelterm|multivariate veelterm]]en.
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.
 
Zo is 21 de grootste gemene deler van {{nowrap|252 en 105 (252 {{=}} 21 × 12, 105 {{=}} 21 × 5)}} aangezien de ggd van {{nowrap|147 (252 - 105) en 105}} ook gelijk is aan 21. Aangezien men in het algoritme 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.
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. <ref>{{en}} {{aut|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.</ref> Ook is het een belangrijk onderdeel van het [[RSA (cryptografie)|RSA-algoritme]], een [[Asymmetrische cryptografie|publieke sleutel versleuteling]] methode, die op grote schaal in de [[electronic commerce|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 [[omgekeerde|multiplicatieve inverse]]n van een [[eindig veld]] voldoen. Het algoritme van Euclides kan ook worden gebruikt in de constructie van [[kettingbreuk]]en, in de [[Sturm-ketting]]methode voor het vinden van reële wortels van een veelterm en in diverse moderne [[ontbinden in priemfactoren|geheel getal factorisatie]] algoritmen. Ten slotte is het een fundamenteel instrument voor het bewijzen van [[stelling (wiskunde)|stellingen]] in de moderne [[getaltheorie]], zoals de [[vier-kwadratenstelling van Lagrange]] en de [[hoofdstelling van de rekenkunde]] (unieke factorisatie).
 
== Uitbreiding ==
Door [[uitgebreid algoritme van Euclides|omkering van de stappen in het algoritme van Euclides]] kan de ggd worden uitgedrukt als de [[lineaire combinatie|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 [[Stelling van Bachet-Bézout|identiteit van Bézout]]. Op deze manier geeft dit [[Uitgebreid algoritme van Euclides|uitgebreide algoritme]] een oplossing voor de [[Diophantische vergelijking]]
 
:<math>ax+by=\rm{ggd}(a,b)\,</math>
 
== Geschiedenis ==
De oudste overgeleverde beschrijving van het Euclidische algoritme vindt men in de ''[[Elementen van Euclides|Elementen]]'' (boek VII, propositie 1 en 2) van [[Euclides van Alexandrië|Euclides]] (ca. 300 v.Chr.), waarmee het een van de oudste numerieke [[algoritme]]n is die nog steeds worden gebruikt. Euclides beschouwde het [[meetkunde|meetkundige]] probleem om van twee afstanden een gemeenschappelijke "maat" te vinden. Het algoritme is waarschijnlijk niet door Euclides bedacht, maar was vrijwel zeker al bekend 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.
 
Het originele algoritme werd alleen voor natuurlijke getallen en meetkundige lengtes ([[reëel getal|reële getal]]len) beschreven, maar in de 19e eeuw werd het algoritme veralgemeend tot andere soorten soorten getallen, zoals de [[Geheel getal van Gauss|gehele getallen van Gauss]] en [[polynoom|veeltermen]] in één variabele. Dit leidde tot moderne [[abstracte algebra]]ïsche begrippen zoals [[Euclidisch domein|Euclidische domeinen]]. [[Gabriel Lamé]] leverde in 1844 het [[wiskundig bewijs]] dat het algoritme nooit meer stappen vereist dan vijf keer het aantal cijfers (basis 10) van het kleinere gehele getal. Dit bewijs markeert het begin van [[computationele complexiteitstheorie]]. In de 20e eeuw werd het algoritme van Euclides verder veralgemeend naar andere [[wiskundige structuur|wiskundige structuren]], zoals [[knoop (wiskunde)|knopen]] en multivariate veeltermen. Ook werden methoden ontwikkeld voor het verbeteren van de efficiëntie van het algoritme.
 
== Toepassingen ==
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.<ref>{{en}} {{aut|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.</ref> Ook is het een belangrijk onderdeel van het [[RSA (cryptografie)|RSA-algoritme]], een [[Asymmetrische cryptografie|publieke sleutel versleutelingsmethode]], die op grote schaal in de [[electronic commerce|elektronische handel]] wordt gebruikt. Het algoritme wordt gebruikt bij het oplossen van [[Diophantische vergelijking]]en, zoals het vinden van getallen die aan meerdere congruenties ([[Chinese reststelling]]) of [[omgekeerde|multiplicatieve inversen]] van een [[Eindig lichaam (Ned) / Eindig veld (Be)|eindig veld]] voldoen. Het algoritme van Euclides kan ook worden gebruikt in de constructie van [[kettingbreuk]]en, in de [[Sturm-ketting]]methode voor het vinden van reële wortels van een veelterm en in diverse moderne [[ontbinden in priemfactoren|geheelgetalfactorisatie-algoritmen]]. Ten slotte is het een fundamenteel instrument voor het bewijzen van [[stelling (wiskunde)|stellingen]] in de moderne [[getaltheorie]], zoals de [[vier-kwadratenstelling van Lagrange]] en de [[hoofdstelling van de rekenkunde]] (unieke factorisatie).
 
== Het algoritme ==
# Noem het grootste van de beide getallen ''A'', het andere ''B''.
# Trek ''B'' net zo vaak van ''A'' af totdat er 0 over blijft of een getal kleiner dan ''B'' (''A'' mod ''B'').
# Wanneer er 0 over blijft zijn we klaar en is ''B'' de ggd.
# Zo niet, herhaal dan het algoritme met ''B'' en wat er van ''A'' over is.
 
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 [[bewijs (wiskunde)|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 ==
Het volgende voorbeeld, waarin de ggd van 900 en 1140 wordt bepaald, verduidelijkt het algoritme van Euclides.
 
Deling van 1140 door 900 levert:
:<math>1140 = 1 \times 900 + 240</math>
 
Omdat de gezochte ggd ook de ggd van 900 en 240 is, wordt 900 door 240 gedeeld:
:<math>900 = 3 \times 240 + 180</math>
 
Dat gaat zo verder:
:<math>240 = 1 \times 180 + 60</math>
:<math>180 = 3 \times 60 + 0</math>
Nu is de rest 0, waarmee een einde aan de berekening komt. De grootste gemene deler van 900 en 1140 is 60, want:
 
:de laatste stap, 180 = 3 x× 60 + 0, laat zien dat 60|180.,
:de stap daarvoor, 240 = 1 x× 180 + 60, laat zien dat 60|240.,
:verder terug, 900 = 3 x× 240 + 180, laat zien dat 60|900.,
:en de eerste stap, 1140 = 1 x× 900 + 240, dat 60|1140.
De conclusie is dat 60 een gemene deler is van 900 en 1140.
 
DeAls conclusie is dus dat 60d een gemene deler is van 900 en 1140., dan laat
:de eerste regel, 1140 = 1 × 900 + 240, zien dat d|240
 
:de tweede regel, 900 = 3 × 240 + 180, dat d|180
En als d een gemene deler is van 900 en 1140, dan laat
:en de derde regel, 240 = 1 × 180 + 60, dat d|60
 
Daaruit volgt dat elke gemene deler van 900 en 1140 een deler is van 60. Dan is 60 de grootste gemene deler.
:de eerste regel, 1140 = 1 x 900 + 240, zien dat d|240.
:de tweede regel, 900 = 3 x 240 + 180, dat d|180.
:en de derde regel, 240 = 1 x 180 + 60, dat d|60.
 
Daaruit volgt dat elke gemene deler van 900 en 1140 deler is van 60. Dus is 60 de grootste gemene deler.
 
De berekening laat zich kort opschrijven als de rij:
:<math>1140\ \ 900\ \ 240\ \ 180\ \ 60\ \ 0\,</math>
 
Voor elk opvolgend drietal ... a b c ... in de rij geldt: a mod b = c
 
Op dezelfde manier wordt de berekningberekening van de ggd van 752 en 372 opgeschreven:
 
:<math>752\ \ 372\ \ 8\ \ 4\ \ 0</math>
 
Daaruit volgt:
:<math>\mathrm{ggd}(752,372) = 4.</math>
 
== Het algoritme ==
# Noem het grootste van de beide getallen ''A'', het andere ''B''.
# Trek ''B'' net zo vaak van ''A'' af totdat er 0 over blijft of een getal kleiner dan ''B''. (''A'' mod ''B'')
# Wanneer er 0 over blijft zijn we klaar, en is ''B'' de ggd.
# Zo niet, herhaal dan het algoritme met ''B'' en wat er van ''A'' over is.
 
== Geschiedenis ==
Het algoritme van Euclides is een schoolvoorbeeld van een algoritme en het oudst bekende. Euclides vermeldt het in ''[[Elementen van Euclides|Elementen]]'' (boek VII, propositie 1 en 2).<!-- en noemde het ''antepheireis'', veranderen wegnemen --> Euclides beschouwde het [[meetkunde|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 ==
Er is een uitbreiding van het algoritme, het [[Uitgebreid algoritme van Euclides|uitgebreide algoritme van Euclides]], waarmee ook een oplossing van de [[Diophantische vergelijking]]
 
:<math>ax+by=\rm{ggd}(a,b)\,</math>
 
wordt verkregen.
 
== Implementatie ==
Afhankelijk van de mogelijkheden die een programmeertaal biedt, kan er gebruik gemaakt worden van [[recursie (informatica)|recursief programmeren]] en de 'mod'-operatie. In onderstaande implementatie wordt de stap
# Noem het grootste van de beide getallen ''A'', het andere ''B''
overgeslagen: het ene getal wordt zonder meer ''A'' en het andere ''B'' genoemd. Niettemin gaat het goed, aangezien {{nowrap|''A'' mod ''B''}} gelijk is aan ''A'' wanneer {{nowrap|''B'' > ''A''}} en de getallen daardoor bij de eerste recursie omgedraaid worden.
 
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:
<pre>
intbepaal ggd(int aA, int bB):
als B = 0
{
if (b =antwoord = 0)A
{anders
antwoord = ggd(B, (A mod B))
return a;
}
else
{
return ggd(b,a%b);
}
}
</pre>
 
Bij programmeertalen die geen ondersteuning voor recursief programmeren bieden en/of de 'mod'-operatie niet kennen, kan ook onderstaande gebruikt worden:
Een iteratieve versie:
<pre>
intbepaal ggd(int aA, int bB):
zolang (A ≠ B)
{
als A > B
int rest;
verminder A met B
 
while (b != 0)anders
verminder B met A
{
rest = a % b;
a = b;
b = rest;
}
 
return a;
}
</pre>
Na doorlopen van deze code zijn de getallen ''A'' en ''B'' gelijk en elkaars grootste gemene deler (evenals van de oorspronkelijke getallen).
 
{{Appendix}}
==Voetnoten==
{{references|85%}}
 
[[Categorie:Getaltheorie]]