Accession Number:

AD0757364

Title:

The Computing Time of the Euclidean Algorithm

Descriptive Note:

Corporate Author:

STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s):

• Collins, George E.

Report Date:

1973-01-01

Pagination or Media Count:

21.0

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.

Descriptors:

• *NUMBER THEORY
• *NUMERICAL ANALYSIS
• ALGORITHMS
• COMPUTER PROGRAMMING
• SET THEORY
• THEOREMS

Subject Categories:

• Theoretical Mathematics
• Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE