Eŭklida algoritmo

En matematiko, **eŭklida algoritmo** estas algoritmo por kalkuli la plej grandan komunan divizoron (PGKD) de du entjeroj aŭ pli ĝenerale de du eroj de eŭklida domajno. Ĝia avantaĝo estas tio ke ĝi ne postulas faktorigon de la entjeroj.

Ĝi estas unu el la plej malnovaj sciataj algoritmoj, datata al la antikvaj grekoj.

## Priskribo de la algoritmo 
Estu donita du nenegativaj entjeroj *a* kaj *b*, ne ambaŭ egalaj al nulo.

Kontrolu ĉu *b* estas nulo; se jes, do *a* estas la PGKD. Se ne, ripetu la procezon uzante nombrojn *b* kaj *a mod b*, la reston post dividado de *a* per *b*.

### Rikura varianto 
Uzante rikuron la algoritmo povas esti esprimita kiel:

 **funkcio** PGKD (a, b)
     **se** b = 0
         **redoni** a
     **alie**
         **redoni** PGKD (b, a **mod** b)

### Ripeta varianto 
Pli kompetenta varianto estas la ripeta:

 **funkcio** PGKD (a, b)
     **dum** b ≠ 0
         t := b
         b := a **mod** b
         a := t
     **redoni** a

### Originala algoritmo 
La originala algoritmo priskribita de Eŭklido traktis la problemon geometrie, uzante ripetitan subtrahon anstataŭ divido kun resto.

  **funkcio** PGKD (a, b)
     **se** a = 0 **redoni** b
     **dum** b ≠ 0
         **se** a > b
             a := a − b
         **alie**
             b := b − a
     **redoni** a

## Ekzemploj 
Jen estas du ekzemploj de la ripeta varianto:

Tiel *PGKD (3555, 675) = 45*

Tiel *PGKD (457, 938) = 1*

En ĉiu ripeto krom eble la unua *a>b* en ĉiu voko. Se komence *b>a* do la unua ripeto interŝanĝas la valorojn.

## Pruvo 
Supozu ke *a* kaj *b* estas pozitivaj entjeroj kies plej grandan komunan divizoron oni volas ekscii. La resto de divido de *a* per *b* estu *r*. Tiam *a = qb+r* kie *q* estas la kvociento de la divido.

Ĉiu komuna dividanto de *a* kaj *b* estas ankaŭ dividanto de *r*. Por vidi kial ĉi tio estas vera, konsideru ke *r* povas esti skribita kiel *r = a-qb*. Nun, se estas komuna dividanto *d* de *a* kaj *b* tia ke *a* = *sd* kaj *b* = *td*, tiam *r = (s-qt)d*. Pro tio ke ĉi ĉiuj nombroj, kaj ankaŭ *s-qt*, estas entjeroj, *r* estas dividebla per *d*.

Simile, se *d* estas dividanto de *b* kaj *r* do *d* estas dividanto de *a*.

La pli supraj rezonadoj veras por ĉiu dividanto *d*. Tial, la plej granda komuna divizoro de *a* kaj *b* estas ankaŭ la plej granda komuna divizoro de *b* kaj *r*. Pro tio sufiĉas daŭrigi serĉadon por la plej granda komuna divizoro kun la nombroj *b* kaj *r*.

Pro tio ke *r* estas pli malgranda je absoluta valoro ol *b*, estos atingita *r=0* post ne pli ol *b* ŝtupoj.

## Rultempo 
[eta|230px|Grafika prezento de la [rultempo por PGKD (x, y). Ruĝa indikas rapidan kalkuladon, pli blua indikas pli malrapidan kalkuladon.]]

Por eŭklida algoritmo, la enigoj postulantaj la plej multajn dividojn estas du sinsekvaj fibonaĉi-nombroj, ĉar iliaj kvocientoj estas la plej malrapida konverĝa ĉenfrakcio de la ora proporcio. Ĉi tiu la plej malbona okazo postulas *O(n)* dividojn, kie *n* estas kvanto de ciferoj en la enigo. Tamen, la divido mem ne estas operacio de konstanta tempo, tiel la tuta tempa komplikeco de la algoritmo estas *O(n2)* (kvadrata tempo).

La kaŭzo estas ke divido de du *n*-bitaj nombroj prenas tempon *O(n(m+1))*, kie *m* estas la longo de la kvociento. Konsideru la kalkuladon de *PGKD (a, b)* kie *a* kaj *b* havi maksimume *n* bitojn, estu a_0,\dots,a_k la vico de nombroj produktitaj per la algoritmo, kaj estu n_0,\dots,n_k iliaj longoj. Tiam *k=O(n)*, kaj la rultempo estas barita per

:O\Big(\sum_{i

Ĉi tiu estas konsiderinde pli bona ol la originala eŭklida algoritmo, en kiu la modula operacio estas plenumata per ripetita subtraho en *O(2n)* paŝoj (eksponenta tempo). Tiel ĉi tiu versio de la algoritmo postulas tempon *O(n 2n)* tempo por *n*-ciferaj nombroj (ankaŭ eksponenta tempo).

Eŭklida algoritmo estas larĝe uzata en praktiko, aparte por malgrandaj nombroj, pro ĝia simpleco. Alternativa algoritmo, la duuma PGKD algoritmo, uzas la duuma prezenton uzatan de komputiloj por eviti dividojn, kiuj estas kutime malrapidaj ĉe komputiloj, kvankam ankaŭ ĝia rultempo estas *O(n2)*; ĝia avantaĝo estas je la pli malgranda valoro de konstanto latenta en la granda O.

Estas pli malsimplaj algoritmoj kiuj havas asimptote malpli grandan rultempon O(n (\log n)^2 (\log \log n)). Vidu en komputa komplikeco de matematikaj operacioj por pliaj detaloj.

## Rilato al ĉenfrakcioj 
La kvocientoj kiuj aperas kiam la eŭklida algoritmo estas aplikita al la enigoj *a* kaj *b* estas precize la nombroj okazantaj en la ĉenfrakcia prezento de *a/b*.

Por *a=3555, b=675* la rilatoj kun la kvocientoj montritaj per grasa tiparo estas

: 3555 = 675 · **5** + 180
: 675 = 180 · **3** + 135
: 180 = 135 · **1** + 45
: 135 = 45 · **3** + 0

kaj do

:\frac{3555}{675} = \mathbf{5} + \frac{1}{\mathbf{3} + \frac{1}{\mathbf{1} + \frac{1}{\mathbf{3}}}}

Ĉi tiu maniero povas esti aplikita al ajnaj reelaj enigoj *a* kaj *b* kun nenula *b*. Se *a/b* estas neracionala tiam la eŭklida algoritmo ne finiĝas, generante malfinian vicon de kvocientoj de ĉenfrakcia prezento de *a/b*.

## Ĝeneraligo al eŭklidaj domajnoj 
La eŭklida algoritmo povas esti aplikita al ringoj, ne nur al entjeroj. La plej ĝenerala ĉirkaŭteksto en kiu la algoritmo finiĝas kun la plej granda komuna divizoro estas en eŭklida domajno. Ekzemple, la gaŭsaj entjeroj kaj polinomringoj super kampo estas ambaŭ eŭklidaj domajnoj.

Estu ringo de polinomoj kun racionalaj koeficientoj. En ĉi tiu ringo, divido kun resto estas farata per la polinoma divido. Ĉe la rezultantaj polinomoj la konduka koeficiento estas tiam farata egala al 1 per divido je ĝi.

Ekzemple por kalkuli la plej grandan komunan divizoron de

: x^4-4x^3+4x^2-3x+14 = (x^2-5x+7)(x^2+x+2)

kaj

: x^4+8x^3+12x^2+17x+6 = (x^2+7x+3)(x^2+x+2)

estas

Ĉi tio kongruas kun la eksplicita faktorigo. Por ĝeneralaj eŭklidaj domajnoj, la pruvo de praveco estas per indukto sur iu ampleksa funkcio. Por la entjeroj, ĉi tiu ampleksa funkcio redonas la nombron mem. Por polinomoj, ĝi redonas gradon de la polinomo (en ĉiu paŝo de la algoritmo la grado malpligrandiĝas je minimume 1).

## Historio 
La eŭklida algoritmo estas unu el la plej malnovaj sciataj algoritmoj. Ĝi aperita en Elementoj de Eŭklido ĉirkaŭ -300 (7-a libro, propozicio 2). Eŭklido originale formulis la problemon geometrie, kiel la problemon de trovado de la plej granda komuna "mezuro" por du strekaj longoj, kiel problemo de trovo de streko kiu povis esti uzata por mezuri ambaŭ strekojn per entjera obligo sen resto. Lia algoritmo funkciis per ripetita subtraho de la pli mallonga streko el la pli longa streko. Tamen, la algoritmo verŝajne ne estis esplorita de Eŭklido kaj ĝi povis esti jam sciata je supren ĝis 200 jaroj pli frue. Ĝi estis preskaŭ certe sciata de Eudoksus de Cnidus (proksimume -375), kaj Aristotelo (proksimume -330) aludis je ĝi en lia *Temoj*, 158b, 29-35.

## Vidu ankaŭ 
* Plej granda komuna divizoro
* Plej malgranda komuna oblo
* Etendita eŭklida algoritmo
* Duuma PGKD algoritmo
* PGKD algoritmo de Lehmer

## Eksteraj ligiloj 
* Eŭklida algoritmo je tranĉi-la-nodon
* Duuma eŭklida algoritmo je tranĉi-la-nodon
* Eŭklida ludo je tranĉi-la-nodon
* 
* 
* 
* Eŭklida algoritmo je MathPages
* Realigo de eŭklida algoritmo en Javascript
* Realigo de eŭklida algoritmo en .NET 
* Muziko kaj eŭklida algoritmo

Kategorio:Nombraj teoriaj algoritmoj