Lower bounds for integer greatest common divisor computations

Yishay Mansour, Baruch Schieber, Prasoon Tiwari

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations

Abstract

An Ω(log log n) lower bound is proved on the depth of any computation tree with operations {+, -, /, mod, ≤} that computes the greatest common divisor (gcd) of all pairs of n-bit integers. A novel technique for handling the truncation operation is implicit in the proof. Also proved is a Θ(n) bound on the depth of any algebraic computation trees with operations {+, -, *, /, ≤} (where ″/″ stands for exact division) that solve many simple problems, e.g., testing if an n-bit integer is odd or computing the gcd of two n-bit integers.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherPubl by IEEE
Pages54-63
Number of pages10
ISBN (Print)0818608773
StatePublished - Dec 1 1988
Externally publishedYes

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Lower bounds for integer greatest common divisor computations'. Together they form a unique fingerprint.

Cite this