#![allow(
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
clippy::cast_possible_wrap
)]
use std::collections::BTreeMap;
use crate::coeff::{Field, Integral, Plethystic, QAlgebra, Ring};
pub type Atom = (u32, u32);
pub type Linears = BTreeMap<(u32, u32), i32>;
#[derive(Clone, Debug)]
pub struct AFrac<C: Integral> {
num: Vec<C>,
den: BTreeMap<Atom, u32>,
tail: Vec<C>,
scale: u128,
}
fn gcd32(mut a: u32, mut b: u32) -> u32 {
while b != 0 {
let t = a % b;
a = b;
b = t;
}
a
}
fn split(u: u32, v: u32) -> (u128, Option<Atom>) {
assert!(u > 0 || v > 0, "0·α + 0 is zero");
let g = gcd32(u, v);
if u == 0 {
(g as u128, None) } else {
(g as u128, Some((u / g, v / g)))
}
}
const TRIAL_BOUND: u128 = 1 << 10;
fn pmul<C: Integral>(a: &[C], b: &[C]) -> Vec<C> {
if a.is_empty() || b.is_empty() {
return Vec::new();
}
let mut out = vec![C::zero(); a.len() + b.len() - 1];
for (i, x) in a.iter().enumerate() {
if x.is_zero() {
continue;
}
for (j, y) in b.iter().enumerate() {
let t = x.mul(y);
out[i + j].add_assign(&t);
}
}
trim(&mut out);
out
}
fn pscale<C: Integral>(a: &[C], c: &C) -> Vec<C> {
if c.is_zero() {
return Vec::new();
}
a.iter().map(|x| x.mul(c)).collect()
}
fn pdiv_exact<C: Integral>(a: &[C], c: &C) -> Vec<C> {
a.iter()
.map(|x| {
x.div_exact(c)
.expect("a content divides the coefficients it was taken from")
})
.collect()
}
fn content<C: Integral>(a: &[C]) -> C {
let mut g = C::zero();
for c in a {
g = g.gcd(c);
}
g
}
fn primitive<C: Integral>(a: &[C]) -> Vec<C> {
if a.is_empty() {
return Vec::new();
}
let g = content(a);
let mut out = pdiv_exact(a, &g);
if out[out.len() - 1].is_negative() {
out = out.iter().map(C::neg).collect();
}
out
}
fn prem<C: Integral>(a: &[C], b: &[C]) -> Vec<C> {
assert!(!b.is_empty(), "pseudo-division by the zero polynomial");
if a.len() < b.len() {
return a.to_vec();
}
let lc = b[b.len() - 1].clone();
let mut r = a.to_vec();
while r.len() >= b.len() && !r.is_empty() {
let shift = r.len() - b.len();
let factor = r[r.len() - 1].clone();
r = pscale(&r, &lc);
for (i, y) in b.iter().enumerate() {
let t = y.mul(&factor).neg();
r[shift + i].add_assign(&t);
}
trim(&mut r);
if !r.is_empty() {
r = primitive(&r);
}
}
r
}
fn pgcd<C: Integral>(a: &[C], b: &[C]) -> Vec<C> {
if a.is_empty() && b.is_empty() {
return vec![C::one()];
}
if a.is_empty() {
return primitive(b);
}
if b.is_empty() {
return primitive(a);
}
let (mut x, mut y) = (primitive(a), primitive(b));
if x.len() < y.len() {
core::mem::swap(&mut x, &mut y);
}
while !y.is_empty() {
let r = prem(&x, &y);
x = y;
y = if r.is_empty() { r } else { primitive(&r) };
}
primitive(&x)
}
fn divide_exact<C: Integral>(a: &[C], b: &[C]) -> Vec<C> {
assert!(!b.is_empty(), "exact division by the zero polynomial");
if a.is_empty() {
return Vec::new();
}
let lc = b[b.len() - 1].clone();
let mut r = a.to_vec();
let mut q = vec![C::zero(); a.len() - b.len() + 1];
while r.len() >= b.len() && !r.is_empty() {
let shift = r.len() - b.len();
let factor = r[r.len() - 1]
.div_exact(&lc)
.expect("a gcd's leading coefficient divides the quotient's");
q[shift] = factor.clone();
for (i, y) in b.iter().enumerate() {
let t = y.mul(&factor).neg();
r[shift + i].add_assign(&t);
}
trim(&mut r);
}
assert!(r.is_empty(), "an exact division left a remainder");
trim(&mut q);
q
}
fn mul_tails<C: Integral>(a: &[C], b: &[C]) -> Vec<C> {
if a.is_empty() {
return b.to_vec();
}
if b.is_empty() {
return a.to_vec();
}
pmul(a, b)
}
fn tail_lcm<C: Integral>(a: &[C], b: &[C]) -> (Vec<C>, Vec<C>, Vec<C>) {
if a == b {
return (Vec::new(), Vec::new(), a.to_vec());
}
if a.is_empty() {
return (b.to_vec(), Vec::new(), b.to_vec());
}
if b.is_empty() {
return (Vec::new(), a.to_vec(), a.to_vec());
}
let g = pgcd(a, b);
let for_a = divide_exact(b, &g);
let for_b = divide_exact(a, &g);
let lcm = pmul(a, &for_a);
(for_a, for_b, lcm)
}
fn trim<C: Ring>(v: &mut Vec<C>) {
while v.last().is_some_and(C::is_zero) {
v.pop();
}
}
fn mul_linear_in_place<C: Ring>(p: &mut Vec<C>, u: u32, v: u32) {
if p.is_empty() {
return;
}
let (cu, cv) = (C::from_u128(u as u128), C::from_u128(v as u128));
p.push(C::zero());
for k in (0..p.len()).rev() {
let hi = if k > 0 { p[k - 1].mul(&cu) } else { C::zero() };
let mut lo = p[k].mul(&cv);
lo.add_assign(&hi);
p[k] = lo;
}
trim(p);
}
fn mul_linear<C: Ring>(p: &[C], u: u32, v: u32) -> Vec<C> {
let mut out = p.to_vec();
mul_linear_in_place(&mut out, u, v);
out
}
#[allow(dead_code)]
pub(crate) fn divide_by_linear<C: Ring>(p: &[C], u: u32, v: u32) -> Option<Vec<C>> {
let mut num = p.to_vec();
divide_in_place(&mut num, u, v).then_some(num)
}
fn divides_by_linear<C: Ring>(p: &[C], u: u32, v: u32) -> bool {
debug_assert!(gcd32(u, v) == 1 && u > 0, "divisor must be primitive in α");
let d = p.len() - 1;
let cu = C::from_u128(u as u128);
let cv = C::from_u128(v as u128);
let Some(mut q) = p[d].div_exact(&cu) else {
return false;
};
for i in (1..d).rev() {
let mut r = p[i].clone();
r.sub_assign(&q.mul(&cv));
match r.div_exact(&cu) {
Some(next) => q = next,
None => return false,
}
}
let mut r = p[0].clone();
r.sub_assign(&q.mul(&cv));
r.is_zero()
}
fn divide_in_place<C: Ring>(num: &mut Vec<C>, u: u32, v: u32) -> bool {
if num.is_empty() {
return true; }
if num.len() == 1 {
return false; }
if !divides_by_linear(num, u, v) {
return false;
}
let cu = C::from_u128(u as u128);
let cv = C::from_u128(v as u128);
let d = num.len() - 1;
num[d] = num[d]
.div_exact(&cu)
.expect("divisibility was just established");
for i in (1..d).rev() {
let back = num[i + 1].mul(&cv);
let mut r = num[i].clone();
r.sub_assign(&back);
num[i] = r.div_exact(&cu).expect("divisibility was just established");
}
num.remove(0);
trim(num);
true
}
impl<C: Integral + 'static> crate::memo::HeapSize for AFrac<C> {
fn heap_bytes(&self) -> usize {
let coeffs = |v: &Vec<C>| {
v.capacity() * std::mem::size_of::<C>()
+ v.iter().map(crate::memo::coeff_heap_bytes).sum::<usize>()
};
coeffs(&self.num) + coeffs(&self.tail) + crate::memo::HeapSize::heap_bytes(&self.den)
}
}
impl<C: Integral> AFrac<C> {
pub fn from_coeffs(mut num: Vec<C>) -> Self {
trim(&mut num);
AFrac {
num,
den: BTreeMap::new(),
tail: Vec::new(),
scale: 1,
}
}
pub fn linear(u: u32, v: u32) -> Self {
Self::from_coeffs(vec![C::from_u128(v as u128), C::from_u128(u as u128)])
}
pub fn inv_linear(u: u32, v: u32) -> Self {
let (content, atom) = split(u, v);
let mut den = BTreeMap::new();
if let Some(a) = atom {
den.insert(a, 1);
}
AFrac {
num: vec![C::one()],
den,
tail: Vec::new(),
scale: content,
}
}
pub fn from_factors(factors: &Linears) -> Self {
<Self as Ring>::one().mul_factors(factors)
}
pub fn mul_factors(&self, factors: &Linears) -> Self {
let mut out = self.clone();
for (&(u, v), &m) in factors {
if m == 0 {
continue;
}
let (content, atom) = split(u, v);
let reps = m.unsigned_abs();
if m > 0 {
for _ in 0..reps {
out.scale_content(content);
if let Some((au, av)) = atom {
out.num = mul_linear(&out.num, au, av);
}
}
} else {
for _ in 0..reps {
out.scale *= content;
if let Some(a) = atom {
*out.den.entry(a).or_insert(0) += 1;
}
}
}
}
out
}
pub fn div_linear(&self, u: u32, v: u32) -> Self {
let (content, atom) = split(u, v);
let mut out = self.clone();
out.scale *= content;
if let Some(a) = atom {
*out.den.entry(a).or_insert(0) += 1;
out.reduce_at(a);
}
out.content_reduce();
out
}
pub fn scale_int(&self, k: i64) -> Self {
if k == 0 {
return <Self as Ring>::zero();
}
let c = C::from_i64(k);
let mut out = self.clone();
for x in &mut out.num {
*x = x.mul(&c);
}
trim(&mut out.num);
out.content_reduce();
out
}
pub fn div_int(&self, k: u128) -> Self {
assert!(k != 0, "division by zero");
let mut out = self.clone();
out.scale *= k;
out.content_reduce();
out
}
fn scale_content(&mut self, k: u128) {
if k == 1 {
return;
}
let g = crate::coeff::gcd_u128(self.scale, k);
self.scale /= g;
let rest = k / g;
if rest != 1 {
let c = C::from_u128(rest);
for x in &mut self.num {
*x = x.mul(&c);
}
trim(&mut self.num);
}
}
pub fn reduce(&mut self) {
if self.num.is_empty() {
self.den.clear();
self.tail.clear();
self.scale = 1;
return;
}
let atoms: Vec<Atom> = self.den.keys().copied().collect();
for a in atoms {
self.reduce_at(a);
}
self.reduce_tail();
self.content_reduce();
}
fn reduce_tail(&mut self) {
if self.tail.is_empty() {
return;
}
let g = pgcd(&self.num, &self.tail);
if g.len() > 1 {
self.num = divide_exact(&self.num, &g);
self.tail = divide_exact(&self.tail, &g);
}
if self.tail[self.tail.len() - 1].is_negative() {
self.tail = self.tail.iter().map(C::neg).collect();
self.num = self.num.iter().map(C::neg).collect();
}
if self.tail.len() == 1 {
self.tail.clear();
}
}
fn reduce_at(&mut self, atom: Atom) {
let (u, v) = atom;
while let Some(&m) = self.den.get(&atom) {
if m == 0 || self.num.is_empty() || !divide_in_place(&mut self.num, u, v) {
break;
}
if m == 1 {
self.den.remove(&atom);
} else {
self.den.insert(atom, m - 1);
}
}
}
fn content_reduce(&mut self) {
if self.scale == 1 || self.num.is_empty() {
return;
}
let mut residue = self.scale;
let mut p = 2u128;
while p < TRIAL_BOUND && p * p <= residue {
if residue.is_multiple_of(p) {
while residue.is_multiple_of(p) {
residue /= p;
}
self.cancel_scalar(p);
}
p += if p == 2 { 1 } else { 2 };
}
if residue > 1 {
self.cancel_scalar(residue);
}
}
fn cancel_scalar(&mut self, p: u128) {
let d = C::from_u128(p);
while self.scale.is_multiple_of(p) {
let q: Option<Vec<C>> = self.num.iter().map(|x| x.div_exact(&d)).collect();
match q {
Some(q) => {
self.num = q;
self.scale /= p;
}
None => return,
}
}
}
pub fn parts(&self) -> (&[C], impl Iterator<Item = (&Atom, &u32)>, u128) {
(&self.num, self.den.iter(), self.scale)
}
pub fn div_tail(&self, tail: &[C]) -> Self {
assert!(
!tail.iter().all(C::is_zero),
"a zero denominator in Q(alpha)"
);
let mut out = self.clone();
out.tail = mul_tails(&out.tail, tail);
out.reduce();
out
}
pub fn tail(&self) -> &[C] {
&self.tail
}
pub fn into_poly(mut self) -> Option<Vec<C>> {
self.reduce();
if !self.den.is_empty() || !self.tail.is_empty() {
return None;
}
if self.scale == 1 {
return Some(self.num);
}
let d = C::from_u128(self.scale);
self.num.iter().map(|x| x.div_exact(&d)).collect()
}
pub fn into_rational_poly(mut self) -> Option<(Vec<C>, u128)> {
self.reduce();
(self.den.is_empty() && self.tail.is_empty()).then_some((self.num, self.scale))
}
pub fn invert_alpha(&self) -> Self {
assert!(
self.tail.is_empty(),
"alpha-inversion is written for the factored denominator only"
);
if self.num.is_empty() {
return <Self as Ring>::zero();
}
let degree = self.num.len() - 1;
let mult: u32 = self.den.values().sum();
let mut num: Vec<C> = self.num.iter().rev().cloned().collect();
let mut den: BTreeMap<Atom, u32> = BTreeMap::new();
let mut scale = self.scale;
for (&(u, v), &m) in &self.den {
let (content, atom) = split(v, u);
match atom {
Some(a) => *den.entry(a).or_insert(0) += m,
None => {
debug_assert_eq!(content, 1, "a primitive atom's swap has unit content");
}
}
}
let shift = mult as i64 - degree as i64;
match shift.cmp(&0) {
core::cmp::Ordering::Greater => {
let mut shifted = vec![C::zero(); shift as usize];
shifted.append(&mut num);
num = shifted;
}
core::cmp::Ordering::Less => {
*den.entry((1, 0)).or_insert(0) += (-shift) as u32;
}
core::cmp::Ordering::Equal => {}
}
trim(&mut num);
let mut out = AFrac {
num,
den,
tail: Vec::new(),
scale: 1,
};
out.scale = core::mem::replace(&mut scale, 1);
out.reduce();
out
}
pub fn degree(&self) -> Option<usize> {
(!self.num.is_empty()).then(|| self.num.len() - 1)
}
fn lift(&self, target: &BTreeMap<Atom, u32>, scale: u128, tail_extra: &[C]) -> Vec<C> {
let mut num = self.num.clone();
for (&(u, v), &m) in target {
let extra = m - self.den.get(&(u, v)).copied().unwrap_or(0);
for _ in 0..extra {
mul_linear_in_place(&mut num, u, v);
}
}
let k = scale / self.scale;
if k != 1 {
let c = C::from_u128(k);
for x in &mut num {
*x = x.mul(&c);
}
trim(&mut num);
}
if !tail_extra.is_empty() {
num = pmul(&num, tail_extra);
}
num
}
}
impl AFrac<i128> {
pub fn eval_i128(&self, alpha: &crate::coeff::Rational) -> Option<crate::coeff::Rational> {
use crate::coeff::{Field, Rational};
let (num, den, scale) = self.parts();
if num.is_empty() {
return Some(Rational::zero());
}
let mut acc = Rational::zero();
for c in num.iter().rev() {
acc = acc.mul(alpha);
acc.add_assign(&Rational::from_i128(*c));
}
let mut d = Rational::from_u128(scale);
for (&(u, v), &m) in den {
let mut f = Rational::from_u128(u as u128).mul(alpha);
f.add_assign(&Rational::from_u128(v as u128));
if f.is_zero() {
return None;
}
for _ in 0..m {
d = d.mul(&f);
}
}
if !self.tail.is_empty() {
let mut t = Rational::zero();
for c in self.tail.iter().rev() {
t = t.mul(alpha);
t.add_assign(&Rational::from_i128(*c));
}
if t.is_zero() {
return None;
}
d = d.mul(&t);
}
Some(acc.div(&d))
}
pub fn into_natural_poly(self) -> Option<Vec<i128>> {
let coeffs = self.into_poly()?;
coeffs.iter().all(|&c| c >= 0).then_some(coeffs)
}
}
impl<C: Integral + Field> AFrac<C> {
pub fn eval(&self, alpha: &C) -> Option<C> {
if self.num.is_empty() {
return Some(C::zero());
}
let mut d = C::from_u128(self.scale);
for (&(u, v), &m) in &self.den {
let mut f = C::from_u128(u as u128).mul(alpha);
f.add_assign(&C::from_u128(v as u128));
if f.is_zero() {
return None;
}
for _ in 0..m {
d = d.mul(&f);
}
}
let horner = |p: &[C]| {
let mut acc = C::zero();
for c in p.iter().rev() {
acc = acc.mul(alpha);
acc.add_assign(c);
}
acc
};
if !self.tail.is_empty() {
let t = horner(&self.tail);
if t.is_zero() {
return None;
}
d = d.mul(&t);
}
Some(horner(&self.num).div(&d))
}
}
impl<C: Integral> PartialEq for AFrac<C> {
fn eq(&self, other: &Self) -> bool {
if self.num.is_empty() || other.num.is_empty() {
return self.num.is_empty() && other.num.is_empty();
}
if self.den == other.den && self.scale == other.scale && self.tail == other.tail {
return self.num == other.num;
}
let mut lcm = self.den.clone();
for (k, &m) in &other.den {
let e = lcm.entry(*k).or_insert(0);
*e = (*e).max(m);
}
let g = crate::coeff::gcd_u128(self.scale, other.scale);
let s = self.scale / g * other.scale;
self.lift(&lcm, s, &other.tail) == other.lift(&lcm, s, &self.tail)
}
}
impl<C: Integral> Eq for AFrac<C> {}
crate::coeff::impl_ring_ops!([C: Integral] AFrac<C>);
impl<C: Integral> Ring for AFrac<C> {
fn zero() -> Self {
AFrac {
num: Vec::new(),
den: BTreeMap::new(),
tail: Vec::new(),
scale: 1,
}
}
fn one() -> Self {
AFrac {
num: vec![C::one()],
den: BTreeMap::new(),
tail: Vec::new(),
scale: 1,
}
}
fn is_zero(&self) -> bool {
self.num.is_empty()
}
fn add_assign(&mut self, other: &Self) {
if other.is_zero() {
return;
}
if self.is_zero() {
*self = other.clone();
return;
}
let needs_atoms = other
.den
.iter()
.any(|(k, &m)| self.den.get(k).copied().unwrap_or(0) < m);
let needs_scale = !self.scale.is_multiple_of(other.scale);
let (mine, theirs, common) = tail_lcm(&self.tail, &other.tail);
if needs_atoms || needs_scale || !mine.is_empty() {
let mut lcm = self.den.clone();
for (k, &m) in &other.den {
let e = lcm.entry(*k).or_insert(0);
*e = (*e).max(m);
}
let g = crate::coeff::gcd_u128(self.scale, other.scale);
let s = self.scale / g * other.scale;
self.num = self.lift(&lcm, s, &mine);
self.den = lcm;
self.scale = s;
self.tail = common;
}
let lifted = other.lift(&self.den, self.scale, &theirs);
if self.num.len() < lifted.len() {
self.num.resize(lifted.len(), C::zero());
}
for (x, y) in self.num.iter_mut().zip(lifted.iter()) {
x.add_assign(y);
}
trim(&mut self.num);
}
fn mul(&self, other: &Self) -> Self {
if self.is_zero() || other.is_zero() {
return Self::zero();
}
let mut num = vec![C::zero(); self.num.len() + other.num.len() - 1];
for (i, a) in self.num.iter().enumerate() {
if a.is_zero() {
continue;
}
for (j, b) in other.num.iter().enumerate() {
let v = a.mul(b);
num[i + j].add_assign(&v);
}
}
trim(&mut num);
let mut den = self.den.clone();
for (k, &m) in &other.den {
*den.entry(*k).or_insert(0) += m;
}
let mut f = AFrac {
num,
den,
tail: mul_tails(&self.tail, &other.tail),
scale: self.scale * other.scale,
};
f.reduce();
f
}
fn neg(&self) -> Self {
AFrac {
num: self.num.iter().map(C::neg).collect(),
den: self.den.clone(),
tail: self.tail.clone(),
scale: self.scale,
}
}
fn from_i64(n: i64) -> Self {
Self::from_coeffs(vec![C::from_i64(n)])
}
fn from_u128(n: u128) -> Self {
Self::from_coeffs(vec![C::from_u128(n)])
}
fn from_i128(n: i128) -> Self {
Self::from_coeffs(vec![C::from_i128(n)])
}
fn try_from_u128(n: u128) -> Option<Self> {
C::try_from_u128(n).map(|c| Self::from_coeffs(vec![c]))
}
fn try_from_i128(n: i128) -> Option<Self> {
C::try_from_i128(n).map(|c| Self::from_coeffs(vec![c]))
}
}
impl<C: Integral> QAlgebra for AFrac<C> {
fn div_u128(&self, n: u128) -> Self {
assert!(n != 0, "division of AFrac by zero");
let mut out = self.clone();
out.scale *= n;
out.content_reduce();
out
}
}
fn nth_root(k: u32, n: u32) -> Option<u32> {
if n == 1 {
return Some(k);
}
let mut r = 0u32;
while r.pow(n) < k {
r += 1;
}
(r.pow(n) == k).then_some(r)
}
fn raise_atom<C: Integral>(u: u32, v: u32, n: u32) -> (Vec<(Atom, u32)>, Vec<C>) {
if v == 0 {
debug_assert_eq!(u, 1, "a primitive atom with no constant term is alpha");
return (vec![((1, 0), n)], Vec::new());
}
let mut raised = vec![C::zero(); n as usize + 1];
raised[0] = C::from_u128(v as u128);
raised[n as usize] = C::from_u128(u as u128);
if n.is_multiple_of(2) {
return (Vec::new(), raised);
}
let (Some(t), Some(s)) = (nth_root(u, n), nth_root(v, n)) else {
return (Vec::new(), raised);
};
let cofactor = divide_by_linear(&raised, t, s)
.expect("t*alpha + s divides u*alpha^n + v when t^n = u and s^n = v");
(vec![((t, s), 1)], cofactor)
}
impl<C: Integral> Plethystic for AFrac<C> {
fn frobenius(&self, n: u32) -> Self {
assert!(
n > 0,
"the plethystic Frobenius needs n >= 1: p_0 does not raise variables"
);
if n == 1 || self.is_zero() {
return self.clone();
}
let spread = |p: &[C]| {
if p.is_empty() {
return Vec::new();
}
let mut out = vec![C::zero(); (p.len() - 1) * n as usize + 1];
for (k, c) in p.iter().enumerate() {
out[k * n as usize] = c.clone();
}
out
};
let mut den: BTreeMap<Atom, u32> = BTreeMap::new();
let mut tail = spread(&self.tail);
for (&(u, v), &m) in &self.den {
let (atoms, rest) = raise_atom::<C>(u, v, n);
for (a, k) in atoms {
*den.entry(a).or_insert(0) += k * m;
}
for _ in 0..m {
tail = mul_tails(&tail, &rest);
}
}
let mut out = AFrac {
num: spread(&self.num),
den,
tail,
scale: self.scale,
};
out.reduce();
out
}
}
impl<C: Integral> core::fmt::Display for AFrac<C> {
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
if self.num.is_empty() {
return f.write_str("0");
}
let mut first = true;
f.write_str("(")?;
for (k, c) in self.num.iter().enumerate() {
if c.is_zero() {
continue;
}
if !first {
f.write_str(" + ")?;
}
first = false;
match k {
0 => write!(f, "{c:?}")?,
1 => write!(f, "{c:?}a")?,
_ => write!(f, "{c:?}a^{k}")?,
}
}
f.write_str(")")?;
if self.scale != 1 {
write!(f, "/{}", self.scale)?;
}
for (&(u, v), &m) in &self.den {
match (u, v) {
(1, 0) => f.write_str("/(a)")?,
(1, _) => write!(f, "/(a+{v})")?,
(_, 0) => write!(f, "/({u}a)")?,
_ => write!(f, "/({u}a+{v})")?,
}
if m > 1 {
write!(f, "^{m}")?;
}
}
if !self.tail.is_empty() {
f.write_str("/(")?;
let mut first = true;
for (k, c) in self.tail.iter().enumerate() {
if c.is_zero() {
continue;
}
if !first {
f.write_str("+")?;
}
first = false;
match k {
0 => write!(f, "{c:?}")?,
1 => write!(f, "{c:?}a")?,
_ => write!(f, "{c:?}a^{k}")?,
}
}
f.write_str(")")?;
}
Ok(())
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::coeff::Rational;
fn r(n: i128) -> Rational {
Rational::from_int(n)
}
#[test]
fn frobenius_raises_alpha_and_the_tail_catches_what_leaves() {
type F = AFrac<i128>;
let a = F::inv_linear(1, 1); let two = a.frobenius(2);
assert_eq!(two.parts().1.count(), 0, "alpha^2 + 1 has no linear factor");
assert_eq!(two.tail(), &[1, 0, 1], "1/(alpha^2 + 1)");
assert_eq!(a.frobenius(1), a, "n = 1 is the identity");
let three = a.frobenius(3);
let atoms: Vec<_> = three.parts().1.map(|(a, &m)| (*a, m)).collect();
assert_eq!(atoms, vec![((1, 1), 1)]);
assert_eq!(three.tail(), &[1, -1, 1]);
let over_alpha = F::inv_linear(1, 0);
let cubed = over_alpha.frobenius(3);
let atoms: Vec<_> = cubed.parts().1.map(|(a, &m)| (*a, m)).collect();
assert_eq!(atoms, vec![((1, 0), 3)], "1/alpha^3");
assert!(cubed.tail().is_empty());
}
#[test]
fn frobenius_is_a_ring_homomorphism() {
type F = AFrac<i128>;
let a = F::inv_linear(1, 1);
let b = F::from_coeffs(vec![0, 1]).div_linear(1, 2); for n in 1..5 {
assert_eq!(
a.mul(&b).frobenius(n),
a.frobenius(n).mul(&b.frobenius(n)),
"multiplicative at n = {n}"
);
let mut sum = a.clone();
sum.add_assign(&b);
sum.reduce();
let mut raised = a.frobenius(n);
raised.add_assign(&b.frobenius(n));
raised.reduce();
assert_eq!(sum.frobenius(n), raised, "additive at n = {n}");
}
}
#[test]
fn a_tail_cancels_against_the_numerator() {
type F = AFrac<i128>;
let tailed = F::inv_linear(1, 1).frobenius(2); let mut whole = tailed.mul(&F::from_coeffs(vec![1, 0, 1])); whole.reduce();
assert_eq!(whole, <F as Ring>::one(), "the tail divides out");
assert!(whole.tail().is_empty());
let mut doubled = tailed.clone();
doubled.add_assign(&tailed);
doubled.reduce();
assert_eq!(doubled.tail(), &[1, 0, 1]);
assert_eq!(doubled, tailed.scale_int(2));
assert_eq!(
tailed.eval_i128(&r(1)),
Some(Rational::new(1, 2)),
"at alpha = 1"
);
}
#[test]
fn atoms_normalize_to_primitive_forms() {
assert_eq!(split(0, 5), (5, None), "0·α + 5 is the constant 5");
assert_eq!(split(3, 0), (3, Some((1, 0))), "3α = 3 · α");
assert_eq!(split(2, 4), (2, Some((1, 2))), "2α + 4 = 2 · (α + 2)");
assert_eq!(split(3, 2), (1, Some((3, 2))), "already primitive");
}
#[test]
fn dividing_by_a_non_primitive_form_stays_integral() {
let f: AFrac<i128> = AFrac::linear(2, 4);
let q = f.div_linear(2, 4);
assert_eq!(q, <AFrac<i128> as Ring>::one(), "{q}");
let half: AFrac<i128> = <AFrac<i128> as Ring>::one().div_linear(2, 4);
let (num, _, scale) = half.parts();
assert_eq!(scale, 2, "the content lives in the scalar: {half}");
assert_eq!(num, &[1i128]);
}
#[test]
fn exact_division_by_a_linear_form() {
let p = vec![2i128, 3, 1];
let q = divide_by_linear(&p, 1, 1).expect("(α+1) divides it");
assert_eq!(q, vec![2i128, 1], "α + 2");
assert!(divide_by_linear(&p, 1, 3).is_none(), "(α+3) does not");
assert!(divide_by_linear(&p, 2, 1).is_none());
}
#[test]
fn division_by_alpha() {
let p = vec![0i128, 3, 1]; assert_eq!(divide_by_linear(&p, 1, 0), Some(vec![3i128, 1]));
let q = vec![1i128, 3, 1]; assert_eq!(divide_by_linear(&q, 1, 0), None);
}
#[test]
fn round_trip_through_every_atom() {
for p in [vec![1i128], vec![2, 3, 1], vec![0, 0, 5], vec![-7, 4]] {
for (u, v) in [(1u32, 0u32), (1, 1), (1, 5), (2, 1), (3, 2)] {
let prod = mul_linear(&p, u, v);
let back = divide_by_linear(&prod, u, v)
.unwrap_or_else(|| panic!("({u}α+{v}) must divide its own multiple"));
assert_eq!(back, p, "round trip through {u}α+{v}");
}
}
}
#[test]
fn ring_axioms_hold() {
type F = AFrac<Rational>;
let a = F::inv_linear(1, 1); let b = F::inv_linear(1, 2); let one = <F as Ring>::one();
assert_eq!(a.mul(&one), a);
assert_eq!(a.mul(&b), b.mul(&a));
let mut z = a.clone();
z.add_assign(&a.neg());
assert!(z.is_zero());
assert_eq!(z, <F as Ring>::zero());
let mut sum = a.clone();
sum.add_assign(&b);
let mut want = a.mul(&b);
want.add_assign(&b.mul(&b));
assert_eq!(sum.mul(&b), want);
}
#[test]
fn addition_uses_the_exact_lcm() {
type F = AFrac<Rational>;
let mut s = F::inv_linear(1, 1);
s.add_assign(&F::inv_linear(1, 1));
let (num, den, scale) = s.parts();
assert_eq!(num, &[r(2)]);
assert_eq!(scale, 1);
assert_eq!(den.collect::<Vec<_>>(), vec![(&(1, 1), &1)], "{s}");
}
#[test]
fn addition_over_two_atoms() {
type F = AFrac<Rational>;
let mut s = F::inv_linear(1, 1);
s.add_assign(&F::inv_linear(1, 2));
assert_eq!(s.eval(&r(3)), Some(Rational::new(9, 20)), "{s}");
let (num, _, _) = s.parts();
assert_eq!(num, &[r(3), r(2)]);
}
#[test]
fn reduction_cancels_and_into_poly_answers_about_the_element() {
type F = AFrac<i128>;
let f = F::from_coeffs(vec![2, 3, 1]).div_linear(1, 1);
assert_eq!(f.clone().into_poly(), Some(vec![2i128, 1]), "{f}");
assert_eq!(F::inv_linear(1, 1).into_poly(), None);
assert_eq!(F::from_coeffs(vec![1]).div_linear(0, 2).into_poly(), None);
let g: AFrac<Rational> = AFrac::from_coeffs(vec![r(1)]).div_linear(0, 2);
assert_eq!(g.into_poly(), Some(vec![Rational::new(1, 2)]));
}
#[test]
fn equality_survives_an_unnormalized_content() {
type F = AFrac<Rational>;
let a = F::from_coeffs(vec![r(1)]).div_linear(0, 2); let b = F::from_coeffs(vec![r(3)]).div_linear(0, 6); assert_eq!(a, b, "{a} vs {b}");
let c: AFrac<i128> = AFrac::from_coeffs(vec![1]).div_linear(0, 2);
let d: AFrac<i128> = AFrac::from_coeffs(vec![3]).div_linear(0, 6);
assert_eq!(c, d, "{c} vs {d}");
}
#[test]
fn factors_multiply_and_cancel_before_expanding() {
type F = AFrac<Rational>;
let mut f: Linears = Linears::new();
f.insert((1, 2), 1); f.insert((0, 3), 1); f.insert((2, 1), -1); let v = F::from_factors(&f);
assert_eq!(v.eval(&r(1)), Some(r(3)), "{v}");
let inv: Linears = f.iter().map(|(&k, &m)| (k, -m)).collect();
let one = v.mul_factors(&inv);
assert_eq!(one, <F as Ring>::one(), "{one}");
}
#[test]
fn division_by_integers_is_exact_over_a_non_qalgebra() {
type F = AFrac<i128>;
let f = <F as Ring>::from_i64(6).div_u128(4);
assert_eq!(f.eval_rational(), (vec![3i128], 2));
}
impl AFrac<i128> {
fn eval_rational(mut self) -> (Vec<i128>, u128) {
self.reduce();
assert!(self.den.is_empty());
(self.num, self.scale)
}
}
#[test]
fn alpha_inversion_is_an_involution() {
type F = AFrac<Rational>;
let cases = [
F::from_coeffs(vec![r(2), r(3), r(1)]), F::inv_linear(1, 1), F::inv_linear(1, 0), F::linear(3, 2).div_linear(2, 5), F::from_coeffs(vec![r(7)]).div_linear(0, 3), ];
for f in &cases {
let back = f.invert_alpha().invert_alpha();
assert_eq!(
&back,
f,
"involution: {f} -> {} -> {back}",
f.invert_alpha()
);
for &x in &[2i128, 3, 5] {
let want = f.eval(&Rational::new(1, x));
let got = f.invert_alpha().eval(&r(x));
assert_eq!(got, want, "{f} at α = 1/{x}");
}
}
}
#[test]
fn inverting_alpha_can_remove_an_atom() {
type F = AFrac<Rational>;
let f = F::inv_linear(1, 0); let g = f.invert_alpha(); assert_eq!(g, F::linear(1, 0), "{g}");
let (_, den, _) = g.parts();
assert_eq!(den.count(), 0, "the α atom must be gone, not merely equal");
}
#[test]
fn evaluation_and_its_poles() {
type F = AFrac<Rational>;
let f = F::inv_linear(1, 1);
assert_eq!(f.eval(&r(3)), Some(Rational::new(1, 4)));
assert_eq!(f.eval(&r(-1)), None, "α = −1 is a pole");
let g = F::linear(1, 1).div_linear(1, 1);
assert_eq!(g.eval(&r(-1)), Some(r(1)));
}
}