pub trait EuclideanDomain: CommutativeRing {
type EuclideanValue: Ord;
// Required methods
fn euclidean_fn(&self) -> Self::EuclideanValue;
fn div_euclid(&self, other: &Self) -> Self;
fn rem_euclid(&self, other: &Self) -> Self;
// Provided methods
fn gcd(&self, other: &Self) -> Self
where Self: Sized + Clone { ... }
fn lcm(&self, other: &Self) -> Self
where Self: Sized + Clone + Div<Output = Self> { ... }
}Expand description
Represents a Euclidean Domain.
A Euclidean domain is an integral domain equipped with a Euclidean function that enables division with remainder. This is the foundation of the Euclidean algorithm for computing greatest common divisors.
§Mathematical Definition
A commutative ring R is a Euclidean domain if there exists a function
φ: R \ {0} → ℕ (the Euclidean function) such that for any a, b ∈ R
with b ≠ 0, there exist q, r ∈ R satisfying:
a = b·q + r- Either
r = 0orφ(r) < φ(b)
For integers, φ(n) = |n| (absolute value).
§Properties
- Every Euclidean domain is a Principal Ideal Domain (PID).
- Every Euclidean domain is a Unique Factorization Domain (UFD).
- The Euclidean algorithm terminates in finite steps.
§Examples
- Integers
ℤwithφ(n) = |n| - Gaussian integers
ℤ[i]withφ(a + bi) = a² + b² - Polynomial rings
F[x]over a field withφ(p) = deg(p)
Required Associated Types§
Sourcetype EuclideanValue: Ord
type EuclideanValue: Ord
The Euclidean function value type (typically a measure of “size”). For integers, this is the absolute value.
Required Methods§
Sourcefn euclidean_fn(&self) -> Self::EuclideanValue
fn euclidean_fn(&self) -> Self::EuclideanValue
Computes the Euclidean function value.
For integers, this returns the absolute value. For polynomials, this would return the degree.
Sourcefn div_euclid(&self, other: &Self) -> Self
fn div_euclid(&self, other: &Self) -> Self
Computes the quotient of Euclidean division.
For a.div_euclid(b), returns q such that a = b*q + r
where 0 ≤ r < |b|.
Sourcefn rem_euclid(&self, other: &Self) -> Self
fn rem_euclid(&self, other: &Self) -> Self
Computes the remainder of Euclidean division.
For a.rem_euclid(b), returns r such that a = b*q + r
where 0 ≤ r < |b|.
Unlike the % operator, the result is always non-negative.
Provided Methods§
Dyn Compatibility§
This trait is not dyn compatible.
In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.