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:

 a  b  Ekspliko 3555  675    3555 = 675 · 5 + 180 675  180    675 = 180 · 3 + 135 180  135    180 = 135 · 1 + 45 135  45    135 = 45 · 3 + 0 45  0 
Tiel PGKD (3555, 675) = 45

 a  b  Ekspliko 457  938    457 = 938 · 0 + 457 938  457    938 = 457 · 2 + 24 457  24    457 = 24 · 19 + 1 24  1    24 = 24 · 1 + 0 1  0 
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  la vico de nombroj produktitaj per la algoritmo, kaj estu  iliaj longoj. Tiam k=O(n), kaj la rultempo estas barita per

Ĉ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 . 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

Ĉ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



kaj



estas

 a  b            

Ĉ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