Euklids algoritme

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

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.

Bakgrunn[rediger | rediger kilde]

Euklids algoritme er en av de eldste kjente algoritmene, siden den står beskrevet i Euklids Elementer 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 Eudoksos fra Knidos (omkring 375 f.Kr.), og Aristoteles (omkring 330 f.Kr.) antydet den i hans Topics, 158b, 29–35.

Algebraisk formulering[rediger | rediger kilde]

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

  a = b \cdot q_1 + r_1

 b = r_1 \cdot q_2 + r_2

 r_1 = r_2 \cdot q_3 + r_3

         \cdot

        \cdot

        \cdot

 r_{n-2} = r_{n-1} \cdot q_n + r_n

 r_{n-1} = r_n \cdot q_{n+1} + r_{n+1}

Man begynner altså med tallene a og b, og gjentar prosedyren helt til  r_{n+1} = 0. Da er  r_n største felles divisor for a og b.

Tallet q_1 er kvotienten mellom a og b, og beregenes ved vanlig divisjon. Tallet r_1 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 :

 q_1 = a div  b og  r_1 = a mod b, 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 optimiserer 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.