TY - GEN
T1 - Lower bounds for integer greatest common divisor computations
AU - Mansour, Yishay
AU - Schieber, Baruch
AU - Tiwari, Prasoon
PY - 1988
Y1 - 1988
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
U2 - 10.1109/sfcs.1988.21921
DO - 10.1109/sfcs.1988.21921
M3 - Conference contribution
AN - SCOPUS:0024141922
SN - 0818608773
SN - 9780818608773
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 -