Euclidean algorithm

English

Alternative forms

• Template:L

Noun

1. Template:Lb Any of certain algorithms first described in Template:W.
   • Template:Quote-book
2. Template:Lb 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.
   • 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, Template:W 204, page 279,

     In a quadratic field $\mathbb{Q}(\sqrt{D})$, $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\le -19$ even remainder sequences with possibly nondecreasing norms cannot determine the GCD of arbitrary inputs.

   • 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, Template:W 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 ($ℬ$).

   • Template:Quote-book

Translations

• Czech: Template:T
• Finnish: Template:T
• French: Template:T
• German: Template:T
• Hungarian: Template:T+
• Icelandic: Template:T
• Italian: Template:T
• Romanian: Template:T
• Russian: Template:T
• Spanish: Template:T