The Computing Time of the Euclidean Algorithm

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1973
Accession Number
AD0757364

Entities

People

  • George E. Collins

Organizations

  • Stanford University

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Artificial Intelligence
  • Computer Science
  • Computers
  • Decomposition
  • Digital Computers
  • Mathematics
  • Notation
  • Numbers
  • Real Numbers
  • Schools
  • Sequences
  • United States
  • Universities

Readers

  • Graph Algorithms and Convex Optimization.
  • Regression Analysis.