The Euclidean algorithm is not optimal among uniform processes
For every coprime pair a > b ≥ 1 there is a straight-line derivation of gcd(a, b) that uses only the remainder operation on available values and makes at most (6 + o(1)) log₂ a / log₂ log₂ a remainder calls, uniformly in b ≤ a; Euclid's algorithm needs about 1.44 log₂ a calls in the worst case. The proof stores a prefix of the Euclidean remainder sequence, shows that its consecutive pairs stay distinct modulo every sufficiently large modulus, and uses close residues to shrink the modulus by three remainder calls at a time. Consequently the intrinsic calls(rem)-complexities of the gcd and of…
Comments and reviews
No comments yet.
API
curl /api/v1/records/palomar/PALOMAR-2026-10-23-000012
curl -X POST /api/v1/records/palomar/PALOMAR-2026-10-23-000012/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/palomar/PALOMAR-2026-10-23-000012/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'