Journal of the ACM Bibliography
Yishay Mansour, Baruch Schieber, and Prasoon Tiwari. A lower bound
for integer greatest common divisor computations. Journal of the
ACM, 38(2):453-471, April 1991.
[BibTeX entry]
Categories and Subject Descriptors:
F.2.1 [Analysis of Algorithms and Problem Complexity]:
Numerical Algorithms and Problems -- number-theoretic
computations
General Terms:
Algorithms
Additional Key Words and Phrases:
Floor operation, greatest common divisor, lower bound, mod operation,
truncation
Selected papers that cite this one
Selected references
- László Babai, Bettina Just, and Friedhelm Meyer auf der
Heide. On the limits of
computations with the floor function. Information and
Computation, 78(2):99-107, August 1988.
- Michael Ben-Or. Lower bounds for algebraic
computation trees (preliminary report). In Proceedings of the
Fifteenth Annual ACM Symposium on Theory of Computing, pages
80-86, Boston, Massachusetts, 25-27 April 1983.
- Alberto Bertoni, Giancarlo Mauri, and Nicoletta Sabadini. A characterization of the
class of functions computable in polynomial time on random access
machines. In Conference Proceedings of the Thirteenth Annual
ACM Symposium on Theory of Computation, pages 168-176, Milwaukee,
Wisconsin, 11-13 May 1981.
- Yishay Mansour, Baruch Schieber, and Prasoon Tiwari. The complexity of
approximating the square root (extended summary). In 30th
Annual Symposium on Foundations of Computer Science, pages
325-330, Research Triangle Park, North Carolina, 30 October-1 November
1989. IEEE.
- Shlomo Moran, Marc Snir, and Udi Manber. Applications of Ramsey's theorem to
decision tree complexity. Journal of the ACM,
32(4):938-949, October 1985.
Shortcuts: