Dictionary

Euclidean algorithm en · NOUN

Meanings

1. (historical) Any of certain algorithms first described in Euclid's Elements.
   • The Euclidean algorithms for finding a compound ratio also allowed a ratio and an inverse ratio, and more than two ratios to be compounded, since each compounded pair is equivalent to a single ratio between lines. 1998, John J. Roche, The Mathematics of Measurement: A Critical History, The Athlone Press, page 44:
2. Specifically, a method, based on a division algorithm, for finding the greatest common divisor (gcd) of two given integers; any of certain variations or generalisations of said method.
   • 2003, Ali Akhavi, Brigitte Vallée, Average Bit-Complexity of Euclidean Algorithms, Ugo Montanari, Jose D.P. Rolim, Emo Welzl (editors), Automata, Languages and Programming: 27th International Colloquium, Proceedings, Springer, LNCS 1853, page 373, In this paper, we provide new analyses that characterize the precise average bit-complexity of a class of Euclidean algorithms. We consider here five algorithms that are all classical variations of the Euclidean algorithm and are called Classical (𝒢), By-Excess (ℒ), Centered (𝒦), Subtractive (𝒯) and Binary (ℬ).
   • The general behavior of lattice reduction algorithms is far from being well understood.[…]We explain how a mixed methodology has already proved fruitful for small dimensions p, corresponding to the variety of Euclidean algorithms (p = 1) and to the Gauss algorithm (p = 2). 2009, Brigitte Vallée, Antonio Vera, “3: Probabilistic Analyses of Lattice Reduction Algorithms”, in Phong Q. Nguyen, Brigitte Vallée, editors, The LLL Algorithm: Survey and Applications, Springer, page 71:
   • 1985, Erich Kaltofen, Heinrich Rolletschek, Arithmetic in Quadratic Fields with Unique Factorization, Bob F. Caviness (editor), EUROCAL '85, European Conference on Computer Algebra, Linz, Proceedings, Volume 2, Springer, LNCS 204, page 279, In a quadratic field Q (√), D a squarefree integer, with class number 1 any algebraic integer can be decomposed uniquely into primes but for only 21 domains Euclidean algorithms are known. We prove that for D<-19 even remainder sequences with possibly nondecreasing norms cannot determine the GCD of arbitrary inputs.

Forms

Translations (12)

de euklidische Algorithmus (number theory) · it algoritmo di Euclide (number theory) · cs Euklidův algoritmus (number theory) · bg алгоритъм на Евклид (number theory) · is reiknirit Evklíðs (number theory) · ar خَوَارِزْمِيَّة إِقْلِيدِس (number theory) · ro algoritm euclidian (number theory) · es algoritmo de Euclides (number theory) · ru алгори́тм Евкли́да (number theory) · hu euklideszi algoritmus (number theory) · fr algorithme d'Euclide (number theory) · fi Eukleideen algoritmi (number theory)