Algorithmus Euclidis

E Vicipaedia
Salire ad: navigationem, quaerere
Ecce methodus Euclidis divisoris communis maximi (DCM) inveniendi duorum longitudinum BA et DC, ambabus multipla longitudinis communis (monadis) esse definitis. Longitudine DC breviore, ea ad BA "metandam" usurpatur, sed solum semel, quod residuum EA est minus CD. Nunc EA metatur (bis) longitudinem breviorem DC, residuo FC breviore quam longitudine EA. Ergo FC metatur (ter) longitundinem EA. Quia non est residuum, processus finem habet, et FC est divisor communis maximus. Ab dextera est exemplum Nicomachi cum numeris 49 et 21, dantibus DCM 7 (vide Heath 1908:300).

In mathematica algorithmus Euclidis est modus efficax duorum numerorum integrorum divisoris communis maximi (DCM, sive factoris communis maximi) computandi. Ex mathematico Graeco Euclide nominatur, qui eum in libris VII et X Elementorum descripsit.[1]

In forma simplicissima, algorithmus Euclidis pari integrorum incipit, tunc parem novum fingit ex numere minore et differentia inter numeros maiorem et minorem consistentem. Processus iteratur dum numeri sint aequi. Hic numerus igitur est paris principalis divisor communis maximus.

Unus est ex veterrimis algorithmis numericis adhuc in uso commune. Algorithmus principalis in Elementis (c. 300 a.C.n.) descriptus solos numeros naturales et longitudines geometricas (numeros reales) tractavit, sed saeculo 19 definitio amplificata est ad alia genera numerorum comprehenda, qualia sunt numeri integri Gaussiani et polynomia unius variabilis. Hoc notiones hodiernas algebrae abstractae attulit, e.g. anulos Euclidianos. Nunc algorithmus Euclidis latiore definitur ut et alias structuras mathematicas comprehendat, e.g. nodos et polynomia multiplarum variabilium.

Algorithmus multes applicationes theoreticas et practicas habet. Fere ut omnes rhythmos musicales traditionales gentium variarum generat usurpari potest.[2] Pars est praecipua algorithmi RSA, methodi incryptionis clavi publica in commercio electronico pervagati. Ut aequationes Diaphonteas solvat adhibet, e.g., ut numeros qui multiplas congruentias satisfaciunt (vide theorema Sericum de residuis) vel inversos multiplicativos corporis finiti inveniat. Etiam usurpatur ut fractiones continuas construat, in methoda catenarum Sturm ut radices reales polynomii inveniat, et in pluribus algorithmis recentibus factorizationis numerorum integrorum. Denique instrumentum est elementarium ad theoremata demonstranda in theoria numerorum hodierna, talia quales sunt theorema quatuor quadratorum Lagrange et theorema fundamentale arithmeticae.

Si residuis divisionis Euclidianae et non subtractionibus conficitur, algorithmus Euclidis DCM magnorum numerorum efficaciter computat: nunquam plures gradus divisionis quam quinquies numerum cifrarum (in systema decimale) numeri minoris poscit. Hoc a Gabriele Lamé anno 1844 demonstratum est, initium theoriae complexitatis computationalis signans. Methodi ad efficacitatem algorithmi meliorem faciendam saeculo vicensimo creati sunt.

Divisor communis maximus duorum numerorum est maximus numerus qui ambos ita dividit ut residuum non relinquat. Algorithmus Euclidis in elemento nititur, quod DCM duorum numerorum non mutatur si numerus maior ex minore subtrahitur. Nam si k, m, n sunt integri, et k est factor communis duorum integrorum A et B, ergo A = nk et B = mk significat AB = (nm)k, ergo k est etiam factor communis differentiae. Quod k etiam divisorem communem maximum potest representare infra demonstratur. Exempli gratia, 21 est DCM 252 et 105 (252 = 12 × 21; 105 = 5 × 21); quia 252 − 105 = (12 − 5) × 21 = 147, DCM 147 et 105 est etiam 21.

Quandoquidem maior duorum numerorum minuitur, iteratio hunc processi numeros dat ordine minores dum unus zerum sit. Cum hoc fit, DCM est numerus residuus qui non est zerum.

int euclidis_dcm(int m, int n)
{
        if(n == 0)
                return m;
        else
                return euclidis_dcm(n, m % n);
}

Notae[recensere | fontem recensere]

  1. Thomas L. Heath, The Thirteen Books of Euclid's Elements, 2nd ed. [Facsimile. Original publication: Cambridge University Press, 1925], 1956, Dover Publications
  2. Toussaint, Godfried (July 31 to August 3, 2005), "The Euclidean algorithm generates traditional musical rhythms", Proceedings of BRIDGES: Mathematical Connections in Art, Music, and Science (Banff, Alberta, Canada): 47–56 

Bibliographia[recensere | fontem recensere]

Nexus externi[recensere | fontem recensere]

Commons-logo.svg Vicimedia Communia plura habent quae ad Algorithmum Euclidis spectant.