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 (27215567/100000 cyc/op); best used at frame, block, or batch aggregation boundaries.

Snap-Circuit Wiring Role: 2-to-1 Binary Combiner / Join Stage `(i64,i64)->i64` — ideal for merging two upstream DAG branches, dot products, or pairwise rank fusion.

Hardware _rdtsc: 27215567/100000 cycles/op
Latency: 1063207/12500 ns/op
Throughput: 12500000/1063207 ops/us
Compiled ELF64 .text: 201 B (53 x86_64 insns)
C64 64KB RAM Budget: 1069/65536 (1069 B source)
Ternary Vote: + (score 1) | Salience: 1178945/14508
Pure-Rust Capsule Source Code (1069 B)
/// Binary (Stein's) GCD for `i64`, same contract as the modulo loop it replaces.
///
/// `gcd_i64` at ~677 cycles/op pays for a real 64-bit divide on every round.
/// Stein's algorithm needs no divide at all: normalise the signs the same way
/// (`saturating_neg`, so `i64::MIN` becomes `i64::MAX`), strip the shared power
/// of two, then subtract and discard factors of two.
///
/// Edge cases preserved exactly: `gcd(0, 0) = 1`, `gcd(0, x) = x`,
/// `gcd(x, 0) = x`.
pub const fn gcd_binary_i64(a: i64, b: i64) -> i64 {
    let mut a = if a < 0 { a.saturating_neg() } else { a };
    let mut b = if b < 0 { b.saturating_neg() } else { b };
    if a == 0 && b == 0 {
        return 1;
    }
    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 (201 B .text / 53 insns)
gcd_binary_i64:
    test    rdi, rdi
    js    .LBB7_1
    test    rsi, rsi
    js    .LBB7_3
.LBB7_4:
    mov    rdx, rsi
    or    rdx, rdi
    je    .LBB7_5
.LBB7_7:
    test    rdi, rdi
    mov    rax, rdi
    cmove    rax, rsi
    je    .LBB7_6
    test    rsi, rsi
    je    .LBB7_6
    rep        bsf    rcx, rdi
    shr    rdi, cl
.LBB7_10:
    mov    rax, rdi
    rep        bsf    rcx, rsi
    sar    rsi, cl
    mov    rcx, rdi
    sub    rcx, rsi
    mov    rdi, rsi
    cmovl    rdi, rax
    sub    rsi, rax
    cmovl    rsi, rcx
    test    rsi, rsi
    jne    .LBB7_10
    rep        bsf    rcx, rdx
    shl    rdi, cl
    mov    rax, rdi
    ret
.LBB7_1:
    xor    eax, eax
    mov    rcx, rdi
    neg    rcx
    setns    al
    movabs    rcx, 9223372036854775807
    add    rcx, rax
    neg    rdi
    cmovo    rdi, rcx
    test    rsi, rsi
    jns    .LBB7_4
.LBB7_3:
    xor    eax, eax
    mov    rcx, rsi
    neg    rcx
    setns    al
    movabs    rcx, 9223372036854775807
    add    rcx, rax
    neg    rsi
    cmovo    rsi, rcx
    mov    rdx, rsi
    or    rdx, rdi
    jne    .LBB7_7
.LBB7_5:
    mov    eax, 1
.LBB7_6:
    ret

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

Global RankCapsule & DomainHardware _rdtscLatencyThroughputELF .textTernary VoteAuthor Aye
#2030gcd_binary_i64 (THIS CAPSULE)
domain: math | id: bbf489200f39dd46b16954913d96fbe1
27215567/100000 cyc/op1063207/12500 ns/op12500000/1063207 ops/us201 B .text (53 insns)+ (1)aye::Peter+Omni(0+1)::aarch64 @ 432Hz
#2043gcd_i64
domain: gemini-diary-x86_64 | id: db0770ddd3c0c6bf15e56d0aafbede66
135541833/200000 cyc/op4034011/12500 ns/op12500000/4034011 ops/us148 B .text (48 insns)+ (1)aye::Hue+Gemini(0+1)::x86_64 @ 432Hz