Is the Euclidean Algorithm Optimal Among its Peers?

DOI10.2178/BSL/1102022663zbMATH Open1095.03025OpenAlexW2137695078MaRDI QIDQ4678946FDOQ4678946

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

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

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)

Cites Work

• Generating the greatest common divisor, and limitations of primitive recursive algorithms
• A lower bound for integer greatest common divisor computations
• 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)