mathhook_core/core/polynomial/
gcd_ops.rs

1//! Polynomial GCD Operations
2//!
3//! Provides GCD, LCM, and cofactor computation for polynomial expressions.
4//! Uses IntPoly fast-path dispatch to route to optimized algorithms.
5
6use super::classification::PolynomialClassification;
7use super::error::PolynomialError;
8use super::integer_gcd;
9use crate::algebra::gcd::{polynomial_gcd, PolynomialGcd as PolynomialGcdTrait};
10use crate::core::Expression;
11use crate::simplify::Simplify;
12
13/// Trait for polynomial GCD operations
14///
15/// Provides methods for computing GCD, LCM, and cofactors of polynomial
16/// expressions. The implementation uses IntPoly fast-path when possible.
17///
18/// # Examples
19///
20/// ```rust,ignore
21/// use mathhook_core::core::polynomial::PolynomialGcdOps;
22/// use mathhook_core::core::Expression;
23/// use mathhook_core::{symbol, expr};
24///
25/// let x = symbol!(x);
26/// // x^2 - 1 = (x-1)(x+1)
27/// let p1 = expr!((x ^ 2) - 1);
28/// // x - 1
29/// let p2 = expr!(x - 1);
30///
31/// let gcd = p1.polynomial_gcd(&p2).unwrap();
32/// // GCD divides both polynomials
33/// ```
34pub trait PolynomialGcdOps: PolynomialClassification {
35    /// Compute GCD of two polynomials
36    ///
37    /// Returns the greatest common divisor of `self` and `other`.
38    /// Uses IntPoly fast-path for integer univariate polynomials.
39    ///
40    /// # Arguments
41    ///
42    /// * `other` - The other polynomial
43    ///
44    /// # Returns
45    ///
46    /// Returns `Ok(gcd)` on success, or `Err(PolynomialError)` if the operation fails.
47    fn polynomial_gcd(&self, other: &Self) -> Result<Expression, PolynomialError>;
48
49    /// Compute LCM of two polynomials
50    ///
51    /// Returns the least common multiple of `self` and `other`.
52    fn polynomial_lcm(&self, other: &Self) -> Result<Expression, PolynomialError>;
53
54    /// Compute GCD and cofactors
55    ///
56    /// Returns tuple (gcd, self/gcd, other/gcd).
57    fn polynomial_cofactors(
58        &self,
59        other: &Self,
60    ) -> Result<(Expression, Expression, Expression), PolynomialError>;
61}
62
63impl PolynomialGcdOps for Expression {
64    fn polynomial_gcd(&self, other: &Self) -> Result<Expression, PolynomialError> {
65        polynomial_gcd(self, other)
66    }
67
68    fn polynomial_lcm(&self, other: &Self) -> Result<Expression, PolynomialError> {
69        use crate::core::Number;
70
71        // Handle integer case directly
72        if let (Expression::Number(Number::Integer(a)), Expression::Number(Number::Integer(b))) =
73            (self, other)
74        {
75            let gcd_val = integer_gcd(*a, *b);
76            if gcd_val == 0 {
77                return Ok(Expression::integer(0));
78            }
79            let lcm_val = (*a / gcd_val) * *b;
80            return Ok(Expression::integer(lcm_val.abs()));
81        }
82
83        let gcd = self.polynomial_gcd(other)?;
84
85        if gcd.is_zero() {
86            return Ok(Expression::integer(0));
87        }
88
89        let product = Expression::mul(vec![self.clone(), other.clone()]);
90        let vars = self.find_variables();
91        if vars.is_empty() {
92            // For constants, LCM = |a * b| / gcd(a, b)
93            return Ok(product.simplify());
94        }
95        Ok(PolynomialGcdTrait::quo_polynomial(&product, &gcd, &vars[0]))
96    }
97
98    fn polynomial_cofactors(
99        &self,
100        other: &Self,
101    ) -> Result<(Expression, Expression, Expression), PolynomialError> {
102        let gcd = self.polynomial_gcd(other)?;
103
104        if gcd.is_zero() || gcd.is_one() {
105            return Ok((gcd, self.clone(), other.clone()));
106        }
107
108        let vars = self.find_variables();
109        if vars.len() == 1 {
110            let var = &vars[0];
111            let (q1, r1) = PolynomialGcdTrait::div_polynomial(self, &gcd, var);
112            let (q2, r2) = PolynomialGcdTrait::div_polynomial(other, &gcd, var);
113
114            if r1.is_zero() && r2.is_zero() {
115                return Ok((gcd, q1, q2));
116            }
117        }
118
119        Ok((gcd, self.clone(), other.clone()))
120    }
121}
122
123#[cfg(test)]
124mod tests {
125    use super::*;
126    use crate::{expr, symbol};
127
128    #[test]
129    fn test_polynomial_gcd_basic() {
130        let _x = symbol!(x);
131        let p1 = expr!((x ^ 2) - 1);
132        let p2 = expr!(x - 1);
133
134        let gcd = p1.polynomial_gcd(&p2).unwrap();
135        assert!(!gcd.is_zero());
136    }
137
138    #[test]
139    fn test_polynomial_lcm_basic() {
140        let a = Expression::integer(6);
141        let b = Expression::integer(8);
142
143        let lcm = a.polynomial_lcm(&b).unwrap();
144        assert!(!lcm.is_zero());
145    }
146
147    #[test]
148    fn test_polynomial_cofactors_basic() {
149        let _x = symbol!(x);
150        let p1 = expr!((x ^ 2) - 1);
151        let p2 = expr!(x - 1);
152
153        let (gcd, cof1, cof2) = p1.polynomial_cofactors(&p2).unwrap();
154        assert!(!gcd.is_zero());
155        assert!(!cof1.is_zero());
156        assert!(!cof2.is_zero());
157    }
158}
mathhook_core/core/polynomial/gcd_ops.rs

mathhook_core/core/polynomial/
gcd_ops.rs
