The complete analysis of the binary Euclidean algorithm

DOI10.1007/BFB0054853MaRDI QIDQ3840152zbMATH OpenFDO

Authors Brigitte Vallée

Publication date 7 March 1999

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0054853

zbMATH Keywords

complexitycontinued fractionsEuclidean algorithm

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Continued fraction calculations (number-theoretic aspects) (11Y65)

Review text

The number of steps of versions of the Euclidean algorithm for integers has been studied often; \textit{R. Brent} [Algorithms and Complexity, Proc. Symp., Pittsburgh 1976, 321-355 (1976; Zbl 0373.68040)] based his analysis on some unproven but realistic hypotheses. Here, the author provides an unconditional analysis of several parameters of the binary Euclidean algorithm, including the number of steps. For a description of the methods used in the proofs, see [\textit{P. Flajolet} and \textit{B. Vallée}, Continued fraction algorithms, functional operators, and structure constants, Theor. Comput. Sci. 194, No. 1-2, 1-34 (1998)]. The constants obtained by the author and by Brent agree numerically to more than 40 decimal places, but a proof of equality is still lacking. For the entire collection see [Zbl 0891.00022].

Recommendations

• A rigorous version of R. P. Brent's model for the binary Euclidean algorithm
• scientific article; zbMATH DE number 3581610
• Dynamics of the binary Euclidean algorithm: Functional analysis and operators
• New binary Euclidean algorithms
• On the asymptotic analysis of the Euclidean algorithm

Cited in

(10)

• Partial evaluation of the Euclidean algorithm, revisited
• Dynamics of the binary Euclidean algorithm: Functional analysis and operators
• A supplement to J. Shallit's paper ``Origins of the analysis of the Euclidean algorithm
• Maximum number of steps taken by modular exponentiation and Euclidean algorithm
• New binary Euclidean algorithms
• scientific article; zbMATH DE number 3581610 (Why is no real title available?)
• scientific article; zbMATH DE number 7368168 (Why is no real title available?)
• \((1+i)\)-ary GCD computation in \(\mathbb Z[i]\) as an analogue to the binary GCD algorithm.
• A rigorous version of R. P. Brent's model for the binary Euclidean algorithm
• Existence of a limiting distribution for the binary GCD algorithm

This page was built for publication: The complete analysis of the binary Euclidean algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3840152)