Is the Euclidean Algorithm Optimal Among its Peers?

DOI10.2178/bsl/1102022663zbMath1095.03025OpenAlexW2137695078MaRDI QIDQ4678946

Yiannis N. Moschovakis, L. P. D. van den Dries

Publication date: 24 May 2005

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

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

zbMATH Keywords

greatest common divisorEuclidean algorithmrecursive program

Mathematics Subject Classification ID

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

Related Items (2)

A REMARK ON PRIMALITY TESTING AND DECIMAL EXPANSIONS ⋮ Lower bounds for decision problems in imaginary, norm-Euclidean quadratic integer rings

Cites Work

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

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