The Euclidean algorithm is not optimal among uniform processes
Reusing a stored Euclidean prefix, we show that every pair $a\geq b$ has a derivation of $\gcd(a,b)$ from $a,b$ with $O(\log a/\log\log a)$ applications of the remainder function alone; Euclid's algorithm needs order $\log a$ in the worst case. These derivations bound the intrinsic complexity of gcd and coprimeness by the same order, refuting Moschovakis's conjectured logarithmic lower bounds for uniform processes; by his best-uniform-process theorem, a single uniform process attains this bound. The Main Conjecture for algorithms remains open. We also prove an $\Omega(\log\log a)$ lower…
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2610.00604
curl -X POST /api/v1/records/hexagon/2610.00604/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2610.00604/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'