Lower bounds for integer greatest common divisor computations
- 1 January 1988
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
An Omega (log log n) lower bound is proved on the depth of any computation tree with operations (+, -, /, mod, <or=) 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 Theta (n) bound on the depth of any algebraic computation trees with operations (+, -, *, /, <or=) (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.Keywords
This publication has 12 references indexed in Scilit:
- Correction to "Lower Bounds for Sorting with Realistic Instruction Sets"IEEE Transactions on Computers, 1986
- Lower Bounds for Sorting with Realistic Instruction SetsIEEE Transactions on Computers, 1985
- On the control power of integer divisionTheoretical Computer Science, 1983
- The Computational Complexity of Continued FractionsSIAM Journal on Computing, 1983
- Lower bounds for algebraic decision treesJournal of Algorithms, 1982
- Division in idealized unit cost RAMsJournal of Computer and System Sciences, 1981
- Fast Probabilistic Algorithms for Verification of Polynomial IdentitiesJournal of the ACM, 1980
- Factoring numbers in O(logn) arithmetic stepsInformation Processing Letters, 1979
- A characterization of the power of vector machinesJournal of Computer and System Sciences, 1976
- Berechnung und programm. IActa Informatica, 1972