pub trait NonZeroFactorizable: NonZero + Clone {
type Factor: NonZero + Eq + PartialEq + Ord + PartialOrd + Hash + Clone + Debug;
type Power: Add<Output = Self::Power> + AddAssign + Sub<Output = Self::Power> + SubAssign + One + Signed + Eq + Copy + Clone + Debug;
type Residual: FactorizationResidual;
// Required method
fn factorize(
&self,
) -> NonZeroFactorization<Self::Factor, Self::Power, Self::Residual>;
}Expand description
Creating a factorization of an integer or rational number.
This factorization does not necessarily consist of primes, and it is not necessarily complete:
finding all prime factors of a large number is expensive, so the routines give up at some point
and report whatever they did not decompose in
NonZeroFactorization::residual.
§Invariant
Whatever the parameters the implementation was tuned with, the factorization always describes the entire value:
value == sign * residual * product(factor ^ power)So a factorization never silently loses part of the value; when a cofactor could not be split,
it ends up in residual and
NonZeroFactorization::is_complete is false.
Required Associated Types§
Sourcetype Factor: NonZero + Eq + PartialEq + Ord + PartialOrd + Hash + Clone + Debug
type Factor: NonZero + Eq + PartialEq + Ord + PartialOrd + Hash + Clone + Debug
Some number greater than 1, probably a prime but not necessarily.
Sourcetype Power: Add<Output = Self::Power> + AddAssign + Sub<Output = Self::Power> + SubAssign + One + Signed + Eq + Copy + Clone + Debug
type Power: Add<Output = Self::Power> + AddAssign + Sub<Output = Self::Power> + SubAssign + One + Signed + Eq + Copy + Clone + Debug
How often the factor appears in the number.
This is marked Copy, because a 64-bit power already allows for values up to 2^(2^64), which has about 5.6 * 10^18 decimal digits. Finding primes that are larger than that is too expensive.
Sourcetype Residual: FactorizationResidual
type Residual: FactorizationResidual
The part of the value that was not decomposed.
This is one exactly when the factorization is complete. It is a separate type because it is
not necessarily representable as a Factor: a cofactor of a
big integer can be larger than a machine word, and a rational number leaves a residual on
both sides of the fraction.
Required Methods§
Sourcefn factorize(
&self,
) -> NonZeroFactorization<Self::Factor, Self::Power, Self::Residual>
fn factorize( &self, ) -> NonZeroFactorization<Self::Factor, Self::Power, Self::Residual>
Decompose into factors.
Note that these factors will often be, but are not guaranteed to be, primes.
The value is always described completely: see the invariant on
NonZeroFactorizable and on NonZeroFactorization.
Dyn Compatibility§
This trait is not dyn compatible.
In older versions of Rust, dyn compatibility was called "object safety".