[−][src]Trait maths_traits::algebra::ring_like::Factorizable

pub trait Factorizable: Sized {
    type Factors: Iterator<Item = Self>;
    fn factors(self) -> Self::Factors;
}

For semirings that have a known algorithm for decomposing elements into a set of irreducible factors

Notes on "Irreduciblity"

An irreducible factor as defined here is any element that cannot be written as a product of two or more non-invertible elements. Note that this is technically, but not usually, different than a "prime" element. For more information, see Divisibility.

Uniqueness and Ordering

This trait on its own makes no guarantees that the returned factors are unique or ordered in any way. The only requirements are that:

  • The product of the factors must be the original number
  • No factors of 1 are included
  • 0 returns [0]
  • Only one invertible element can be included and must be the first factor
    • For example, -6 might return [-1, 2, 3] or [-1, 3, 2], but not [2, -1, 3]

Importantly, this means does that some structures can return different sets of factors at different times. For example, in ℤ[√5], 6 = 2*3 = (1+√5)*(1-√5) are both valid irreducible factorizations.

However, if the UniquelyFactorizable trait is also implemented, this is restricted somewhat, but only up to ordering and units.

In particular, given two lists of factors for an element:

  • There is still no guaranteed ordering, so the lists could be permuted somehow
  • Some factors in the second might be multiplied by some invertible element from the first or return an extra invertible element in the list.
    • For instance, -10 might return [-5, 2] or [5,-2] or [2,-5] or even [-1,5,2]

Furthermore, there is no requirement for any sort of ordering, as the wide range of possible implementing structures gives no obvious standard as to what that would be.

However, implementors are highly encouraged to guarantee some sort of ordering and uniqueness themselves using their particular properties. For instance, the implementation on the primitive integers return all non-negative factors in order of increasing absolute magnitude with a -1 at the beginning for negative numbers, or a polynomial could factor as monic polynomials of increasing degree.

Associated Types

type Factors: Iterator<Item = Self>

Loading content...

Required methods

fn factors(self) -> Self::Factors

Loading content...

Implementations on Foreign Types

impl Factorizable for u8[src]

type Factors = TrialDivision<Self>

impl Factorizable for i8[src]

type Factors = TrialDivision<Self>

impl Factorizable for u16[src]

type Factors = TrialDivision<Self>

impl Factorizable for i16[src]

type Factors = TrialDivision<Self>

impl Factorizable for u32[src]

type Factors = TrialDivision<Self>

impl Factorizable for i32[src]

type Factors = TrialDivision<Self>

impl Factorizable for u64[src]

type Factors = TrialDivision<Self>

impl Factorizable for i64[src]

type Factors = TrialDivision<Self>

impl Factorizable for u128[src]

type Factors = TrialDivision<Self>

impl Factorizable for i128[src]

type Factors = TrialDivision<Self>

impl Factorizable for usize[src]

type Factors = TrialDivision<Self>

impl Factorizable for isize[src]

type Factors = TrialDivision<Self>

Loading content...

Implementors

Loading content...