{"id":"palomar/PALOMAR-2026-10-23-000012","url":"https://github.com/jasondavies/euclid-uniform-processes/tree/2548681524c7d0d606fa3a4cff00b495157e948f","json":"https://data.palomar-registry.org/entries/PALOMAR-2026-10-23-000012-v2.json","repo":"https://github.com/jasondavies/euclid-uniform-processes","tags":["math.LO","cs.CC","msc:03D15","msc:68Q17","msc:11A05","msc:11Y16"],"score":0,"title":"The Euclidean algorithm is not optimal among uniform processes","trust":"high","domain":"math.LO","source":"palomar","authors":["Jason Davies"],"reviews":0,"subject":"math.LO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"verified":true,"discussed":0,"published":"2026-10-27","reactions":{},"formalized":true}