Arithmetic complexity

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.

REFERENCES

• 1: Agrawal, M., Kayal, N., and Saxena, N. 2004. Primes is in P. Annals Math., Second Ser. 160, 781--793.
• 2: Van den Dries, L. 2003. Generating the greatest common divisor, and limitations of primitive recursive algorithms. Found. Computat. Math. 3, 297--324.
• 3: Van den Dries, L. and Moschovakis, Y. N. 2004. Is the Euclidean algorithm optimal among its peers? Bull. Symb. Logic 10, 390--418.
• 4: Donald Ervin Knuth, The Art of Computer Programming, 2nd Ed. (Addison-Wesley Series in Computer Science and Information, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1978
• 5: Yishay Mansour , Baruch Schieber , Prasoon Tiwari, A lower bound for integer greatest common divisor computations, Journal of the ACM (JACM), v.38 n.2, p.453-471, April 1991 [doi>10.1145/103516.103522]
• 6: Yishay Mansour , Baruch Schieber , Prasoon Tiwari, Lower bounds for computations with the floor operation, SIAM Journal on Computing, v.20 n.2, p.315-327, April 1990 [doi>10.1137/0220020]
• 7: McCarthy, J. 1963. A basis for a mathematical theory of computation. In Computer Programming and Formal Systems, P. Braffort and D. Herschberg, Eds. North-Holland, Amsterdam, The Netherlands, 33--70.
• 8: João Meidânis, Lower bounds for arithmetic problems, Information Processing Letters, v.38 n.2, p.83-87, April 26, 1991 [doi>10.1016/0020-0190(91)90227-9]
• 9: Yiannis N. Moschovakis, On primitive recursive algorithms and the greatest common divisor function, Theoretical Computer Science, v.301 n.1-3, p.1-30, 14 May 2003 [doi>10.1016/S0304-3975(02)00487-5]
• 10: Poizat, B. 1995. Les Petits Cailloux. Nur al-Mantiq wal-Ma'rifah.
• 11: Rose, H. 1994. A Course in Number Theory, second ed. Clarendon Press.
• 12: Smoryński, C. 1991. Logical Number Theory I. Springer-Verlag, Berlin, Germany.
• 13: Joachim von zur Gathen , Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, NY, 1999

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Machine-independent complexity**

General Terms:
Algorithms, Theory

Keywords:
Lower bounds for arithmetical problems, coprimeness, greatest common divisor, recursive programs