clm_rust_core/cpn/
solver.rs1pub fn math_gcd(mut a: i64, mut b: i64) -> i64 {
2 a = a.abs();
3 b = b.abs();
4 while b > 0 {
5 let t = b;
6 b = a % b;
7 a = t;
8 }
9 a
10}
11
12pub fn math_lcm(a: i64, b: i64) -> i64 {
13 if a == 0 || b == 0 {
14 return 0;
15 }
16 let gcd = math_gcd(a, b);
17 ((a * b) / gcd).abs()
18}
19
20pub fn solve_nullspace(
21 matrix: &[Vec<i64>],
22 rows: usize,
23 cols: usize,
24 transpose: bool,
25) -> Vec<Vec<i64>> {
26 let (work_rows, work_cols) = if transpose {
27 (cols, rows)
28 } else {
29 (rows, cols)
30 };
31
32 let mut a_mat = vec![vec![0; work_cols]; work_rows];
34 for r in 0..work_rows {
35 for c in 0..work_cols {
36 a_mat[r][c] = if transpose {
37 if c < matrix.len() && r < matrix[c].len() {
38 matrix[c][r]
39 } else {
40 0
41 }
42 } else {
43 if r < matrix.len() && c < matrix[r].len() {
44 matrix[r][c]
45 } else {
46 0
47 }
48 };
49 }
50 }
51
52 let mut pivot_row = vec![-1; work_cols];
53 let mut is_free = vec![true; work_cols];
54
55 let mut p = 0;
56 let mut c = 0;
57
58 while c < work_cols && p < work_rows {
59 let mut pr = p;
61 let mut found = false;
62 while pr < work_rows {
63 if a_mat[pr][c] != 0 {
64 found = true;
65 break;
66 }
67 pr += 1;
68 }
69
70 if !found {
71 c += 1;
72 continue;
73 }
74
75 if pr != p {
77 a_mat.swap(p, pr);
78 }
79
80 let pivot = a_mat[p][c];
81 is_free[c] = false;
82 pivot_row[c] = p as i32;
83
84 for i in 0..work_rows {
86 if i != p {
87 let val_i = a_mat[i][c];
88 if val_i != 0 {
89 let g = math_gcd(pivot, val_i);
90 let factor_p = val_i / g;
91 let factor_i = pivot / g;
92
93 for j in 0..work_cols {
94 a_mat[i][j] = factor_i * a_mat[i][j] - factor_p * a_mat[p][j];
95 }
96
97 let mut r_gcd = 0;
99 for j in 0..work_cols {
100 r_gcd = math_gcd(r_gcd, a_mat[i][j]);
101 }
102 if r_gcd > 1 {
103 for j in 0..work_cols {
104 a_mat[i][j] /= r_gcd;
105 }
106 }
107 }
108 }
109 }
110
111 let mut p_gcd = 0;
113 for j in 0..work_cols {
114 p_gcd = math_gcd(p_gcd, a_mat[p][j]);
115 }
116 if p_gcd > 1 {
117 for j in 0..work_cols {
118 a_mat[p][j] /= p_gcd;
119 }
120 }
121
122 p += 1;
123 c += 1;
124 }
125
126 let mut basis_vectors = Vec::new();
128
129 for f in 0..work_cols {
130 if is_free[f] {
131 let mut num_vec = vec![0; work_cols];
132 let mut den_vec = vec![1; work_cols];
133
134 for j in 0..work_cols {
135 if is_free[j] {
136 if j == f {
137 num_vec[j] = 1;
138 den_vec[j] = 1;
139 } else {
140 num_vec[j] = 0;
141 den_vec[j] = 1;
142 }
143 } else {
144 let pr = pivot_row[j] as usize;
145 let a_pr_j = a_mat[pr][j];
146 let a_pr_f = a_mat[pr][f];
147
148 let mut num = -a_pr_f;
149 let mut den = a_pr_j;
150 if den < 0 {
151 num = -num;
152 den = -den;
153 }
154 let g = math_gcd(num, den);
155 num_vec[j] = num / g;
156 den_vec[j] = den / g;
157 }
158 }
159
160 let mut lcm = 1;
162 for j in 0..work_cols {
163 lcm = math_lcm(lcm, den_vec[j]);
164 }
165
166 let mut int_vec = vec![0; work_cols];
168 for j in 0..work_cols {
169 int_vec[j] = num_vec[j] * (lcm / den_vec[j]);
170 }
171
172 let mut vec_gcd = 0;
174 for j in 0..work_cols {
175 vec_gcd = math_gcd(vec_gcd, int_vec[j]);
176 }
177 if vec_gcd > 1 {
178 for j in 0..work_cols {
179 int_vec[j] /= vec_gcd;
180 }
181 }
182
183 let mut all_non_positive = true;
185 for j in 0..work_cols {
186 if int_vec[j] > 0 {
187 all_non_positive = false;
188 break;
189 }
190 }
191 if all_non_positive {
192 for j in 0..work_cols {
193 int_vec[j] = -int_vec[j];
194 }
195 }
196
197 basis_vectors.push(int_vec);
198 }
199 }
200
201 basis_vectors
202}
203
204pub const MAX_SAFE_INT: i64 = 9_007_199_254_740_991;
205pub const MIN_SAFE_INT: i64 = -9_007_199_254_740_991;
206pub const PINVARIANT_OVERFLOW_CODE: &str = "ERR_PINVARIANT_SAFE_INT_OVERFLOW";
207
208#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
209pub struct PInvariantRangeError {
210 pub code: String,
211 pub step: String,
212 pub message: String,
213}
214
215impl PInvariantRangeError {
216 pub fn new(step: &str, message: impl Into<String>) -> Self {
217 Self {
218 code: PINVARIANT_OVERFLOW_CODE.to_string(),
219 step: step.to_string(),
220 message: message.into(),
221 }
222 }
223}
224
225fn check_safe_i128(val: i128, step: &str) -> Result<i64, PInvariantRangeError> {
226 if val < (MIN_SAFE_INT as i128) || val > (MAX_SAFE_INT as i128) {
227 return Err(PInvariantRangeError::new(
228 step,
229 format!("Value {} exceeds IEEE-754 safe integer bounds", val),
230 ));
231 }
232 Ok(val as i64)
233}
234
235fn math_gcd_i128(mut a: i128, mut b: i128) -> i128 {
236 a = a.abs();
237 b = b.abs();
238 while b > 0 {
239 let t = b;
240 b = a % b;
241 a = t;
242 }
243 a
244}
245
246pub fn normalize_primitive_basis(
251 basis: &[Vec<i64>],
252) -> Result<Vec<Vec<i64>>, PInvariantRangeError> {
253 let mut normalized = Vec::with_capacity(basis.len());
254 for vec in basis {
255 let mut g: i128 = 0;
256 for &v in vec {
257 let _ = check_safe_i128(v as i128, "normalization")?;
258 g = math_gcd_i128(g, v as i128);
259 }
260 let mut out: Vec<i64> = if g > 1 {
261 vec.iter().map(|&v| ((v as i128) / g) as i64).collect()
262 } else {
263 vec.clone()
264 };
265 if let Some(&first_nz) = out.iter().find(|&&x| x != 0) {
266 if first_nz < 0 {
267 for x in &mut out {
268 *x = check_safe_i128(-(*x as i128), "normalization")?;
269 }
270 }
271 }
272 normalized.push(out);
273 }
274 normalized.sort();
275 Ok(normalized)
276}
277
278pub fn solve_nullspace_checked(
280 matrix: &[Vec<i64>],
281 rows: usize,
282 cols: usize,
283 transpose: bool,
284) -> Result<Vec<Vec<i64>>, PInvariantRangeError> {
285 for row in matrix {
286 for &v in row {
287 check_safe_i128(v as i128, "input_validation")?;
288 }
289 }
290
291 let (work_rows, work_cols) = if transpose {
292 (cols, rows)
293 } else {
294 (rows, cols)
295 };
296 if work_rows == 0 || work_cols == 0 {
297 return Ok(Vec::new());
298 }
299
300 let mut a_mat = vec![vec![0i64; work_cols]; work_rows];
301 for r in 0..work_rows {
302 for c in 0..work_cols {
303 let val = if transpose {
304 if c < matrix.len() && r < matrix[c].len() {
305 matrix[c][r]
306 } else {
307 0
308 }
309 } else if r < matrix.len() && c < matrix[r].len() {
310 matrix[r][c]
311 } else {
312 0
313 };
314 a_mat[r][c] = check_safe_i128(val as i128, "input_validation")?;
315 }
316 }
317
318 let mut pivot_row = vec![-1i32; work_cols];
319 let mut is_free = vec![true; work_cols];
320 let mut p = 0usize;
321 let mut c = 0usize;
322
323 while c < work_cols && p < work_rows {
324 let mut pr = p;
325 let mut found = false;
326 while pr < work_rows {
327 if a_mat[pr][c] != 0 {
328 found = true;
329 break;
330 }
331 pr += 1;
332 }
333 if !found {
334 c += 1;
335 continue;
336 }
337 if pr != p {
338 a_mat.swap(p, pr);
339 }
340
341 let pivot = a_mat[p][c] as i128;
342 is_free[c] = false;
343 pivot_row[c] = p as i32;
344
345 for i in 0..work_rows {
346 if i != p {
347 let val_i = a_mat[i][c] as i128;
348 if val_i != 0 {
349 let g = math_gcd_i128(pivot, val_i);
350 let factor_p = check_safe_i128(val_i / g, "row_elimination")? as i128;
351 let factor_i = check_safe_i128(pivot / g, "row_elimination")? as i128;
352
353 for j in 0..work_cols {
354 let term1 = check_safe_i128(factor_i * (a_mat[i][j] as i128), "row_elimination")? as i128;
355 let term2 = check_safe_i128(factor_p * (a_mat[p][j] as i128), "row_elimination")? as i128;
356 a_mat[i][j] = check_safe_i128(term1 - term2, "row_elimination")?;
357 }
358
359 let mut r_gcd: i128 = 0;
360 for j in 0..work_cols {
361 r_gcd = math_gcd_i128(r_gcd, a_mat[i][j] as i128);
362 }
363 if r_gcd > 1 {
364 for j in 0..work_cols {
365 a_mat[i][j] = ((a_mat[i][j] as i128) / r_gcd) as i64;
366 }
367 }
368 }
369 }
370 }
371
372 let mut p_gcd: i128 = 0;
373 for j in 0..work_cols {
374 p_gcd = math_gcd_i128(p_gcd, a_mat[p][j] as i128);
375 }
376 if p_gcd > 1 {
377 for j in 0..work_cols {
378 a_mat[p][j] = ((a_mat[p][j] as i128) / p_gcd) as i64;
379 }
380 }
381
382 p += 1;
383 c += 1;
384 }
385
386 let mut basis_vectors = Vec::new();
387 for f in 0..work_cols {
388 if is_free[f] {
389 let mut num_vec = vec![0i64; work_cols];
390 let mut den_vec = vec![1i64; work_cols];
391
392 for j in 0..work_cols {
393 if is_free[j] {
394 num_vec[j] = if j == f { 1 } else { 0 };
395 den_vec[j] = 1;
396 } else {
397 let pr = pivot_row[j] as usize;
398 let a_pr_j = a_mat[pr][j] as i128;
399 let a_pr_f = a_mat[pr][f] as i128;
400 let mut num = -a_pr_f;
401 let mut den = a_pr_j;
402 if den < 0 {
403 num = -num;
404 den = -den;
405 }
406 let g = math_gcd_i128(num, den);
407 num_vec[j] = check_safe_i128(num / g, "back_substitution")?;
408 den_vec[j] = check_safe_i128(den / g, "back_substitution")?;
409 }
410 }
411
412 let mut lcm: i128 = 1;
413 for j in 0..work_cols {
414 let d = den_vec[j] as i128;
415 if lcm == 0 || d == 0 {
416 lcm = 0;
417 } else {
418 let g = math_gcd_i128(lcm, d);
419 lcm = check_safe_i128(((lcm / g) * d).abs(), "back_substitution")? as i128;
420 }
421 }
422
423 let mut int_vec = vec![0i64; work_cols];
424 for j in 0..work_cols {
425 let mult = lcm / (den_vec[j] as i128);
426 int_vec[j] = check_safe_i128((num_vec[j] as i128) * mult, "back_substitution")?;
427 }
428 basis_vectors.push(int_vec);
429 }
430 }
431
432 normalize_primitive_basis(&basis_vectors)
433}
434
435
436#[path = "solver_precomputed.rs"]
437mod solver_precomputed;
438#[allow(unused_imports)]
439pub use solver_precomputed::*;
440#[cfg(test)]
441#[path = "solver_tests.rs"]
442mod tests;
443