𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On certain arithmetic functions involving the greatest common divisor

✍ Scribed by Ekkehard Krätzel; Werner Georg Nowak; László Tóth

Book ID
111488803
Publisher
SP Versita
Year
2012
Tongue
English
Weight
980 KB
Volume
10
Category
Article
ISSN
1895-1074

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On primitive recursive algorithms and th
On primitive recursive algorithms and the greatest common divisor function
✍ Yiannis N. Moschovakis 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 341 KB

We establish linear lower bounds for the complexity of non-trivial, primitive recursive algorithms from piecewise linear given functions. The main corollary is that logtime algorithms for the greatest common divisor from such givens (such as Stein's) cannot be matched in e ciency by primitive recurs