Euklidsk algoritme

I talteori er euklidsk algoritme ein algoritme for å berekne største felles divisor (SFD) til to element i kva for ein som helst euklidsk ring (til dømes to heiltal). Hovudtydinga til algoritmen er at han ikkje treng faktorisering av dei to heiltala, og at han er ein av dei eldste kjende algoritmane som kan daterast tilbake til Hellas i antikken.

Bakgrunn

Euklidsk algoritme er ein av dei eldste kjende algoritmane, sidan han står skildra i Elementa av Euklid frå rundt 300 fvt. (7. bok, proposition 2). Euklid formulerte opphavleg problemet geometrisk, som problemet med å finne det største «målet» for to linjelengder (ei linje som kunne brukast til å måle begge linjer utan nokon rest), og algoritmen hans skreid fram ved gjentekne substraksjonar av det kortaste frå det lengste linjestykket. Algoritmen vart endå truleg oppdaga av Euklid og dermed kjent opp til 200 år tidlegare.

Han var nesten sikkert kjent av Eudoksos frå Knidos (omkring 375 fvt.), og Aristoteles (omkring 330 fvt.) indikert han i hans Topics, 158b, 29–35.

Skildring av algoritmen

Gjeve to heiltal, a og b, finn største heiltala d slik at d deler a og b. Viss b = 0, returner a. Elles blir prosessen gjenteke med tala b og a modulo b. Det er òg mogleg å bruke gjenteke subtraksjon, der det minste talet trekkjast frå det største, heilt til éit av tala er 0. Dette er den opphavlege algoritmen, men han er mindre effektiv.

Implementering

Nytte av rekursjon

Ved bruk av rekursjon, kan algoritmen uttrykkjast som:

 funksjon SFD(a, b)
     viss b = 0 returner a
     ellers returner SFD(b, a mod b)

I blant anna C++ og Java ser algoritmen slik ut:

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

Bruk av iterasjon

Ein effektiv iterativ metode for kompilatorar som ikkje optimiserar halerekursjon:

 funksjon SFD(a, b)
     så lenge b ≠ 0
         t := b
         b := a mod b
         a := t
     returner a

Døme

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

Kjelder

• Denne artikkelen bygger på «Euklids algoritme» frå Wikipedia på bokmål, den 16. september 2011.