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
7 March 1999
0 references
Euclidean algorithm
0 references
complexity
0 references
continued fractions
0 references
0.8647221326828003
0 references
0.8202090859413147
0 references
0.7888168692588806
0 references
0.785467803478241
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