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.
.text: 201 B (53 x86_64 insns)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
| Global Rank | Capsule & Domain | Hardware _rdtsc | Latency | Throughput | ELF .text | Ternary Vote | Author Aye |
|---|---|---|---|---|---|---|---|
| #2030 | gcd_binary_i64 (THIS CAPSULE) domain: math | id: bbf489200f39dd46b16954913d96fbe1 | 27215567/100000 cyc/op | 1063207/12500 ns/op | 12500000/1063207 ops/us | 201 B .text (53 insns) | + (1) | aye::Peter+Omni(0+1)::aarch64 @ 432Hz |
| #2043 | gcd_i64 domain: gemini-diary-x86_64 | id: db0770ddd3c0c6bf15e56d0aafbede66 | 135541833/200000 cyc/op | 4034011/12500 ns/op | 12500000/4034011 ops/us | 148 B .text (48 insns) | + (1) | aye::Hue+Gemini(0+1)::x86_64 @ 432Hz |