mathhook_core/algebra/factor/
common.rs

1//! Common factor extraction and GCD operations
2
3use crate::core::{Expression, Number};
4use num_bigint::BigInt;
5use num_integer::Integer;
6use num_traits::{One, Zero};
7
8impl Expression {
9    /// Find common factor in a list of terms
10    pub(super) fn find_common_factor_in_terms(&self, terms: &[Expression]) -> Expression {
11        if terms.is_empty() {
12            return Expression::integer(1);
13        }
14
15        let mut common = self.extract_factors(&terms[0]);
16
17        for term in &terms[1..] {
18            let term_factors = self.extract_factors(term);
19            common = self.intersect_factors(&common, &term_factors);
20
21            if common.is_empty() {
22                return Expression::integer(1);
23            }
24        }
25
26        if common.is_empty() {
27            Expression::integer(1)
28        } else {
29            Expression::mul(common)
30        }
31    }
32
33    /// Extract factors from an expression
34    pub(super) fn extract_factors(&self, expr: &Expression) -> Vec<Expression> {
35        match expr {
36            Expression::Number(Number::Integer(n)) => {
37                if !n.is_zero() && !n.is_one() {
38                    vec![expr.clone()]
39                } else {
40                    vec![]
41                }
42            }
43            Expression::Symbol(_) => vec![expr.clone()],
44            Expression::Mul(factors) => (**factors).clone(),
45            Expression::Pow(base, _exp) => vec![(**base).clone()],
46            _ => vec![expr.clone()],
47        }
48    }
49
50    /// Find intersection of two factor lists
51    pub(super) fn intersect_factors(
52        &self,
53        factors1: &[Expression],
54        factors2: &[Expression],
55    ) -> Vec<Expression> {
56        let mut common = Vec::new();
57
58        for factor1 in factors1 {
59            if factors2.contains(factor1) {
60                common.push(factor1.clone());
61            }
62        }
63
64        let num1 = self.extract_numeric_factor(factors1);
65        let num2 = self.extract_numeric_factor(factors2);
66
67        if let (Some(n1), Some(n2)) = (num1, num2) {
68            let gcd_num = n1.gcd(&n2);
69            if !gcd_num.is_one() {
70                common.push(Expression::big_integer(gcd_num));
71            }
72        }
73
74        common
75    }
76
77    /// Extract numeric factor from factor list
78    pub(super) fn extract_numeric_factor(&self, factors: &[Expression]) -> Option<BigInt> {
79        for factor in factors {
80            if let Expression::Number(Number::Integer(n)) = factor {
81                return Some(BigInt::from(*n));
82            }
83        }
84        None
85    }
86
87    /// Divide expression by a factor (simplified division)
88    pub(super) fn divide_by_factor(&self, expr: &Expression, factor: &Expression) -> Expression {
89        match (expr, factor) {
90            (Expression::Number(Number::Integer(a)), Expression::Number(Number::Integer(b))) => {
91                if !b.is_zero() && (a % b).is_zero() {
92                    Expression::integer(a / b)
93                } else {
94                    expr.clone()
95                }
96            }
97
98            (Expression::Symbol(s1), Expression::Symbol(s2)) if s1 == s2 => Expression::integer(1),
99
100            (Expression::Mul(factors), _) => {
101                let mut remaining_factors = factors.as_ref().clone();
102                if let Some(pos) = remaining_factors.iter().position(|f| f == factor) {
103                    remaining_factors.remove(pos);
104                    if remaining_factors.is_empty() {
105                        Expression::integer(1)
106                    } else if remaining_factors.len() == 1 {
107                        remaining_factors[0].clone()
108                    } else {
109                        Expression::mul(remaining_factors)
110                    }
111                } else {
112                    expr.clone()
113                }
114            }
115
116            _ => expr.clone(),
117        }
118    }
119
120    /// Factor out numeric coefficients
121    pub fn factor_numeric_coefficient(&self) -> (BigInt, Expression) {
122        match self {
123            Expression::Number(Number::Integer(n)) => (BigInt::from(*n), Expression::integer(1)),
124            Expression::Number(Number::BigInteger(n)) => {
125                (n.as_ref().clone(), Expression::integer(1))
126            }
127            Expression::Mul(factors) => {
128                let mut coefficient = BigInt::one();
129                let mut non_numeric_factors = Vec::new();
130
131                for factor in factors.iter() {
132                    match factor {
133                        Expression::Number(Number::Integer(n)) => {
134                            coefficient *= BigInt::from(*n);
135                        }
136                        Expression::Number(Number::BigInteger(n)) => {
137                            coefficient *= n.as_ref();
138                        }
139                        _ => {
140                            non_numeric_factors.push(factor.clone());
141                        }
142                    }
143                }
144
145                let remaining = if non_numeric_factors.is_empty() {
146                    Expression::integer(1)
147                } else if non_numeric_factors.len() == 1 {
148                    non_numeric_factors[0].clone()
149                } else {
150                    Expression::mul(non_numeric_factors)
151                };
152
153                (coefficient, remaining)
154            }
155            _ => (BigInt::one(), self.clone()),
156        }
157    }
158}
mathhook_core/algebra/factor/common.rs

mathhook_core/algebra/factor/
common.rs
