#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) struct Overflow;
pub(crate) type Checked<T> = Result<T, Overflow>;
fn mul(left: i128, right: i128) -> Checked<i128> {
left.checked_mul(right).ok_or(Overflow)
}
fn sub(left: i128, right: i128) -> Checked<i128> {
left.checked_sub(right).ok_or(Overflow)
}
fn add(left: i128, right: i128) -> Checked<i128> {
left.checked_add(right).ok_or(Overflow)
}
fn exact_div(left: i128, right: i128) -> Checked<i128> {
debug_assert_eq!(left.checked_rem(right), Some(0));
left.checked_div(right).ok_or(Overflow)
}
pub(crate) fn determinant(matrix: &[Vec<i128>]) -> Checked<i128> {
let mut rows = matrix.to_vec();
let n = rows.len();
let mut sign = 1;
let mut previous = 1;
for k in 0..n {
let Some(pivot) = (k..n).find(|&row| rows[row][k] != 0) else {
return Ok(0);
};
if pivot != k {
rows.swap(pivot, k);
sign = -sign;
}
bareiss_step(&mut rows, k, previous)?;
previous = rows[k][k];
}
mul(sign, rows.last().map_or(1, |row| row[n - 1]))
}
fn bareiss_step(rows: &mut [Vec<i128>], k: usize, previous: i128) -> Checked<()> {
let (upper, lower) = rows.split_at_mut(k + 1);
let pivot_row = &upper[k];
for row in lower {
for column in k + 1..pivot_row.len() {
let cross = sub(
mul(row[column], pivot_row[k])?,
mul(row[k], pivot_row[column])?,
)?;
row[column] = exact_div(cross, previous)?;
}
}
Ok(())
}
pub(crate) fn invariant_factors(matrix: &[Vec<i128>]) -> Checked<Vec<i128>> {
let mut rows = matrix.to_vec();
let diagonal = (0..rows.len())
.map(|k| clear_cross(&mut rows, k))
.collect::<Checked<Vec<_>>>()?;
divisibility_chain(diagonal)
}
fn clear_cross(rows: &mut [Vec<i128>], k: usize) -> Checked<i128> {
loop {
let Some((row, column)) = smallest_entry(rows, k) else {
return Ok(0);
};
rows.swap(k, row);
for entries in rows.iter_mut() {
entries.swap(k, column);
}
if !reduce_cross(rows, k)? {
return rows[k][k].checked_abs().ok_or(Overflow);
}
}
}
fn smallest_entry(rows: &[Vec<i128>], k: usize) -> Option<(usize, usize)> {
(k..rows.len())
.flat_map(|row| (k..rows.len()).map(move |column| (row, column)))
.filter(|&(row, column)| rows[row][column] != 0)
.min_by_key(|&(row, column)| rows[row][column].unsigned_abs())
}
fn reduce_cross(rows: &mut [Vec<i128>], k: usize) -> Checked<bool> {
Ok(reduce_column(rows, k)? | reduce_row(rows, k)?)
}
fn reduce_column(rows: &mut [Vec<i128>], k: usize) -> Checked<bool> {
let (upper, lower) = rows.split_at_mut(k + 1);
let pivot_row = &upper[k];
let mut remainder = false;
for row in lower {
let quotient = row[k].checked_div(pivot_row[k]).ok_or(Overflow)?;
for (entry, &above) in row[k..].iter_mut().zip(&pivot_row[k..]) {
*entry = sub(*entry, mul(quotient, above)?)?;
}
remainder |= row[k] != 0;
}
Ok(remainder)
}
fn reduce_row(rows: &mut [Vec<i128>], k: usize) -> Checked<bool> {
let mut remainder = false;
for column in k + 1..rows.len() {
let quotient = rows[k][column].checked_div(rows[k][k]).ok_or(Overflow)?;
for entries in rows[k..].iter_mut() {
entries[column] = sub(entries[column], mul(quotient, entries[k])?)?;
}
remainder |= rows[k][column] != 0;
}
Ok(remainder)
}
fn divisibility_chain(mut diagonal: Vec<i128>) -> Checked<Vec<i128>> {
for first in 0..diagonal.len() {
for second in first + 1..diagonal.len() {
let divisor = gcd(diagonal[first], diagonal[second]);
if divisor != 0 {
diagonal[second] = mul(diagonal[first] / divisor, diagonal[second])?;
diagonal[first] = divisor;
}
}
}
Ok(diagonal)
}
fn gcd(mut left: i128, mut right: i128) -> i128 {
while right != 0 {
(left, right) = (right, left % right);
}
left
}
pub(crate) fn pencil(matrix: &[Vec<i128>]) -> Checked<Vec<i128>> {
let n = matrix.len();
let mut differences = (0..=n)
.map(|point| determinant(&with_transpose(matrix, point as i128, 1)?))
.collect::<Checked<Vec<_>>>()?;
for order in 1..=n {
for node in (order..=n).rev() {
let step = sub(differences[node], differences[node - 1])?;
differences[node] = exact_div(step, order as i128)?;
}
}
let mut coefficients = newton_to_monomial(&differences)?;
while coefficients.last() == Some(&0) {
coefficients.pop();
}
Ok(coefficients)
}
pub(crate) fn with_transpose(
matrix: &[Vec<i128>],
scale: i128,
transpose_scale: i128,
) -> Checked<Vec<Vec<i128>>> {
(0..matrix.len())
.map(|row| {
(0..matrix.len())
.map(|column| {
add(
mul(scale, matrix[row][column])?,
mul(transpose_scale, matrix[column][row])?,
)
})
.collect()
})
.collect()
}
fn newton_to_monomial(newton: &[i128]) -> Checked<Vec<i128>> {
let mut coefficients = vec![newton[newton.len() - 1]];
for node in (0..newton.len() - 1).rev() {
let mut next = vec![0; coefficients.len() + 1];
for (degree, &value) in coefficients.iter().enumerate() {
next[degree + 1] = add(next[degree + 1], value)?;
next[degree] = sub(next[degree], mul(node as i128, value)?)?;
}
next[0] = add(next[0], newton[node])?;
coefficients = next;
}
Ok(coefficients)
}