Problem and root cause
The CVP implementation uses exact-rational sphere enumeration but routes integer inputs through f64 first. Its model evaluation also computes in f64, so removing only a guard in the solver leaves the public solve/evaluation path broken.
In src/solvers/customized/closest_vector_problem.rs, integer basis entries are checked with i64_to_exact_f64() before being converted directly to BigRational, and targets go through ClosestVectorTarget::to_f64() before BigRational::from_float().
In src/models/algebraic/closest_vector_problem.rs, both variants currently use Value = Min<f64> and compute the Euclidean norm using floating multiplication, subtraction, summation, and sqrt. This can lose information even when every input scalar is exactly representable.
The shared numeric interface is defined around f64 transport rather than the exact arithmetic the algorithm needs.
Minimal counterexample
basis = [[1]]
target = [9007199254740992_i64]
The exact answer is coefficients [9007199254740992] and distance zero. The current route rejects it at the f64 integer gate, although both the coefficient and target fit i64 and the solver already uses BigRational.
Required refactor
- Replace the existing target conversion requirement with direct exact-rational conversion:
- i64 -> BigRational::from_integer
- finite f64 -> BigRational::from_float, representing the stored binary float exactly.
Reuse the existing ClosestVectorTarget trait and existing num-rational dependency.
- Remove f64 representability gates from integer basis and enumeration arithmetic. Keep explicit checked conversion when an actual returned coefficient must fit the public Vec solution representation.
- Make model evaluation agree with solver arithmetic. Use exact squared Euclidean distance as the comparison value; minimizing squared distance preserves minimizers and avoids an irrational sqrt. Update decision bounds and reduction consumers consistently, including SubsetSum -> CVP. An approximate ordinary-distance display, if retained, must be presentation only and cannot drive comparisons.
- Update Value serialization/formatting, callers, tests, and documentation for this direct objective-representation replacement. Do not leave solver and evaluate using incompatible numeric semantics.
- Reassess the i64 -> f64 CVP variant edge under the new exact evaluation contract: a genuinely lossless coordinate conversion can be sound; rounded target conversion cannot be registered as an exact reduction.
Acceptance tests
- The counterexample returns the exact coefficients and evaluates to zero through typed and CLI solve paths.
- Large basis/target values with exact cancellation evaluate correctly.
- Distinct exact squared distances remain distinguishable in comparison and decision evaluation.
- The f64 target variant uses the exact value of its stored finite float, without claiming to recover a user's pre-rounded decimal intent.
- Genuine output coefficient overflow is an explicit error.
- Small existing CVP solutions and relevant reduction/decision outcomes remain mathematically correct.
Run focused CVP and dependent reduction/decision tests plus make check.
Design references
SymPy exact-number guidance explains why exact values should remain exact through arithmetic. This repository already has the required BigRational implementation; no external solver or numeric abstraction framework is needed.
Related: #1141 (validated solve results), #1145 (exact-reduction versus numerical-lowering boundary).
Problem and root cause
The CVP implementation uses exact-rational sphere enumeration but routes integer inputs through f64 first. Its model evaluation also computes in f64, so removing only a guard in the solver leaves the public solve/evaluation path broken.
In
src/solvers/customized/closest_vector_problem.rs, integer basis entries are checked withi64_to_exact_f64()before being converted directly to BigRational, and targets go throughClosestVectorTarget::to_f64()beforeBigRational::from_float().In
src/models/algebraic/closest_vector_problem.rs, both variants currently useValue = Min<f64>and compute the Euclidean norm using floating multiplication, subtraction, summation, and sqrt. This can lose information even when every input scalar is exactly representable.The shared numeric interface is defined around f64 transport rather than the exact arithmetic the algorithm needs.
Minimal counterexample
The exact answer is coefficients [9007199254740992] and distance zero. The current route rejects it at the f64 integer gate, although both the coefficient and target fit i64 and the solver already uses BigRational.
Required refactor
Reuse the existing ClosestVectorTarget trait and existing num-rational dependency.
Acceptance tests
Run focused CVP and dependent reduction/decision tests plus
make check.Design references
SymPy exact-number guidance explains why exact values should remain exact through arithmetic. This repository already has the required BigRational implementation; no external solver or numeric abstraction framework is needed.
Related: #1141 (validated solve results), #1145 (exact-reduction versus numerical-lowering boundary).