The Euclidean algorithm is not optimal among uniform processes
Source: github.com/jasondavies/euclid-uniform-processes/tree/254868…
For every 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 (3 + 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 modulo every sufficiently large modulus at most three of its values share a residue class, and uses close residues to shrink the modulus by three remainder calls at a time. Consequently the intrinsic calls(rem)-complexities of the gcd…
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}'