On primitive recursive algorithms and the greatest common divisor function

DOI10.1016/S0304-3975(02)00487-5MaRDI QIDQ1399976zbMATH OpenFDO

Authors Yiannis N. Moschovakis

Publication date 30 July 2003

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0304-3975(02)00487-5

zbMATH Keywords

greatest common divisorrelative primitive recursion

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Recommendations

• Is the Euclidean Algorithm Optimal Among its Peers?
• Generating the greatest common divisor, and limitations of primitive recursive algorithms
• Arithmetic complexity
• A lower bound for integer greatest common divisor computations
• Two Fast GCD Algorithms

Cites work

• A note on definition by cases
• About primitive recursive algorithms
• Generating the greatest common divisor, and limitations of primitive recursive algorithms
• scientific article; zbMATH DE number 1687041 (Why is no real title available?)
• scientific article; zbMATH DE number 217454 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• scientific article; zbMATH DE number 3322506 (Why is no real title available?)
• Intensional aspects of function definitions
• On the asymptotic behaviour of primitive recursive algorithms

Cited in

(10)

• Generating the greatest common divisor, and limitations of primitive recursive algorithms
• An effective programming of GCD algorithms for natural numbers
• The efficiency of primitive recursive functions: a programmer's view
• The laws of integer divisibility, and solution sets of linear divisibility conditions
• A complete characterization of primitive recursive intensional behaviours
• Is the Euclidean Algorithm Optimal Among its Peers?
• The Extraordinary Power of Division in Straight Line Programs
• Arithmetic complexity
• scientific article; zbMATH DE number 3341178 (Why is no real title available?)
• Theoretical computer science: computability, decidability and logic

This page was built for publication: On primitive recursive algorithms and the greatest common divisor function

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