Summary
Add a det_sign_exact() method to Matrix<D> behind a new "exact" Cargo feature flag, using num-bigint/num-rational for exact rational arithmetic. This keeps the default crate zero-dependency.
Motivation: The delaunay crate needs adaptive precision geometric predicates to fix acgetchell/delaunay#228 — 3D bulk Delaunay construction fails at scale because f64 determinants return wrong signs for near-degenerate configurations. The fix requires a fast f64 filter (existing det()) backed by an exact fallback (det_sign_exact()) for the ambiguous cases.
Proposed Changes
1. Add "exact" feature with optional dependencies
Cargo.toml:
[dependencies]
num-bigint = { version = "0.4", optional = true }
num-rational = { version = "0.4", optional = true }
[features]
exact = ["num-bigint", "num-rational"]
2. Implement det_sign_exact() on Matrix<D>
New file src/exact.rs (only compiled with "exact" feature):
fn f64_to_bigrational(x: f64) -> BigRational — exact conversion (every f64 = m × 2^e, so this is lossless)
fn det_sign_exact_impl<const D: usize>(m: &Matrix<D>) -> i8 — Bareiss algorithm (fraction-free Gaussian elimination) in exact BigRational arithmetic, O(D³) operations
- Public method:
Matrix<D>::det_sign_exact(&self) -> i8 returning -1, 0, or +1
3. Version bump to v0.2.0
New public API behind a feature flag = minor version bump per semver.
Design Notes
- Why
BigRational? Every f64 is exactly representable as a rational number (m × 2^e). Determinant computation via Bareiss in BigRational gives the exact sign with no rounding. For the target use case (matrices up to 7×7 for 5D Delaunay), the cost is ~343 BigRational multiplications — trivially fast.
- Why a feature flag?
la-stack currently has zero runtime dependencies. Users who only need f64 operations should not pay for num-bigint/num-rational in their dependency tree.
- Why Bareiss over LU? Bareiss avoids division until the final step, keeping intermediate values as integers (when inputs are integer-representable), which is more efficient for exact arithmetic.
Testing
- Proptest:
det_sign_exact() agrees with det().signum() for well-conditioned random matrices (D=2–5)
- Known matrices: exact sign correct for known singular matrices (det=0), near-singular matrices, identity matrices, and Hilbert-like ill-conditioned matrices
- Edge cases: 1×1 matrices, zero matrices, matrices with subnormal entries
- Feature gating: verify the crate compiles without the
"exact" feature (no regression)
References
- Bareiss, E.H. (1968). "Sylvester's Identity and Multistep Integer-Preserving Gaussian Elimination"
- Shewchuk, J.R. (1997). "Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates"
Downstream
This is a dependency for acgetchell/delaunay#228 — the delaunay crate will use la-stack = { version = "0.2", features = ["exact"] } as part of its new AdaptiveKernel.
Summary
Add a
det_sign_exact()method toMatrix<D>behind a new"exact"Cargo feature flag, usingnum-bigint/num-rationalfor exact rational arithmetic. This keeps the default crate zero-dependency.Motivation: The delaunay crate needs adaptive precision geometric predicates to fix acgetchell/delaunay#228 — 3D bulk Delaunay construction fails at scale because f64 determinants return wrong signs for near-degenerate configurations. The fix requires a fast f64 filter (existing
det()) backed by an exact fallback (det_sign_exact()) for the ambiguous cases.Proposed Changes
1. Add
"exact"feature with optional dependenciesCargo.toml:2. Implement
det_sign_exact()onMatrix<D>New file
src/exact.rs(only compiled with"exact"feature):fn f64_to_bigrational(x: f64) -> BigRational— exact conversion (every f64 = m × 2^e, so this is lossless)fn det_sign_exact_impl<const D: usize>(m: &Matrix<D>) -> i8— Bareiss algorithm (fraction-free Gaussian elimination) in exactBigRationalarithmetic, O(D³) operationsMatrix<D>::det_sign_exact(&self) -> i8returning -1, 0, or +13. Version bump to v0.2.0
New public API behind a feature flag = minor version bump per semver.
Design Notes
BigRational? Every f64 is exactly representable as a rational number (m × 2^e). Determinant computation via Bareiss inBigRationalgives the exact sign with no rounding. For the target use case (matrices up to 7×7 for 5D Delaunay), the cost is ~343 BigRational multiplications — trivially fast.la-stackcurrently has zero runtime dependencies. Users who only need f64 operations should not pay fornum-bigint/num-rationalin their dependency tree.Testing
det_sign_exact()agrees withdet().signum()for well-conditioned random matrices (D=2–5)"exact"feature (no regression)References
Downstream
This is a dependency for acgetchell/delaunay#228 — the
delaunaycrate will usela-stack = { version = "0.2", features = ["exact"] }as part of its newAdaptiveKernel.