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

Fingerprint

Number theory
Lower bound
Arithmetic Functions
Highest common factor
Computing
Recursive Algorithm
Subtraction
Remainder
Division
Multiplication
Costs
Generalise
Integer

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

Cite this

Arithmetic complexity. / Van Den Dries, Lou; Moschovakis, Yiannis N.

In: ACM Transactions on Computational Logic, Vol. 10, No. 1, 2, 01.11.2008.

Research output: Contribution to journalArticle

Van Den Dries, Lou ; Moschovakis, Yiannis N. / Arithmetic complexity. In: ACM Transactions on Computational Logic. 2008 ; Vol. 10, No. 1.
@article{8c871cacffc64f97b1d9c40279b0900b,
title = "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.",
keywords = "Coprimeness, Greatest common divisor, Lower bounds for arithmetical problems, Recursive programs",
author = "{Van Den Dries}, Lou and Moschovakis, {Yiannis N.}",
year = "2008",
month = "11",
day = "1",
doi = "10.1145/1459010.1459012",
language = "English (US)",
volume = "10",
journal = "ACM Transactions on Computational Logic",
issn = "1529-3785",
publisher = "Association for Computing Machinery (ACM)",
number = "1",

}

TY - JOUR

T1 - Arithmetic complexity

AU - Van Den Dries, Lou

AU - Moschovakis, Yiannis N.

PY - 2008/11/1

Y1 - 2008/11/1

N2 - 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.

AB - 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.

KW - Coprimeness

KW - Greatest common divisor

KW - Lower bounds for arithmetical problems

KW - Recursive programs

UR - http://www.scopus.com/inward/record.url?scp=59449097809&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=59449097809&partnerID=8YFLogxK

U2 - 10.1145/1459010.1459012

DO - 10.1145/1459010.1459012

M3 - Article

AN - SCOPUS:59449097809

VL - 10

JO - ACM Transactions on Computational Logic

JF - ACM Transactions on Computational Logic

SN - 1529-3785

IS - 1

M1 - 2

ER -