Binary GCD algorithm
Implementation
| ← Previous revision | Revision as of 20:34, 19 April 2026 | ||
| Line 38: | Line 38: | ||
uint64_t gcd(uint64_t u, uint64_t v) { |
uint64_t gcd(uint64_t u, uint64_t v) { |
||
if (!u || !v) return u | v; // Identity #1 |
if (!u || !v) return u | v; // Identity #1 |
||
int shift = ctz(u | v); |
int shift = ctz(u | v); |
||
u >>= ctz(u); |
u >>= ctz(u); |
||
uint64_t min, max; |
uint64_t min, max; |
||
while (v) { |
while (v) { |
||
v >>= ctz(v); // Identity #3 |
v >>= ctz(v); // Identity #3 |
||
min = (u < v) ? u : v; |
min = (u < v) ? u : v; // Identity #4 |
||
max = (u > v) ? u : v; |
max = (u > v) ? u : v; |
||
u = min; |
u = min; |
||
v = max - min; |
v = max - min; |
||
} |
} |
||
