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

Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Multiplicative structure; Euclidean algorithm; greatest common divisors (11A05) Decidability (number-theoretic aspects) (11U05) 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
• 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)

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

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)