The Computing Time of the Euclidean Algorithm
- 1 March 1974
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 3 (1) , 1-10
- https://doi.org/10.1137/0203001
Abstract
The maximum, minimum and average computing times of the classical Euclidean algorithm for the greatest common divisor of two integers are derived, to within codominance, as functions of the lengths of the two inputs and the output.Keywords
This publication has 5 references indexed in Scilit:
- Integer Arithmetic Algorithms for Polynomial Real Zero DeterminationJournal of the ACM, 1971
- The Calculation of Multivariate Polynomial ResultantsJournal of the ACM, 1971
- On Euclid's Algorithm and the Computation of Polynomial Greatest Common DivisorsJournal of the ACM, 1971
- A Simple Estimate for the Number of Steps in the Euclidean AlgorithmThe American Mathematical Monthly, 1971
- The number of steps in the Euclidean algorithmJournal of Number Theory, 1970