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 redakti

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 redakti

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 redakti

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 redakti

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 redakti

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 redakti

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 redakti

 
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 redakti

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 redakti

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 redakti

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ŭ redakti

Eksteraj ligiloj redakti