mirror of
https://github.com/ruvnet/RuVector.git
synced 2026-05-25 15:03:46 +00:00
12bfcefb18
Lands the deterministic Sinclair-12 Miller-Rabin u64 kernel and build-time prime tables under crates/ruvector-collections/, per ADR-151. Implementation - src/primality_kernel.rs: shared MR core (mulmod via u128, powmod, witness loop, prev/next prime). Single source of truth — include!d from both build.rs and src/primality.rs to keep the build script and runtime kernel byte-identical. - src/primality.rs: public API — is_prime_u32/u64, prev/next_prime_u64, prev_prime_below_pow2(k), next_prime_above_pow2(k), ephemeral_prime(seed). Probabilistic is_prime_u128 gated behind --feature unstable-u128 with Russian-peasant mulmod, mod_add overflow-safe addition, and LCG-seeded witness selection. - build.rs: emits PRIMES_BELOW_2K[57] / PRIMES_ABOVE_2K[57] for k ∈ [8, 64]. ABOVE[64] is a 0 sentinel (no u64 prime > 2^64); k=64 BELOW special-cases via mr_prev_prime_u64(u64::MAX). Tests (76 pass; cross-check 0.00s) - tests/primality_pseudoprimes.rs: pinned A014233 strong pseudoprimes (entries 4, 5, 11) so any witness-set regression — including dropping base-37 — fails loudly. SPP_FIRST_11 = 3_825_123_056_546_413_051 is the canary for base-37 detection. - tests/table_cross_check.rs: re-validates all 114 emitted table entries against MR + sweep_odds_strictly_between (iterates the prime gap, not the range — so even k=63 finishes instantly). - Doc tests + 7 inline unit tests including u128 M_89 smoke. Benches (criterion, M-series) - is_prime_u64 worst case (u64::MAX − 58): 15.63 µs (3 runs ±2%) - prev_prime_below_pow2 k=32 shard router: 7.48 ns - next_prime_u64 ~1e9: 11.44 µs - next_prime_u64 2^61 − 1 general path: 7.83 µs Empirical floor finding: re-running with num-prime 0.4.4 in the same binary on the same hardware measured num_prime::is_prime64(u64::MAX − 58) at 884 ns vs ours at 15.63 µs — confirming the 50 ns PRD target was structurally unachievable in safe Rust (~17.7× headroom recoverable via Montgomery in Phase 0.1, but not 300×). PRD §6 and ADR-151 amended in a follow-up commit.
73 lines
2.8 KiB
Rust
73 lines
2.8 KiB
Rust
// build.rs — emits PRIMES_BELOW_2K[57] and PRIMES_ABOVE_2K[57] using the
|
|
// same Miller-Rabin kernel that ships at runtime. ADR-151 acceptance #2
|
|
// requires the table and the runtime to agree on every entry, and this is
|
|
// how we guarantee that — one source of truth, included from both sides.
|
|
|
|
use std::env;
|
|
use std::fs;
|
|
use std::path::PathBuf;
|
|
|
|
include!("src/primality_kernel.rs");
|
|
|
|
fn main() {
|
|
println!("cargo:rerun-if-changed=src/primality_kernel.rs");
|
|
println!("cargo:rerun-if-changed=build.rs");
|
|
|
|
let mut out = String::with_capacity(4096);
|
|
out.push_str(
|
|
"// AUTO-GENERATED by build.rs from primality_kernel.rs.\n\
|
|
// Do not edit by hand — regenerated on every build.\n\
|
|
//\n\
|
|
// Index: table[k - 8] holds the prime for exponent k, k in [8, 64].\n\n",
|
|
);
|
|
|
|
// BELOW: largest prime strictly less than 2^k.
|
|
out.push_str(
|
|
"/// Largest prime strictly less than 2^k for k in [8, 64], indexed by `k - 8`.\n\
|
|
///\n\
|
|
/// Generated at build time from the same Miller-Rabin kernel that ships at runtime\n\
|
|
/// (ADR-151 acceptance #2). Re-validated under `cargo test`.\n",
|
|
);
|
|
out.push_str("pub const PRIMES_BELOW_2K: [u64; 57] = [\n");
|
|
for k in 8u32..=64 {
|
|
let p = if k == 64 {
|
|
// 2^64 overflows u64. Largest prime < 2^64 is the largest u64
|
|
// prime; u64::MAX itself is composite, so prev_prime(u64::MAX)
|
|
// gives the right answer.
|
|
mr_prev_prime_u64(u64::MAX)
|
|
} else {
|
|
mr_prev_prime_u64(1u64 << k)
|
|
};
|
|
out.push_str(&format!(" {p}, // largest prime < 2^{k}\n"));
|
|
}
|
|
out.push_str("];\n\n");
|
|
|
|
// ABOVE: smallest prime strictly greater than 2^k.
|
|
out.push_str(
|
|
"/// Smallest prime strictly greater than 2^k for k in [8, 64], indexed by `k - 8`.\n\
|
|
///\n\
|
|
/// Entry at k = 64 is `0` (sentinel) — no u64 prime exists greater than 2^64.\n\
|
|
/// Runtime callers must avoid that index.\n",
|
|
);
|
|
out.push_str("pub const PRIMES_ABOVE_2K: [u64; 57] = [\n");
|
|
for k in 8u32..=64 {
|
|
let p = if k == 64 {
|
|
// No u64 prime exists strictly greater than 2^64. Emit a sentinel
|
|
// and forbid this index at the runtime call site (debug_assert
|
|
// in next_prime_above_pow2).
|
|
0u64
|
|
} else {
|
|
mr_next_prime_u64(1u64 << k)
|
|
};
|
|
if p == 0 {
|
|
out.push_str(&format!(" 0, // sentinel: no u64 prime > 2^{k}\n"));
|
|
} else {
|
|
out.push_str(&format!(" {p}, // smallest prime > 2^{k}\n"));
|
|
}
|
|
}
|
|
out.push_str("];\n");
|
|
|
|
let out_dir = PathBuf::from(env::var_os("OUT_DIR").expect("OUT_DIR not set"));
|
|
let out_path = out_dir.join("prime_tables.rs");
|
|
fs::write(&out_path, out).expect("failed to write prime_tables.rs");
|
|
}
|