Arithmetic complexity

Lou Van Den Dries, Yiannis N. Moschovakis

Research output: Contribution to journalArticle

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 languageEnglish (US)
Article number2
JournalACM Transactions on Computational Logic
Volume10
Issue number1
DOIs
StatePublished - Nov 1 2008

Keywords

  • Coprimeness
  • Greatest common divisor
  • Lower bounds for arithmetical problems
  • Recursive programs

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)
  • Logic
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Arithmetic complexity'. Together they form a unique fingerprint.

  • Cite this