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. 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. 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); }