pub fn math_gcd(mut a: i64, mut b: i64) -> i64 {
a = a.abs();
b = b.abs();
while b > 0 {
let t = b;
b = a % b;
a = t;
}
a
}
pub fn math_lcm(a: i64, b: i64) -> i64 {
if a == 0 || b == 0 {
return 0;
}
let gcd = math_gcd(a, b);
((a * b) / gcd).abs()
}
pub fn solve_nullspace(
matrix: &[Vec<i64>],
rows: usize,
cols: usize,
transpose: bool,
) -> Vec<Vec<i64>> {
let (work_rows, work_cols) = if transpose {
(cols, rows)
} else {
(rows, cols)
};
let mut a_mat = vec![vec![0; work_cols]; work_rows];
for r in 0..work_rows {
for c in 0..work_cols {
a_mat[r][c] = if transpose {
if c < matrix.len() && r < matrix[c].len() {
matrix[c][r]
} else {
0
}
} else {
if r < matrix.len() && c < matrix[r].len() {
matrix[r][c]
} else {
0
}
};
}
}
let mut pivot_row = vec![-1; work_cols];
let mut is_free = vec![true; work_cols];
let mut p = 0;
let mut c = 0;
while c < work_cols && p < work_rows {
let mut pr = p;
let mut found = false;
while pr < work_rows {
if a_mat[pr][c] != 0 {
found = true;
break;
}
pr += 1;
}
if !found {
c += 1;
continue;
}
if pr != p {
a_mat.swap(p, pr);
}
let pivot = a_mat[p][c];
is_free[c] = false;
pivot_row[c] = p as i32;
for i in 0..work_rows {
if i != p {
let val_i = a_mat[i][c];
if val_i != 0 {
let g = math_gcd(pivot, val_i);
let factor_p = val_i / g;
let factor_i = pivot / g;
for j in 0..work_cols {
a_mat[i][j] = factor_i * a_mat[i][j] - factor_p * a_mat[p][j];
}
let mut r_gcd = 0;
for j in 0..work_cols {
r_gcd = math_gcd(r_gcd, a_mat[i][j]);
}
if r_gcd > 1 {
for j in 0..work_cols {
a_mat[i][j] /= r_gcd;
}
}
}
}
}
let mut p_gcd = 0;
for j in 0..work_cols {
p_gcd = math_gcd(p_gcd, a_mat[p][j]);
}
if p_gcd > 1 {
for j in 0..work_cols {
a_mat[p][j] /= p_gcd;
}
}
p += 1;
c += 1;
}
let mut basis_vectors = Vec::new();
for f in 0..work_cols {
if is_free[f] {
let mut num_vec = vec![0; work_cols];
let mut den_vec = vec![1; work_cols];
for j in 0..work_cols {
if is_free[j] {
if j == f {
num_vec[j] = 1;
den_vec[j] = 1;
} else {
num_vec[j] = 0;
den_vec[j] = 1;
}
} else {
let pr = pivot_row[j] as usize;
let a_pr_j = a_mat[pr][j];
let a_pr_f = a_mat[pr][f];
let mut num = -a_pr_f;
let mut den = a_pr_j;
if den < 0 {
num = -num;
den = -den;
}
let g = math_gcd(num, den);
num_vec[j] = num / g;
den_vec[j] = den / g;
}
}
let mut lcm = 1;
for j in 0..work_cols {
lcm = math_lcm(lcm, den_vec[j]);
}
let mut int_vec = vec![0; work_cols];
for j in 0..work_cols {
int_vec[j] = num_vec[j] * (lcm / den_vec[j]);
}
let mut vec_gcd = 0;
for j in 0..work_cols {
vec_gcd = math_gcd(vec_gcd, int_vec[j]);
}
if vec_gcd > 1 {
for j in 0..work_cols {
int_vec[j] /= vec_gcd;
}
}
let mut all_non_positive = true;
for j in 0..work_cols {
if int_vec[j] > 0 {
all_non_positive = false;
break;
}
}
if all_non_positive {
for j in 0..work_cols {
int_vec[j] = -int_vec[j];
}
}
basis_vectors.push(int_vec);
}
}
basis_vectors
}
pub const MAX_SAFE_INT: i64 = 9_007_199_254_740_991;
pub const MIN_SAFE_INT: i64 = -9_007_199_254_740_991;
pub const PINVARIANT_OVERFLOW_CODE: &str = "ERR_PINVARIANT_SAFE_INT_OVERFLOW";
#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
pub struct PInvariantRangeError {
pub code: String,
pub step: String,
pub message: String,
}
impl PInvariantRangeError {
pub fn new(step: &str, message: impl Into<String>) -> Self {
Self {
code: PINVARIANT_OVERFLOW_CODE.to_string(),
step: step.to_string(),
message: message.into(),
}
}
}
fn check_safe_i128(val: i128, step: &str) -> Result<i64, PInvariantRangeError> {
if val < (MIN_SAFE_INT as i128) || val > (MAX_SAFE_INT as i128) {
return Err(PInvariantRangeError::new(
step,
format!("Value {} exceeds IEEE-754 safe integer bounds", val),
));
}
Ok(val as i64)
}
fn math_gcd_i128(mut a: i128, mut b: i128) -> i128 {
a = a.abs();
b = b.abs();
while b > 0 {
let t = b;
b = a % b;
a = t;
}
a
}
pub fn normalize_primitive_basis(
basis: &[Vec<i64>],
) -> Result<Vec<Vec<i64>>, PInvariantRangeError> {
let mut normalized = Vec::with_capacity(basis.len());
for vec in basis {
let mut g: i128 = 0;
for &v in vec {
let _ = check_safe_i128(v as i128, "normalization")?;
g = math_gcd_i128(g, v as i128);
}
let mut out: Vec<i64> = if g > 1 {
vec.iter().map(|&v| ((v as i128) / g) as i64).collect()
} else {
vec.clone()
};
if let Some(&first_nz) = out.iter().find(|&&x| x != 0) {
if first_nz < 0 {
for x in &mut out {
*x = check_safe_i128(-(*x as i128), "normalization")?;
}
}
}
normalized.push(out);
}
normalized.sort();
Ok(normalized)
}
pub fn solve_nullspace_checked(
matrix: &[Vec<i64>],
rows: usize,
cols: usize,
transpose: bool,
) -> Result<Vec<Vec<i64>>, PInvariantRangeError> {
for row in matrix {
for &v in row {
check_safe_i128(v as i128, "input_validation")?;
}
}
let (work_rows, work_cols) = if transpose {
(cols, rows)
} else {
(rows, cols)
};
if work_rows == 0 || work_cols == 0 {
return Ok(Vec::new());
}
let mut a_mat = vec![vec![0i64; work_cols]; work_rows];
for r in 0..work_rows {
for c in 0..work_cols {
let val = if transpose {
if c < matrix.len() && r < matrix[c].len() {
matrix[c][r]
} else {
0
}
} else if r < matrix.len() && c < matrix[r].len() {
matrix[r][c]
} else {
0
};
a_mat[r][c] = check_safe_i128(val as i128, "input_validation")?;
}
}
let mut pivot_row = vec![-1i32; work_cols];
let mut is_free = vec![true; work_cols];
let mut p = 0usize;
let mut c = 0usize;
while c < work_cols && p < work_rows {
let mut pr = p;
let mut found = false;
while pr < work_rows {
if a_mat[pr][c] != 0 {
found = true;
break;
}
pr += 1;
}
if !found {
c += 1;
continue;
}
if pr != p {
a_mat.swap(p, pr);
}
let pivot = a_mat[p][c] as i128;
is_free[c] = false;
pivot_row[c] = p as i32;
for i in 0..work_rows {
if i != p {
let val_i = a_mat[i][c] as i128;
if val_i != 0 {
let g = math_gcd_i128(pivot, val_i);
let factor_p = check_safe_i128(val_i / g, "row_elimination")? as i128;
let factor_i = check_safe_i128(pivot / g, "row_elimination")? as i128;
for j in 0..work_cols {
let term1 = check_safe_i128(factor_i * (a_mat[i][j] as i128), "row_elimination")? as i128;
let term2 = check_safe_i128(factor_p * (a_mat[p][j] as i128), "row_elimination")? as i128;
a_mat[i][j] = check_safe_i128(term1 - term2, "row_elimination")?;
}
let mut r_gcd: i128 = 0;
for j in 0..work_cols {
r_gcd = math_gcd_i128(r_gcd, a_mat[i][j] as i128);
}
if r_gcd > 1 {
for j in 0..work_cols {
a_mat[i][j] = ((a_mat[i][j] as i128) / r_gcd) as i64;
}
}
}
}
}
let mut p_gcd: i128 = 0;
for j in 0..work_cols {
p_gcd = math_gcd_i128(p_gcd, a_mat[p][j] as i128);
}
if p_gcd > 1 {
for j in 0..work_cols {
a_mat[p][j] = ((a_mat[p][j] as i128) / p_gcd) as i64;
}
}
p += 1;
c += 1;
}
let mut basis_vectors = Vec::new();
for f in 0..work_cols {
if is_free[f] {
let mut num_vec = vec![0i64; work_cols];
let mut den_vec = vec![1i64; work_cols];
for j in 0..work_cols {
if is_free[j] {
num_vec[j] = if j == f { 1 } else { 0 };
den_vec[j] = 1;
} else {
let pr = pivot_row[j] as usize;
let a_pr_j = a_mat[pr][j] as i128;
let a_pr_f = a_mat[pr][f] as i128;
let mut num = -a_pr_f;
let mut den = a_pr_j;
if den < 0 {
num = -num;
den = -den;
}
let g = math_gcd_i128(num, den);
num_vec[j] = check_safe_i128(num / g, "back_substitution")?;
den_vec[j] = check_safe_i128(den / g, "back_substitution")?;
}
}
let mut lcm: i128 = 1;
for j in 0..work_cols {
let d = den_vec[j] as i128;
if lcm == 0 || d == 0 {
lcm = 0;
} else {
let g = math_gcd_i128(lcm, d);
lcm = check_safe_i128(((lcm / g) * d).abs(), "back_substitution")? as i128;
}
}
let mut int_vec = vec![0i64; work_cols];
for j in 0..work_cols {
let mult = lcm / (den_vec[j] as i128);
int_vec[j] = check_safe_i128((num_vec[j] as i128) * mult, "back_substitution")?;
}
basis_vectors.push(int_vec);
}
}
normalize_primitive_basis(&basis_vectors)
}
#[path = "solver_precomputed.rs"]
mod solver_precomputed;
#[allow(unused_imports)]
pub use solver_precomputed::*;
#[cfg(test)]
#[path = "solver_tests.rs"]
mod tests;