Åpne hovedmenyen

I tallteori er euklids algoritme en algoritme for å beregne største felles divisor (SFD) til to elementer i en hvilken som helst euklidsk ring (for eksempel to heltall). Algoritmens hovedbetydning er at den ikke forutsetter at faktoriseringen av de to heltallene allerede er kjent, og at den er en av de eldste kjente algoritmene som kan dateres tilbake til antikkens Hellas.

Innhold

BakgrunnRediger

Euklids algoritme er en av de eldste algoritmene man kjenner til; den ble allerede beskrevet i Euklids Elementer fra rundt 300 f.Kr. (7. bok, proposisjon 2). Euklids formulering av algoritmen er geometrisk og beskriver en framgangsmåte (algoritme) til å finne det største felles «mål» for to linjestykker. Han finner da et nytt linjestykke som kan brukes til å måle hvert av de to første linjestykkene uten at det blir noen rest. Algoritmen utføres gjennom gjentatte subtraksjoner av det korteste linjestykket fra det lengste og er antagelig Euklids egen oppdagelse[trenger referanse] og var dermed kjent allerede 200 år tidligere.[trenger referanse] <--NB ordet algoritme stammer ikke fra Euklid, men er først kommet til i nyere tid. -->

Algoritmen var nesten helt sikkert kjent allerede av Eudoksos fra Knidos (omkring 375 f.Kr.),[trenger referanse] og Aristoteles (omkring 330 f.Kr.) antyder kjennskap til den i hans Topica', gr. Τόποι, bok VI, del 11.[trenger referanse]

Algebraisk formuleringRediger

I bøker som omhandler den delen av matematikken som heter algebra, formuleres Euklids algoritme ofte slik :

 

 

 

        

        

        

 

 

Man begynner altså med tallene   og  , og gjentar prosedyren helt til   Da er   største felles divisor for   og  .

Tallet   er kvotienten mellom   og  , og beregenes ved vanlig divisjon. Tallet   er resten man får ved divisjonen. Slik fortsetter man å dividere, helt til divisjonen går opp.

Ved hjelp av operatorene div og mod, kan det skrives slik :

  div   og   mod  , osv . . . nedover langs hele rekken, helt til resten som blir igjen ved siste divisjon er lik null.

Beskrivelse av algoritmen (computer)Rediger

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.

ImplementeringRediger

Bruk av rekursjonRediger

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);
 }

Bruk av iterasjonRediger

En effektiv iterativ metode for kompilatorer som ikke optimaliserer halerekursjon:

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

EksempelRediger

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

Et litt større eksempelRediger

A = 551551 ; B = 50065

551551 = 50065 x 11 + 836

50065 = 836 x 59 + 741

836 = 741 x 1 + 95

741 = 95 x 7 + 76

95 = 76 x 1 + 19

76 = 19 x 4 + 0.

Største felles divisor mellom A og B er altså 19.

Her har vi benyttet gammeldags notasjon, som vanligvis er lettere å forstå, fordi man ungår div og mod begrepene, som mange sikkert synes er uvante. For egentlig er det jo bare vanlig divisjon det dreier seg om.