Euklids algoritme
Fra Wikipedia, den frie encyklopedi
I tallteori er euklids algoritme en algoritme for å beregne største felles divisor (SFD) til to elementer i hvilket som helst euklidsk ring (for eksempel to heltall). Algoritmens hovedbetydning er at den ikke trenger faktorisering av de to heltallene, og at den er en av de eldste kjente algoritmene som kan dateres tilbake til antikkens Hellas.
Innhold |
[rediger] Bakgrunn
Euklids algoritme er en av de eldste kjente algoritmene, siden den står beskrevet i Euklids Elementene fra rundt 300 f.Kr. (7. bok, proposition 2). Euklid formulerte opprinnelig problemet geometrisk, som problemet med å finne det største «mål» for to linjelengder (en linje som kunne brukes til å måle begge linjer uten noen rest), og hans algoritme fremskred ved gjentatte substraksjoner av det korteste fra det lengste linjestykket. Algoritmen ble dog antagelig oppdaget av Euklid og dermed kjent opp til 200 år tidligere.
Den var nesten sikkert kjent av Eudoxus fra Cnidus (omkring 375 f.Kr.), og Aristoteles (omkring 330 f.Kr.) antydet den i hans Topics, 158b, 29–35.
[rediger] Beskrivelse av algoritmen
Gitt to heltall, a og b, finn største heltall d slik at d deler a og b. Hvis b = 0, returner a. Ellers gjentas prosessen med tallene b og a modulo b. Det er også mulig å bruke gjentatt subtraksjon, der det minste tallet trekkes fra det største, helt til ett av tallene er 0. Dette er den opprinnelige algoritmen, men den er mindre effektiv.
[rediger] Implementering
[rediger] Bruk av rekursjon
Ved bruk av rekursjon, kan algoritmen uttrykkes som:
funksjon SFD(a, b)
hvis b = 0 returner a
ellers returner SFD(b, a mod b)
I blant annet C++ og Java ser algoritmen slik ut:
int SFD(int a,int b){
if ( b == 0 )
return a;
return SFD(b,a%b);
}
[rediger] Bruk av itterasjon
En effektiv iterativ metode for kompilatorer som ikke optimiserer halerekursjon:
funksjon SFD(a, b)
så lenge b ≠ 0
t := b
b := a mod b
a := t
returner a
[rediger] Eksempel
Finn største felles faktor til 42 og 24.
a = 42, b = 24
a = 24, b = (42 mod 24) = 18
a = 18, b = (24 mod 18) = 6
a = 6, b = (18 mod 6) = 0
b = 0, så svaret er a = 6
