primefactor/
candidates.rs

1//! Implementations of Prime wheels for number factorization
2//! https://en.wikipedia.org/wiki/Wheel_factorization
3#![allow(dead_code)]
4
5/// Wheel factorization algorithm with base {2, 3, 5} (30 spokes)
6#[derive(Clone, Debug, Default, Eq, PartialEq)]
7pub struct PrimeWheel30 {
8    base: u128,
9    first: usize,
10    index: usize,
11}
12
13impl PrimeWheel30 {
14    const FIRSTS: [u128; 3] = [2, 3, 5];
15    const SPOKES: [u128; 8] = [7, 11, 13, 17, 19, 23, 29, 31];
16    pub fn new() -> Self {
17        Self::default()
18    }
19}
20
21impl Iterator for PrimeWheel30 {
22    type Item = u128;
23    fn next(&mut self) -> Option<Self::Item> {
24        if self.first < Self::FIRSTS.len() {
25            let n = Self::FIRSTS[self.first];
26            self.first += 1;
27            Some(n)
28        } else if self.base == 87841638446235960 && self.index > 2 {
29            None
30        } else if self.index < Self::SPOKES.len() {
31            let n = self.base + Self::SPOKES[self.index];
32            self.index += 1;
33            Some(n)
34        } else {
35            self.base += 30;
36            self.index = 1;
37            Some(self.base + Self::SPOKES[0])
38        }
39    }
40}
41
42/// Wheel factorization algorithm with base {2, 3, 5, 7} (210 spokes)
43#[derive(Clone, Debug, Default, Eq, PartialEq)]
44pub struct PrimeWheel210 {
45    base: u128,
46    first: usize,
47    index: usize,
48}
49
50impl PrimeWheel210 {
51    const FIRSTS: [u128; 4] = [2, 3, 5, 7];
52    const SPOKES: [u128; 48] = [
53        11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73,
54        79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 143,
55        149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199,
56        209, 211];
57    pub fn new() -> Self {
58        Self::default()
59    }
60}
61
62impl Iterator for PrimeWheel210 {
63    type Item = u128;
64    fn next(&mut self) -> Option<Self::Item> {
65        if self.first < Self::FIRSTS.len() {
66            let n = Self::FIRSTS[self.first];
67            self.first += 1;
68            Some(n)
69        } else if self.base == 87841638446235960 && self.index > 1 {
70            None
71        } else if self.index < Self::SPOKES.len() {
72            let n = self.base + Self::SPOKES[self.index];
73            self.index += 1;
74            Some(n)
75        } else {
76            self.base += 210;
77            self.index = 1;
78            Some(self.base + Self::SPOKES[0])
79        }
80    }
81}
82
83// Bit-map: 0x0200a2_88282288_20a08a08_820228a2_02088288_28208a20_a08a2802
84const PW210_BITMAP_B: [u8; 27] = [
85    0x02, 0x28, 0x8a, 0xa0, 0x20, 0x8a, 0x20, 0x28,
86    0x88, 0x82, 0x08, 0x02, 0xa2, 0x28, 0x02, 0x82,
87    0x08, 0x8a, 0xa0, 0x20, 0x88, 0x22, 0x28, 0x88,
88    0xa2, 0x00, 0x02];
89
90pub fn is_pw210_candidate_b(num: u128) -> bool {
91    if num < 11 {
92        matches!(num, 2 | 3 | 5 | 7)
93    } else {
94        let index = (num % 210) as usize; // Calculate bit position (0 to 209)
95        let byte_index = index / 8; // Calculate byte index within the array
96        let bit_mask = 1 << (index % 8); // Calculate bit-mask within the byte
97        PW210_BITMAP_B[byte_index] & bit_mask > 0
98    }
99}
100
101const PW210_BITMAP_32: [u32; 7] = [
102    0xa08a2802,
103    0x28208a20,
104    0x02088288,
105    0x820228a2,
106    0x20a08a08,
107    0x88282288,
108    0x000200a2,
109];
110
111pub fn is_pw210_candidate(num: u128) -> bool {
112    if num < 11 {
113        matches!(num, 2 | 3 | 5 | 7)
114    } else {
115        let index = (num % 210) as usize;  // Calculate bit position (0 to 209)
116        let dword_index = index / 32;      // Calculate dword index
117        let bit_mask = 1 << (index & 0x1F); // Calculate bit-mask
118        PW210_BITMAP_32[dword_index] & bit_mask > 0
119    }
120}
121
122#[cfg(test)]
123mod tests {
124    use super::{PrimeWheel210, is_pw210_candidate, is_pw210_candidate_b};
125    #[test]
126    fn test_spokes() {
127        (8..212).for_each(|n| {
128            assert_eq!(PrimeWheel210::SPOKES.contains(&n), is_pw210_candidate(n));
129        });
130    }
131    #[test]
132    fn test_bitmaps() {
133        for n in 0..210 {
134            assert_eq!(is_pw210_candidate(n), is_pw210_candidate_b(n));
135        }
136    }
137}
primefactor/candidates.rs

primefactor/
candidates.rs
