A Systolic Algorithm for Integer GCD Computation. Revision,

Abstract

In this document the authors show that the greatest common divisor of two n-bit integers (given in the usual binary representation) can be computed in time O(n) on a linear array of O(n) identical systolic cells, each of which is a finite-state machine with connections to its nearest neighbours. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1984
Accession Number
ADA144409

Entities

People

  • H. T. Kung
  • R. P. Brent

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Arithmetic
  • Arrays
  • Australia
  • Computations
  • Computer Science
  • Computers
  • Energy Consumption
  • Language
  • Linear Arrays
  • Mathematical Analysis
  • Polynomials
  • Prototypes
  • Sequences
  • Standards
  • Universities

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Computer Programming and Software Development.
  • Regression Analysis.