Analysis of the Binary Euclidean Algorithm

Abstract

In this paper the author analyzes a continuous model of the binary algorithm and finds the expected number of iterations. The results agree with the observed behavior of the algorithm much better than those predicted by Knuth's 'lattice-point' model.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1976
Accession Number
ADA029130

Entities

People

  • Richard P. Brent

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Banach Space
  • Coefficients
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Distribution Functions
  • Instructions
  • Iterations
  • Numbers
  • Power Series
  • Probability
  • Probability Density Functions
  • Probability Distribution Functions
  • Probability Distributions
  • Theorems

Readers

  • Operations Research
  • Structural Dynamics.