Report Number: CS-TR-73-331
Institution: Stanford University, Department of Computer Science
Title: The computing time of the Euclidean algorithm.
Author: Collins, George E.
Date: January 1973
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.
http://i.stanford.edu/pub/cstr/reports/cs/tr/73/331/CS-TR-73-331.pdf