relp_num/integer/factorization/
mod.rs

1//! # Factorizing integers
2use std::num::{NonZeroU16, NonZeroU32, NonZeroU64, NonZeroU8};
3use std::num::{NonZeroI16, NonZeroI32, NonZeroI64, NonZeroI8};
4
5use crate::{NonZeroFactorizable, NonZeroFactorization, NonZeroSign, NonZeroSigned};
6use crate::integer::factorization::prime::primes::SMALL_ODD_PRIMES;
7
8pub mod prime;
9mod size_8;
10mod size_16;
11mod size_32;
12mod size_64;
13mod size_large;
14
15macro_rules! forwards {
16    ($nzity:ty, $nzuty:ty, $ity:ty, $uty:ty, $method_name:path) => {
17        impl NonZeroFactorizable for $ity {
18            type Factor = $uty;
19            type Power = u32;
20            /// The value is factorized through its absolute value, so the residual is positive and
21            /// the sign is kept separately.
22            type Residual = $uty;
23
24            fn factorize(&self) -> NonZeroFactorization<Self::Factor, Self::Power, Self::Residual> {
25                let as_non_zero = <$nzity>::new(*self)
26                    .expect("attempt to factorize zero");
27                as_non_zero.factorize()
28            }
29        }
30
31        impl NonZeroFactorizable for $nzity {
32            type Factor = $uty;
33            type Power = u32;
34            /// The value is factorized through its absolute value, so the residual is positive and
35            /// the sign is kept separately.
36            type Residual = $uty;
37
38            fn factorize(&self) -> NonZeroFactorization<Self::Factor, Self::Power, Self::Residual> {
39                let sign = self.non_zero_signum();
40                let (factors, residual) = $method_name(self.unsigned_abs());
41
42                NonZeroFactorization { sign, factors, residual }
43            }
44        }
45
46        impl NonZeroFactorizable for $uty {
47            type Factor = $uty;
48            type Power = u32;
49            type Residual = $uty;
50
51            fn factorize(&self) -> NonZeroFactorization<Self::Factor, Self::Power, Self::Residual> {
52                let as_non_zero = <$nzuty>::new(*self)
53                    .expect("attempt to factorize zero");
54                let (factors, residual) = $method_name(as_non_zero);
55
56                NonZeroFactorization { sign: NonZeroSign::Positive, factors, residual }
57            }
58        }
59
60        impl NonZeroFactorizable for $nzuty {
61            type Factor = $uty;
62            type Power = u32;
63            type Residual = $uty;
64
65            fn factorize(&self) -> NonZeroFactorization<Self::Factor, Self::Power, Self::Residual> {
66                let (factors, residual) = $method_name(*self);
67
68                NonZeroFactorization { sign: NonZeroSign::Positive, factors, residual }
69            }
70        }
71    }
72}
73
74forwards!(NonZeroI8, NonZeroU8, i8, u8, size_8::factorize);
75forwards!(NonZeroI16, NonZeroU16, i16, u16, size_16::factorize);
76forwards!(NonZeroI32, NonZeroU32, i32, u32, size_32::factorize);
77
78// TODO(PERFORMANCE): Tune these values
79const NR_SMALL_PRIMES: usize = 256;
80const TRIAL_DIVISION_LIMIT: u64 = 0;
81const RHO_BASE_LIMIT: u64 = 0;
82const KEEP_RESIDUAL: bool = false;
83
84fn factorize64(value: NonZeroU64) -> (Vec<(u64, u32)>, u64) {
85    size_64::factorize::<
86        NR_SMALL_PRIMES,
87        TRIAL_DIVISION_LIMIT,
88        RHO_BASE_LIMIT,
89        KEEP_RESIDUAL,
90    >(value)
91}
92
93forwards!(NonZeroI64, NonZeroU64, i64, u64, factorize64);
94
95pub const fn start(nr_small_primes: usize) -> u16 {
96    if nr_small_primes < SMALL_ODD_PRIMES.len() {
97        // Get next prime
98        SMALL_ODD_PRIMES[nr_small_primes]
99    } else {
100        // Largest prime + 2
101        SMALL_ODD_PRIMES[nr_small_primes - 1] + 2
102    }
103}
104
105#[cfg(test)]
106mod test;
relp_num/integer/factorization/mod.rs

relp_num/integer/factorization/
mod.rs
