polycore 0.1.5

Fields, prime fields, sparse and dense polynomials, and sparse echelon forms.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120

use std::ops::{Add, Div, Mul, Neg, Sub};

use num_traits::{One, Zero};

use crate::field::Field;
use crate::uni::Uni;

/// A univariate rational function `num / den` in lowest terms with `den` monic: the field `F(a)`,
/// coefficients for polynomials with a parameter.
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct RatFunc<F> {
    num: Uni<F>,
    den: Uni<F>,
}

impl<F: Field> RatFunc<F> {
    pub fn new(num: &Uni<F>, den: &Uni<F>) -> Self {
        assert!(!den.is_zero(), "zero denominator");
        let g = num.gcd(den);
        let (num, den) = (num / &g, den / &g);
        let l = den.lc().inverse().expect("nonzero denominator");
        Self {
            num: num.scale(&l),
            den: den.scale(&l),
        }
    }

    /// The parameter itself.
    pub fn var() -> Self {
        Uni::x().into()
    }

    pub const fn num(&self) -> &Uni<F> {
        &self.num
    }

    pub const fn den(&self) -> &Uni<F> {
        &self.den
    }

    /// The value at `a`, or `None` at a pole.
    pub fn eval(&self, a: &F) -> Option<F> {
        Some(self.num.eval(a) * self.den.eval(a).inverse()?)
    }

    /// Maps the coefficients, or `None` if `f` refuses one or the denominator vanishes.
    pub fn try_map<G: Field>(&self, f: impl Fn(&F) -> Option<G>) -> Option<RatFunc<G>> {
        let lift = |u: &Uni<F>| u.0.iter().map(&f).collect::<Option<Vec<G>>>().map(Uni::new);
        let (num, den) = (lift(&self.num)?, lift(&self.den)?);
        (!den.is_zero()).then(|| RatFunc::new(&num, &den))
    }
}

impl<F: Field> From<Uni<F>> for RatFunc<F> {
    fn from(num: Uni<F>) -> Self {
        Self {
            num,
            den: Uni::constant(F::one()),
        }
    }
}

impl<F: Field> Zero for RatFunc<F> {
    fn zero() -> Self {
        Uni::zero().into()
    }

    fn is_zero(&self) -> bool {
        self.num.is_zero()
    }
}

impl<F: Field> One for RatFunc<F> {
    fn one() -> Self {
        Uni::constant(F::one()).into()
    }
}

impl<F: Field> Add for RatFunc<F> {
    type Output = Self;
    fn add(self, o: Self) -> Self {
        if self.den == o.den {
            return Self::new(&(&self.num + &o.num), &self.den);
        }
        let num = &(&self.num * &o.den) + &(&o.num * &self.den);
        Self::new(&num, &(&self.den * &o.den))
    }
}

impl<F: Field> Neg for RatFunc<F> {
    type Output = Self;
    fn neg(self) -> Self {
        Self {
            num: -&self.num,
            den: self.den,
        }
    }
}

impl<F: Field> Sub for RatFunc<F> {
    type Output = Self;
    fn sub(self, o: Self) -> Self {
        self + -o
    }
}

impl<F: Field> Mul for RatFunc<F> {
    type Output = Self;
    fn mul(self, o: Self) -> Self {
        Self::new(&(&self.num * &o.num), &(&self.den * &o.den))
    }
}

impl<F: Field> Div for RatFunc<F> {
    type Output = Self;
    fn div(self, o: Self) -> Self {
        assert!(!o.is_zero(), "division by zero");
        Self::new(&(&self.num * &o.den), &(&self.den * &o.num))
    }
}