malachite_nz/integer_polynomial/arithmetic/
exponent_gcd.rs

1// Copyright © 2026 Mikhail Hogrefe
2//
3// This file is part of Malachite.
4//
5// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
6// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
7// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
8
9use crate::integer_polynomial::IntegerPolynomial;
10use malachite_base::polynomial::{ExponentGcd, slice_exponent_gcd};
11
12impl ExponentGcd for IntegerPolynomial {
13    /// Computes the greatest common divisor of the exponents at which an [`IntegerPolynomial`] has
14    /// nonzero coefficients.
15    ///
16    /// $$
17    /// f(p) = \gcd \\{i : p_i \neq 0\\}.
18    /// $$
19    ///
20    /// When the polynomial is not constant, this is the largest $k$ such that $p(x) = q(x^k)$ for
21    /// some polynomial $q$, and
22    /// [`compose_power_of_x`](malachite_base::polynomial::ComposePowerOfX::compose_power_of_x) with
23    /// $k$ recovers $p$ from $q$. A constant polynomial, including zero, gives 0.
24    ///
25    /// # Worst-case complexity
26    /// $T(n) = O(n)$
27    ///
28    /// $M(n) = O(1)$
29    ///
30    /// where $T$ is time, $M$ is additional memory, and $n$ is `self.len()`.
31    ///
32    /// # Examples
33    /// ```
34    /// use core::str::FromStr;
35    /// use malachite_base::num::basic::traits::Zero;
36    /// use malachite_base::polynomial::ExponentGcd;
37    /// use malachite_nz::integer_polynomial::IntegerPolynomial;
38    ///
39    /// assert_eq!(
40    ///     IntegerPolynomial::from_str("x^6-2*x^3+1")
41    ///         .unwrap()
42    ///         .exponent_gcd(),
43    ///     3
44    /// );
45    /// assert_eq!(
46    ///     IntegerPolynomial::from_str("x^4-x").unwrap().exponent_gcd(),
47    ///     1
48    /// );
49    /// assert_eq!(
50    ///     IntegerPolynomial::from_str("-x^4").unwrap().exponent_gcd(),
51    ///     4
52    /// );
53    /// assert_eq!(IntegerPolynomial::from_str("-5").unwrap().exponent_gcd(), 0);
54    /// assert_eq!(IntegerPolynomial::ZERO.exponent_gcd(), 0);
55    /// ```
56    ///
57    /// This is equivalent to `fmpz_poly_deflation` from `fmpz_poly/deflation.c`, FLINT 3.6.0,
58    /// except that a constant gives 0 rather than 1.
59    #[inline]
60    fn exponent_gcd(&self) -> u64 {
61        slice_exponent_gcd(&self.coefficients, |c| *c == 0u32)
62    }
63}
malachite_nz/integer_polynomial/arithmetic/exponent_gcd.rs

malachite_nz/integer_polynomial/arithmetic/
exponent_gcd.rs
