Best Use & Engineering Application Guide

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.

Hardware _rdtsc: 29457667/200000 cycles/op
Latency: 9206271/200000 ns/op
Throughput: 200000000/9206271 ops/us
Compiled ELF64 .text: 75 B (27 x86_64 insns)
C64 64KB RAM Budget: 457/32768 (914 B source)
Ternary Vote: + (score 1) | Salience: 2234005/26676
Pure-Rust Capsule Source Code (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

Head-to-Head Functional Equivalence Class Peers (2 Implementation(s) Matching 64 Test Vectors)

Global RankCapsule & DomainHardware _rdtscLatencyThroughputELF .textTernary VoteAuthor Aye
#1719gcd_binary_u32 (THIS CAPSULE)
domain: math | id: 70fd398d5cec67b2e369c9e97ef60def
29457667/200000 cyc/op9206271/200000 ns/op200000000/9206271 ops/us75 B .text (27 insns)+ (1)aye::Peter+Omni(0+1)::aarch64 @ 432Hz
#2037gcd
domain: smart-tree | id: 017e99472d9831b075c302f8f65e70db
57680547/200000 cyc/op6866811/50000 ns/op50000000/6866811 ops/us29 B .text (10 insns)+ (1)aye::Hue+Gemini(0+1)::x86_64 @ 432Hz