The complete analysis of the binary Euclidean algorithm (Q3840152)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1186933
Language Label Description Also known as
default for all languages
No label defined
    English
    The complete analysis of the binary Euclidean algorithm
    scientific article; zbMATH DE number 1186933

      Statements

      0 references
      7 March 1999
      0 references
      Euclidean algorithm
      0 references
      complexity
      0 references
      continued fractions
      0 references
      The complete analysis of the binary Euclidean algorithm (English)
      0 references
      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].
      0 references

      Identifiers