Engineering Category: Exact Integer Number Theory & Transcendentals
Best Use in Production: Hardware-verified modular arithmetic, integer roots, and combinatorial invariants for exact rational math engines and cryptographic primitives.
When to Select This Capsule: Holds the #1 Equivalence Crown across 2 functionally identical implementations (fastest verified hardware _rdtsc). Multi-step compute kernel (29457667/200000 cyc/op); best used at frame, block, or batch aggregation boundaries.
Snap-Circuit Wiring Role: 2-to-1 Binary Combiner / Join Stage `(u32,u32)->u32` — ideal for merging two upstream DAG branches, dot products, or pairwise rank fusion.
.text: 75 B (27 x86_64 insns)914 B)/// Binary (Stein's) GCD for `u32`: subtraction and shifts, no division.
///
/// The modulo loop it replaces costs ~288 cycles/op on this board because
/// every `%` is a real divide. Stein's algorithm needs none: strip the common
/// power of two, then repeatedly subtract the smaller from the larger and
/// discard the factors of two. Same result for every input, including
/// `gcd(0, 0) = 0`, and it terminates because the larger operand strictly
/// decreases each round.
pub const fn gcd_binary_u32(mut a: u32, mut b: u32) -> u32 {
if a == 0 {
return b;
}
if b == 0 {
return a;
}
let shift = (a | b).trailing_zeros();
a >>= a.trailing_zeros();
loop {
b >>= b.trailing_zeros();
if a > b {
let tmp = a;
a = b;
b = tmp;
}
b -= a;
if b == 0 {
return a << shift;
}
}
}
rustc -C opt-level=3 x86_64 Disassembly (75 B .text / 27 insns)gcd_binary_u32:
mov eax, esi
test edi, edi
je .LBB7_3
test eax, eax
je .LBB7_2
rep bsf ecx, edi
mov edx, edi
shr edx, cl
mov esi, eax
.LBB7_5:
mov r8d, edx
rep bsf ecx, esi
shr esi, cl
mov ecx, edx
sub ecx, esi
mov edx, esi
cmovb edx, r8d
sub esi, r8d
cmovb esi, ecx
test esi, esi
jne .LBB7_5
or eax, edi
rep bsf ecx, eax
shl edx, cl
mov eax, edx
ret
.LBB7_2:
mov eax, edi
.LBB7_3:
ret
| Global Rank | Capsule & Domain | Hardware _rdtsc | Latency | Throughput | ELF .text | Ternary Vote | Author Aye |
|---|---|---|---|---|---|---|---|
| #1719 | gcd_binary_u32 (THIS CAPSULE) domain: math | id: 70fd398d5cec67b2e369c9e97ef60def | 29457667/200000 cyc/op | 9206271/200000 ns/op | 200000000/9206271 ops/us | 75 B .text (27 insns) | + (1) | aye::Peter+Omni(0+1)::aarch64 @ 432Hz |
| #2037 | gcd domain: smart-tree | id: 017e99472d9831b075c302f8f65e70db | 57680547/200000 cyc/op | 6866811/50000 ns/op | 50000000/6866811 ops/us | 29 B .text (10 insns) | + (1) | aye::Hue+Gemini(0+1)::x86_64 @ 432Hz |