malachite_base/unsigned_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::num::basic::unsigneds::PrimitiveUnsigned;
10use crate::polynomial::{ExponentGcd, slice_exponent_gcd};
11use crate::unsigned_polynomial::UnsignedPolynomial;
12
13impl<T: PrimitiveUnsigned> ExponentGcd for UnsignedPolynomial<T> {
14    /// Computes the greatest common divisor of the exponents at which an [`UnsignedPolynomial`] has
15    /// nonzero coefficients.
16    ///
17    /// $$
18    /// f(p) = \gcd \\{i : p_i \neq 0\\}.
19    /// $$
20    ///
21    /// When the polynomial is not constant, this is the largest $k$ such that $p(x) = q(x^k)$ for
22    /// some polynomial $q$, and
23    /// [`compose_power_of_x`](crate::polynomial::ComposePowerOfX::compose_power_of_x) with $k$
24    /// recovers $p$ from $q$. A constant polynomial, including zero, gives 0.
25    ///
26    /// # Worst-case complexity
27    /// $T(n) = O(n)$
28    ///
29    /// $M(n) = O(1)$
30    ///
31    /// where $T$ is time, $M$ is additional memory, and $n$ is `self.len()`.
32    ///
33    /// # Examples
34    /// ```
35    /// use core::str::FromStr;
36    /// use malachite_base::num::basic::traits::Zero;
37    /// use malachite_base::polynomial::ExponentGcd;
38    /// use malachite_base::unsigned_polynomial::UnsignedPolynomial;
39    ///
40    /// assert_eq!(
41    ///     UnsignedPolynomial::<u8>::from_str("x^6+2*x^3+1")
42    ///         .unwrap()
43    ///         .exponent_gcd(),
44    ///     3
45    /// );
46    /// assert_eq!(
47    ///     UnsignedPolynomial::<u8>::from_str("x^4+x")
48    ///         .unwrap()
49    ///         .exponent_gcd(),
50    ///     1
51    /// );
52    /// assert_eq!(
53    ///     UnsignedPolynomial::<u8>::from_str("x^4")
54    ///         .unwrap()
55    ///         .exponent_gcd(),
56    ///     4
57    /// );
58    /// assert_eq!(
59    ///     UnsignedPolynomial::<u8>::from_str("5")
60    ///         .unwrap()
61    ///         .exponent_gcd(),
62    ///     0
63    /// );
64    /// assert_eq!(UnsignedPolynomial::<u8>::ZERO.exponent_gcd(), 0);
65    /// ```
66    ///
67    /// This is equivalent to `nmod_poly_deflation` from `nmod_poly/deflation.c`, FLINT 3.6.0,
68    /// except that a constant gives 0 rather than 1.
69    #[inline]
70    fn exponent_gcd(&self) -> u64 {
71        slice_exponent_gcd(&self.coefficients, |c| *c == T::ZERO)
72    }
73}
malachite_base/unsigned_polynomial/arithmetic/exponent_gcd.rs

malachite_base/unsigned_polynomial/arithmetic/
exponent_gcd.rs
