Algorithmus Euclidis
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 A − B = (n − m)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- ↑ Thomas L. Heath, The Thirteen Books of Euclid's Elements, secunda ed. [Facsimile. Original publication: Cambridge University Press, 1925], 1956, Dover Publications
- ↑ 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- Cohen, Henri (1993). A Course in Computational Algebraic Number Theory. New York: Springer-Verlag. ISBN 0-387-55640-0
- Cohn, H. (1962). Advanced Number Theory. New York: Dover. ISBN 0-486-64023-X
- Cormen TH, Leiserson CE, Rivest RL, and Stein C (2001). Introduction to Algorithms (secunda ed.). MIT Press and McGraw–Hill. ISBN 0-262-03293-7
- Cox, D; Little, J; O'Shea, D (1997). Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra (secunda ed.). Springer-Verlag. ISBN 0-387-94680-2
- Lejeune Dirichlet, Peter Gustav (1894). Dedekind, Richard. ed. Vorlesungen über Zahlentheorie (Lectures on Number Theory). Braunschweig: Vieweg. See also Vorlesungen über Zahlentheorie
- Hardy GH, Wright EM [revised by D.R. Heath-Brown and J.H. Silverman]. (2008). An Introduction to the Theory of Numbers (sexta ed.). Oxford: Clarendon Press. ISBN 978-0-19-921986-5
- Knuth D (1997). The Art of Computer Programming, Volume 2: Seminumerical Algorithms (tertia ed.). Addison–Wesley. ISBN 0-201-89684-2
- LeVeque, William J. (1996) [1977]. Fundamentals of Number Theory. New York: Dover. ISBN 0-486-68906-9
- Mollin, R. A. (2008). Fundamental Number Theory with Applications (secunda ed.). Boca Raton: Chapman & Hall/CRC. ISBN 978-1-4200-6659-3
- Ore, Øystein (1948). Number Theory and Its History. New York: McGraw–Hill
- Rosen, K. H. (2000). Elementary Number Theory and its Applications (quarta ed.). Reading, MA: Addison–Wesley. ISBN 0-201-87073-8
- Schroeder, Manfred (2005). Number Theory in Science and Communication (quarta ed.). Springer-Verlag. ISBN 0-387-15800-6
- Stark, Harold (1978). An Introduction to Number Theory. MIT Press. ISBN 0-262-69060-8
- Stillwell, John (1997). Numbers and Geometry. New York: Springer-Verlag. ISBN 0-387-98289-2
- Stillwell, John (2003). Elements of Number Theory. New York: Springer-Verlag. ISBN 0-387-95587-9
- Tattersall, J. J. (2005). Elementary number theory in nine chapters. Cambridge: Cambridge University Press. ISBN 978-0-521-85014-8
- Uspensky JV, Heaslet MA (1939). Elementary Number Theory. New York: McGraw–Hill
Nexus externi
recensere
|
Vicimedia Communia plura habent quae ad Algorithmum Euclidis spectant. |