relp_num/traits/
factorization.rs

1//! # Number factorization
2//!
3//! Factorize integers and rational numbers into numbers that are often primes.
4use std::fmt::Debug;
5use std::hash::Hash;
6use std::ops::{Add, AddAssign, Sub, SubAssign};
7
8use num_traits::One;
9
10use crate::non_zero::{NonZero, NonZeroSign};
11use crate::Signed;
12
13/// Creating a factorization of an integer or rational number.
14///
15/// This factorization does not necessarily consist of primes, as this can be computationally
16/// expensive.
17pub trait NonZeroFactorizable: NonZero + Clone {
18    /// Some number greater than 1, probably a prime but not necessarily.
19    type Factor: NonZero + Eq + PartialEq + Ord + PartialOrd + Hash + Clone + Debug;
20    /// How often the factor appears in the number.
21    ///
22    /// This is marked Copy, because a 64-bit power already allows for values up to 2^(2^64), which
23    /// has about 5.6 * 10^18 decimal digits. Finding primes that are larger than that is too
24    /// expensive.
25    type Power: Add<Output=Self::Power> + AddAssign + Sub<Output=Self::Power> + SubAssign + One + Signed + Eq + Copy + Clone + Debug;
26
27    /// Decompose into factors.
28    ///
29    /// Note that these factors will often be, but are not guaranteed to be, primes.
30    fn factorize(&self) -> NonZeroFactorization<Self::Factor, Self::Power>;
31}
32
33/// Prime factorization representation of a nonzero rational number.
34///
35/// Includes a sign.
36#[derive(Eq, PartialEq, Clone, Debug)]
37pub struct NonZeroFactorization<Factor, Power> {
38    /// Whether the number is negative.
39    pub sign: NonZeroSign,
40    /// `(prime factor, power)` tuples.
41    ///
42    /// The factors should all be smaller than 64 bits and can have negative powers; that is, appear
43    /// in the denominator. The powers can't be zero, as this is a sparse representation.
44    ///
45    /// When this field is empty, the value `1` or `-1` is represented, depending on `sign`.
46    pub factors: Vec<(Factor, Power)>,
47}
relp_num/traits/factorization.rs

relp_num/traits/
factorization.rs
