Is the Euclidean Algorithm Optimal Among its Peers?

DOI10.2178/BSL/1102022663MaRDI QIDQ4678946zbMATH OpenOpenAlexFDO

Authors Yiannis N. Moschovakis, Lou van den Dries

Publication date 24 May 2005

Published in The Bulletin of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2178/bsl/1102022663

zbMATH Keywords

Euclidean algorithmgreatest common divisorrecursive program

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Multiplicative structure; Euclidean algorithm; greatest common divisors (11A05) Number-theoretic algorithms; complexity (11Y16) Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Decidability (number-theoretic aspects) (11U05)

Recommendations

• On primitive recursive algorithms and the greatest common divisor function
• Arithmetic complexity
• scientific article; zbMATH DE number 1254258
• Sublinear Parallel Algorithm for Computing the Greatest Common Divisor of Two Integers
• On a parallel Lehmer-Euclid GCD algorithm

Cites work

• A lower bound for integer greatest common divisor computations
• Generating the greatest common divisor, and limitations of primitive recursive algorithms
• On primitive recursive algorithms and the greatest common divisor function

Cited in

(5)

• On primitive recursive algorithms and the greatest common divisor function
• A REMARK ON PRIMALITY TESTING AND DECIMAL EXPANSIONS
• Lower bounds for decision problems in imaginary, norm-Euclidean quadratic integer rings
• Arithmetic complexity
• How good is the Chord algorithm?

This page was built for publication: Is the Euclidean Algorithm Optimal Among its Peers?

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