TY - GEN

T1 - Lower bounds for integer greatest common divisor computations

AU - Mansour, Yishay

AU - Schieber, Baruch

AU - Tiwari, Prasoon

PY - 1988/12/1

Y1 - 1988/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0024141922&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0024141922&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0024141922

SN - 0818608773

T3 - Annual Symposium on Foundations of Computer Science (Proceedings)

SP - 54

EP - 63

BT - Annual Symposium on Foundations of Computer Science (Proceedings)

PB - Publ by IEEE

ER -