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
21            #[must_use]
22            fn factorize(&self) -> NonZeroFactorization<Self::Factor, Self::Power> {
23                let as_non_zero = <$nzity>::new(*self)
24                    .expect("attempt to factorize zero");
25                as_non_zero.factorize()
26            }
27        }
28
29        impl NonZeroFactorizable for $nzity {
30            type Factor = $uty;
31            type Power = u32;
32
33            #[must_use]
34            fn factorize(&self) -> NonZeroFactorization<Self::Factor, Self::Power> {
35                let sign = self.non_zero_signum();
36                let factors = $method_name(self.unsigned_abs());
37
38                NonZeroFactorization { sign, factors }
39            }
40        }
41
42        impl NonZeroFactorizable for $uty {
43            type Factor = $uty;
44            type Power = u32;
45
46            #[must_use]
47            fn factorize(&self) -> NonZeroFactorization<Self::Factor, Self::Power> {
48                let as_non_zero = <$nzuty>::new(*self)
49                    .expect("attempt to factorize zero");
50
51                NonZeroFactorization { sign: NonZeroSign::Positive, factors: $method_name(as_non_zero) }
52            }
53        }
54
55        impl NonZeroFactorizable for $nzuty {
56            type Factor = $uty;
57            type Power = u32;
58
59            #[must_use]
60            fn factorize(&self) -> NonZeroFactorization<Self::Factor, Self::Power> {
61                NonZeroFactorization { sign: NonZeroSign::Positive, factors: $method_name(*self) }
62            }
63        }
64    }
65}
66
67forwards!(NonZeroI8, NonZeroU8, i8, u8, size_8::factorize);
68forwards!(NonZeroI16, NonZeroU16, i16, u16, size_16::factorize);
69forwards!(NonZeroI32, NonZeroU32, i32, u32, size_32::factorize);
70
71// TODO(PERFORMANCE): Tune these values
72const NR_SMALL_PRIMES: usize = 256;
73const TRIAL_DIVISION_LIMIT: u64 = 0;
74// TODO(ARCHITECTURE): Eliminate this redundant constant which should be a copy of the above
75const TRIAL_DIVISION_LIMIT_USIZE: usize = 0;
76const RHO_BASE_LIMIT: u64 = 0;
77const KEEP_RESIDUAL: bool = false;
78
79fn factorize64(value: NonZeroU64) -> Vec<(u64, u32)> {
80    size_64::factorize::<
81        NR_SMALL_PRIMES,
82        TRIAL_DIVISION_LIMIT,
83        RHO_BASE_LIMIT,
84        KEEP_RESIDUAL,
85    >(value)
86}
87
88forwards!(NonZeroI64, NonZeroU64, i64, u64, factorize64);
89
90pub const fn start(nr_small_primes: usize) -> u16 {
91    if nr_small_primes < SMALL_ODD_PRIMES.len() {
92        // Get next prime
93        SMALL_ODD_PRIMES[nr_small_primes]
94    } else {
95        // Largest prime + 2
96        SMALL_ODD_PRIMES[nr_small_primes - 1] + 2
97    }
98}
99
100#[cfg(test)]
101mod test;
relp_num/integer/factorization/mod.rs

relp_num/integer/factorization/
mod.rs
