Arithmetic complexity

DOI10.1145/1459010.1459012MaRDI QIDQ5277820zbMATH OpenOpenAlexFDO

Authors Yiannis N. Moschovakis, Lou van den Dries

Publication date 12 July 2017

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1459010.1459012

zbMATH Keywords

coprimenessgreatest common divisorlower bounds for arithmetical problemsrecursive programs

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On primitive recursive algorithms and the greatest common divisor function
• A lower bound for integer greatest common divisor computations
• Circuit and decision tree complexity of some number theoretic problems
• Is the Euclidean Algorithm Optimal Among its Peers?
• Lower bounds for arithmetic problems

Cited in

(12)

• Lower bounds for decision problems in imaginary, norm-Euclidean quadratic integer rings
• Lower bounds for arithmetic problems
• Complexity of logical theories involving coprimality
• On primitive recursive algorithms and the greatest common divisor function
• Generating the greatest common divisor, and limitations of primitive recursive algorithms
• On Faster Integer Calculations Using Non-arithmetic Primitives
• scientific article; zbMATH DE number 3931010 (Why is no real title available?)
• A lower bound for integer greatest common divisor computations
• On asymptotic estimates for arithmetic cost functions
• Is the Euclidean Algorithm Optimal Among its Peers?
• The Extraordinary Power of Division in Straight Line Programs
• A difference in complexity between recursion and tail recursion

This page was built for publication: Arithmetic complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5277820)