mirror of
https://github.com/ruvnet/RuVector.git
synced 2026-05-26 07:44:05 +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.
35 lines
948 B
TOML
35 lines
948 B
TOML
[package]
|
||
name = "ruvector-collections"
|
||
version.workspace = true
|
||
edition.workspace = true
|
||
license.workspace = true
|
||
authors.workspace = true
|
||
repository.workspace = true
|
||
readme = "README.md"
|
||
description = "High-performance collection management for Ruvector vector databases"
|
||
build = "build.rs"
|
||
|
||
[features]
|
||
default = []
|
||
# Opt-in probabilistic Miller-Rabin for u128 (PRD §5, ADR-151).
|
||
# WASM u128 codegen is ~5× slower than native; gate keeps it out of default bundles.
|
||
unstable-u128 = []
|
||
|
||
[dependencies]
|
||
ruvector-core = { version = "2.0.2", path = "../ruvector-core" }
|
||
serde = { workspace = true }
|
||
serde_json = { workspace = true }
|
||
thiserror = { workspace = true }
|
||
dashmap = { workspace = true }
|
||
parking_lot = { workspace = true }
|
||
uuid = { workspace = true }
|
||
bincode = { workspace = true }
|
||
chrono = { workspace = true }
|
||
|
||
[dev-dependencies]
|
||
criterion = { version = "0.5", features = ["html_reports"] }
|
||
|
||
[[bench]]
|
||
name = "primality"
|
||
harness = false
|
||
|