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, and it is not necessarily complete:
16/// finding all prime factors of a large number is expensive, so the routines give up at some point
17/// and report whatever they did not decompose in
18/// [`NonZeroFactorization::residual`](NonZeroFactorization#structfield.residual).
19///
20/// # Invariant
21///
22/// Whatever the parameters the implementation was tuned with, the factorization always describes
23/// the entire value:
24///
25/// ```text
26/// value == sign * residual * product(factor ^ power)
27/// ```
28///
29/// So a factorization never silently loses part of the value; when a cofactor could not be split,
30/// it ends up in `residual` and
31/// [`NonZeroFactorization::is_complete`](NonZeroFactorization::is_complete) is `false`.
32pub trait NonZeroFactorizable: NonZero + Clone {
33    /// Some number greater than 1, probably a prime but not necessarily.
34    type Factor: NonZero + Eq + PartialEq + Ord + PartialOrd + Hash + Clone + Debug;
35    /// How often the factor appears in the number.
36    ///
37    /// This is marked Copy, because a 64-bit power already allows for values up to 2^(2^64), which
38    /// has about 5.6 * 10^18 decimal digits. Finding primes that are larger than that is too
39    /// expensive.
40    type Power: Add<Output=Self::Power> + AddAssign + Sub<Output=Self::Power> + SubAssign + One + Signed + Eq + Copy + Clone + Debug;
41    /// The part of the value that was not decomposed.
42    ///
43    /// This is one exactly when the factorization is complete. It is a separate type because it is
44    /// not necessarily representable as a [`Factor`](NonZeroFactorizable::Factor): a cofactor of a
45    /// big integer can be larger than a machine word, and a rational number leaves a residual on
46    /// both sides of the fraction.
47    type Residual: FactorizationResidual;
48
49    /// Decompose into factors.
50    ///
51    /// Note that these factors will often be, but are not guaranteed to be, primes.
52    ///
53    /// The value is always described completely: see the invariant on
54    /// [`NonZeroFactorizable`] and on [`NonZeroFactorization`].
55    fn factorize(&self) -> NonZeroFactorization<Self::Factor, Self::Power, Self::Residual>;
56}
57
58/// The part of a value that a factorization did not decompose.
59///
60/// A residual of one means that nothing was left over, so the factors describe the value exactly.
61///
62/// This trait is deliberately weaker than [`num_traits::One`]: it demands no multiplication,
63/// because the residual of a rational factorization is a `(numerator, denominator)` pair, which has
64/// no meaningful product.
65pub trait FactorizationResidual: Eq + Clone + Debug {
66    /// The residual of a factorization that decomposed the entire value.
67    fn one() -> Self;
68    /// Whether nothing was left undecomposed.
69    fn is_one(&self) -> bool;
70}
71
72macro_rules! residual_from_num_traits_one {
73    ($($ty:ty)*) => {
74        $(
75            impl FactorizationResidual for $ty {
76                #[inline]
77                fn one() -> Self {
78                    <$ty as One>::one()
79                }
80
81                #[inline]
82                fn is_one(&self) -> bool {
83                    <$ty as One>::is_one(self)
84                }
85            }
86        )*
87    }
88}
89residual_from_num_traits_one!(u8 u16 u32 u64 u128 usize);
90
91/// A rational number leaves a residual on both sides of the fraction.
92///
93/// The two halves are `(numerator residual, denominator residual)`; they can't be merged into a
94/// single value, as that value would generally not be an integer.
95impl<Numerator, Denominator> FactorizationResidual for (Numerator, Denominator)
96where
97    Numerator: FactorizationResidual,
98    Denominator: FactorizationResidual,
99{
100    #[inline]
101    fn one() -> Self {
102        (Numerator::one(), Denominator::one())
103    }
104
105    #[inline]
106    fn is_one(&self) -> bool {
107        self.0.is_one() && self.1.is_one()
108    }
109}
110
111/// Factorization of a nonzero integer or rational number.
112///
113/// Includes a sign.
114///
115/// # Invariant
116///
117/// The three fields together always describe the entire value:
118///
119/// ```text
120/// value == sign * residual * product(factor ^ power)
121/// ```
122///
123/// The factorization routines are deliberately incomplete, because splitting a large cofactor is
124/// expensive. Whatever they did not decompose is in `residual` rather than dropped, so the identity
125/// above holds regardless of how they were tuned. Use [`Self::is_complete`] to find out whether the
126/// value was decomposed entirely.
127#[derive(Eq, PartialEq, Clone, Debug)]
128pub struct NonZeroFactorization<Factor, Power, Residual> {
129    /// Whether the number is negative.
130    pub sign: NonZeroSign,
131    /// `(factor, power)` tuples.
132    ///
133    /// These factors are often, but not necessarily, primes; they are all larger than 1. The
134    /// factors should all be smaller than 64 bits and can have negative powers; that is, appear in
135    /// the denominator. The powers can't be zero, as this is a sparse representation.
136    ///
137    /// When this field is empty, nothing was decomposed and the value is `sign * residual`. In
138    /// particular, an empty list does **not** mean that the value is `1` or `-1`; that is the case
139    /// only when the `residual` is one as well.
140    pub factors: Vec<(Factor, Power)>,
141    /// The part of the value that was not decomposed.
142    ///
143    /// One exactly when the factors describe the entire value, see [`Self::is_complete`]. It is
144    /// always positive; the sign of the value is in `sign`.
145    pub residual: Residual,
146}
147
148impl<Factor, Power, Residual: FactorizationResidual> NonZeroFactorization<Factor, Power, Residual> {
149    /// Whether the value was decomposed entirely, that is, whether the residual is one.
150    ///
151    /// When this is `false`, the `factors` describe only the part of the value that could be split
152    /// off cheaply, and multiplying them together does not reproduce the value: the `residual` is
153    /// the missing factor.
154    #[must_use]
155    #[inline]
156    pub fn is_complete(&self) -> bool {
157        self.residual.is_one()
158    }
159}
relp_num/traits/factorization.rs

relp_num/traits/
factorization.rs
