Euklids algoritme

Fra Wikipedia, den frie encyklopedi
Hopp til: navigasjon, søk

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.

Bakgrunn[rediger | rediger kilde]

Euklids algoritme er en av de eldste algoritmene man kjenner til. For den er 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 der blir noen rest. Algoritmen består i gjentatte substraksjoner av det korteste linjestykket fra det lengste. Algoritmen 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 formulering[rediger | rediger kilde]

I bøker som omhandler den delen av matematikken som heter algebra, formuleres Eulklids 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 | rediger kilde]

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.

Implementering[rediger | rediger kilde]

Bruk av rekursjon[rediger | rediger kilde]

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 iterasjon[rediger | rediger kilde]

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

Eksempel[rediger | rediger kilde]

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 eksempel[rediger | rediger kilde]

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 å fortå, 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.