eo es eo pt eo eo eo pt eo en it es eo eo en eo eo eo eo eo eo eo eo eo eo en eo eo eo eo eo pl eo eo en de pl de oc fr oc oc fr oc de fr de en de en en pl en de pl fr it en it fr it fr de fr de en en en en en eo eo eo eo eo eo eo eo eo eo eo en eo eo eo eo eo eo fr fr fr de eo en eo eo eo eo eo pl eo en eo en de en pl pl en en en en en eo eo eo eo eo eo es eo es eo eo eo eo es es es eo es es eo es eo eo lt eo eo eo eo de es eo eo eo eo eo sv ur eo eo eo eo es eo eo eo eo eo eo eo eo tr fi eo eo it eo eo eo eo eo eo eo eo eo eo eo eo ar az uz ru bg bn ca ckb hbs_lat de el en es eu fa fi fr lt he hu hy id it ja ko it lt lv ml be nds nl nb nb pl pms pt ro ru en hbs_lat en sk sl hbs_lat sv ta th tr fy vi zh zh eo eo eo eo eo eo eo eo eo
El Vikipedio, la libera enciklopedio
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.
1 Priskribo de la algoritmo
6 Ĝeneraligo al eŭklidaj domajnoj
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 | redakti fonton]
Uzante rikuron la algoritmo povas esti esprimita kiel:
funkcio PGKD (a, b) se b = 0 redoni a alie redoni PGKD (b, a mod b)
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 | redakti fonton]
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 | redakti fonton]
Jen estas du ekzemploj de la ripeta varianto:
3555 = 675 · 5 + 180
675 = 180 · 3 + 135
180 = 135 · 1 + 45
135 = 45 · 3 + 0
Tiel PGKD (3555, 675) = 45
457 = 938 · 0 + 457
938 = 457 · 2 + 24
457 = 24 · 19 + 1
24 = 24 · 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 | redakti fonton]
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 | redakti fonton]
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 , … , a k {\displaystyle a_{0},\dots ,a_{k}} la vico de nombroj produktitaj per la algoritmo, kaj estu n 0 , … , n k {\displaystyle n_{0},\dots ,n_{k}} iliaj longoj. Tiam k=O(n), kaj la rultempo estas barita per
O ( ∑ i < k n i ( n i − n i + 1 + 2 ) ) ⊆ O ( n ∑ i < k ( n i − n i + 1 + 2 ) ) ⊆ O ( n ( n 0 + 2 k ) ) ⊆ O ( n 2 ) {\displaystyle O{\Big (}\sum _{i<k}n_{i}(n_{i}-n_{i+1}+2){\Big )}\subseteq O{\Big (}n\sum _{i<k}(n_{i}-n_{i+1}+2){\Big )}\subseteq O(n(n_{0}+2k))\subseteq O(n^{2})}
Ĉ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 ) ) {\displaystyle O(n(\log n)^{2}(\log \log n))} . Vidu en komputa komplikeco de matematikaj operacioj por pliaj detaloj.
Rilato al ĉenfrakcioj[redakti | redakti fonton]
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
3555 675 = 5 + 1 3 + 1 1 + 1 3 {\displaystyle {\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[redakti | redakti fonton]
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 − 4 x 3 + 4 x 2 − 3 x + 14 = ( x 2 − 5 x + 7 ) ( x 2 + x + 2 ) {\displaystyle x^{4}-4x^{3}+4x^{2}-3x+14=(x^{2}-5x+7)(x^{2}+x+2)}
x 4 + 8 x 3 + 12 x 2 + 17 x + 6 = ( x 2 + 7 x + 3 ) ( x 2 + x + 2 ) {\displaystyle x^{4}+8x^{3}+12x^{2}+17x+6=(x^{2}+7x+3)(x^{2}+x+2)}
x 4 + 8 x 3 + 12 x 2 + 17 x + 6 {\displaystyle x^{4}+8x^{3}+12x^{2}+17x+6}
x 4 − 4 x 3 + 4 x 2 − 3 x + 14 {\displaystyle x^{4}-4x^{3}+4x^{2}-3x+14}
x 4 − 4 x 3 + 4 x 2 − 3 x + 14 {\displaystyle x^{4}-4x^{3}+4x^{2}-3x+14}
x 3 + 2 3 x 2 + 5 3 x − 2 3 {\displaystyle x^{3}+{\tfrac {2}{3}}x^{2}+{\tfrac {5}{3}}x-{\tfrac {2}{3}}}
x 3 + 2 3 x 2 + 5 3 x − 2 3 {\displaystyle x^{3}+{\tfrac {2}{3}}x^{2}+{\tfrac {5}{3}}x-{\tfrac {2}{3}}}
x 2 + x + 2 {\displaystyle x^{2}+x+2}
x 2 + x + 2 {\displaystyle x^{2}+x+2}
Ĉ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 | redakti fonton]
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 | redakti fonton]
Plej granda komuna divizoro
Plej malgranda komuna oblo
PGKD algoritmo de Lehmer
Eksteraj ligiloj[redakti | redakti fonton]
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
Eric W. Weisstein, Eŭklida algoritmo en MathWorld.
Eŭklida algoritmo en PlanetMath.
Eric W. Weisstein, Teoremo de Lamé en MathWorld.
Eŭklida algoritmo je MathPages
Realigo de eŭklida algoritmo en Javascript
Realigo de eŭklida algoritmo en .NET
Muziko kaj eŭklida algoritmo
Informoj pri la paĝo
Citi ĉi tiun artikolon
Ĉi tiu paĝo estis lastafoje redaktita je 16:20, 25 dec. 2016.
La teksto disponeblas laŭ la permesilo Krea Komunaĵo Atribuite-Samkondiĉe 3.0 Neadaptita; eble aldonaj kondiĉoj aplikeblas. Vidu la uzkondiĉojn por detaloj.
Regularo pri respekto de la privateco
Vidigo por porteblaj aparatoj