mathhook_core/core/polynomial/educational/
gcd.rs

1//! Polynomial GCD educational explanations
2
3use super::super::algorithms::integer_gcd;
4use super::super::algorithms::zippel_gcd::educational;
5use super::super::classification::PolynomialClassification;
6use super::super::gcd_ops::PolynomialGcdOps;
7use super::super::properties::PolynomialProperties;
8use super::create_explanation;
9use crate::core::{Expression, Number};
10use crate::educational::step_by_step::{Step, StepByStepExplanation};
11
12pub fn explain_poly_gcd_impl(expr: &Expression, other: &Expression) -> StepByStepExplanation {
13    let mut steps = Vec::new();
14
15    steps.push(Step {
16        title: "Polynomial GCD".to_owned(),
17        description: format!("Compute GCD of {} and {}", expr, other),
18        expression: expr.clone(),
19        rule_applied: "Initial".to_owned(),
20        latex: None,
21    });
22
23    if let (Expression::Number(Number::Integer(n1)), Expression::Number(Number::Integer(n2))) =
24        (expr, other)
25    {
26        let gcd = integer_gcd(*n1, *n2);
27        steps.push(Step {
28            title: "Integer GCD".to_owned(),
29            description: format!(
30                "Both inputs are integers. Using Euclidean algorithm:\n\
31                 GCD({}, {}) = {}",
32                n1, n2, gcd
33            ),
34            expression: Expression::integer(gcd),
35            rule_applied: "Euclidean Algorithm".to_owned(),
36            latex: None,
37        });
38
39        return create_explanation(expr.clone(), Expression::integer(gcd), steps);
40    }
41
42    if expr.is_zero() {
43        steps.push(Step {
44            title: "Zero Input".to_owned(),
45            description: format!("GCD(0, b) = |b|\nResult: {}", other),
46            expression: other.clone(),
47            rule_applied: "Zero Property".to_owned(),
48            latex: None,
49        });
50        return create_explanation(expr.clone(), other.clone(), steps);
51    }
52
53    if other.is_zero() {
54        steps.push(Step {
55            title: "Zero Input".to_owned(),
56            description: format!("GCD(a, 0) = |a|\nResult: {}", expr),
57            expression: expr.clone(),
58            rule_applied: "Zero Property".to_owned(),
59            latex: None,
60        });
61        return create_explanation(expr.clone(), expr.clone(), steps);
62    }
63
64    if expr.is_one() || other.is_one() {
65        steps.push(Step {
66            title: "Coprime with 1".to_owned(),
67            description: "GCD with 1 is always 1".to_owned(),
68            expression: Expression::integer(1),
69            rule_applied: "Identity Property".to_owned(),
70            latex: None,
71        });
72        return create_explanation(expr.clone(), Expression::integer(1), steps);
73    }
74
75    let vars_self = expr.polynomial_variables();
76    let vars_other = other.polynomial_variables();
77    let mut all_vars: Vec<_> = vars_self.clone();
78    for v in vars_other.iter() {
79        if !all_vars.iter().any(|s| s.name() == v.name()) {
80            all_vars.push(v.clone());
81        }
82    }
83    let is_univariate = all_vars.len() <= 1;
84
85    let max_degree = if let Some(var) = all_vars.first() {
86        let d1 = expr.degree(var).unwrap_or(0);
87        let d2 = other.degree(var).unwrap_or(0);
88        d1.max(d2)
89    } else {
90        0
91    };
92
93    let has_large_coeffs = max_degree >= 20;
94    let is_sparse = max_degree >= 15;
95
96    steps.push(Step {
97        title: "Analyze Polynomial Characteristics".to_owned(),
98        description: format!(
99            "Variables: {} ({})\n\
100             Maximum degree: {}\n\
101             Characteristics: {}",
102            if all_vars.is_empty() {
103                "constant".to_owned()
104            } else {
105                all_vars
106                    .iter()
107                    .map(|v| v.name().to_owned())
108                    .collect::<Vec<_>>()
109                    .join(", ")
110            },
111            if is_univariate {
112                "univariate"
113            } else {
114                "multivariate"
115            },
116            max_degree,
117            if max_degree >= 10 {
118                "high-degree (modular methods preferred)"
119            } else {
120                "low-degree (classical methods efficient)"
121            }
122        ),
123        expression: expr.clone(),
124        rule_applied: "Analysis".to_owned(),
125        latex: None,
126    });
127
128    let rationale = educational::explain_selection_rationale(
129        is_univariate,
130        max_degree,
131        is_sparse,
132        has_large_coeffs,
133    );
134    steps.push(Step {
135        title: "Algorithm Selection".to_owned(),
136        description: rationale,
137        expression: expr.clone(),
138        rule_applied: "Selection".to_owned(),
139        latex: None,
140    });
141
142    let use_modular = is_sparse || has_large_coeffs || max_degree >= 10 || !is_univariate;
143
144    if use_modular {
145        steps.push(Step {
146            title: "Zippel Modular GCD Overview".to_owned(),
147            description: educational::algorithm_overview().to_owned(),
148            expression: expr.clone(),
149            rule_applied: "Algorithm Description".to_owned(),
150            latex: None,
151        });
152
153        steps.push(Step {
154            title: "Content Extraction".to_owned(),
155            description: educational::explain_content_extraction().to_owned(),
156            expression: expr.clone(),
157            rule_applied: "Step 1".to_owned(),
158            latex: None,
159        });
160
161        steps.push(Step {
162            title: "CRT Reconstruction".to_owned(),
163            description: educational::explain_crt_reconstruction().to_owned(),
164            expression: expr.clone(),
165            rule_applied: "Step 2-3".to_owned(),
166            latex: None,
167        });
168
169        steps.push(Step {
170            title: "Trial Division Verification".to_owned(),
171            description: educational::explain_trial_division().to_owned(),
172            expression: expr.clone(),
173            rule_applied: "Step 4".to_owned(),
174            latex: None,
175        });
176    } else {
177        steps.push(Step {
178            title: "Euclidean Algorithm".to_owned(),
179            description: "The polynomial GCD is computed using the Euclidean algorithm:\n\
180                         1. Divide larger degree polynomial by smaller\n\
181                         2. Replace larger with remainder\n\
182                         3. Repeat until remainder is zero\n\
183                         4. Last non-zero remainder is the GCD"
184                .to_owned(),
185            expression: expr.clone(),
186            rule_applied: "Algorithm".to_owned(),
187            latex: None,
188        });
189    }
190
191    match expr.polynomial_gcd(other) {
192        Ok(gcd) => {
193            steps.push(Step {
194                title: "GCD Result".to_owned(),
195                description: format!("GCD({}, {}) = {}", expr, other, gcd),
196                expression: gcd.clone(),
197                rule_applied: "Final".to_owned(),
198                latex: None,
199            });
200
201            create_explanation(expr.clone(), gcd, steps)
202        }
203        Err(e) => {
204            steps.push(Step {
205                title: "Error".to_owned(),
206                description: format!("GCD computation failed: {}", e),
207                expression: expr.clone(),
208                rule_applied: "Error".to_owned(),
209                latex: None,
210            });
211
212            create_explanation(expr.clone(), Expression::integer(1), steps)
213        }
214    }
215}
mathhook_core/core/polynomial/educational/gcd.rs

mathhook_core/core/polynomial/educational/
gcd.rs
