Abstract
We obtain lower bounds on the cost of computing various arithmetic functions and deciding various arithmetic relations from specified primitives. This includes lower bounds for computing the greatest common divisor and deciding coprimeness of two integers, from primitives like addition, subtraction, division with remainder and multiplication. Some of our results are in terms of recursive programs, but they generalize directly to most (plausibly all) algorithms from the specified primitives. Our methods involve some elementary number theory as well as the development of some basic notions and facts about recursive algorithms.
Original language | English (US) |
---|---|
Article number | 2 |
Journal | ACM Transactions on Computational Logic |
Volume | 10 |
Issue number | 1 |
DOIs | |
State | Published - Nov 1 2008 |
Keywords
- Coprimeness
- Greatest common divisor
- Lower bounds for arithmetical problems
- Recursive programs
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science
- Logic
- Computational Mathematics