1 use num_traits::{One, PrimInt, Zero};
2
primitive_root(prime: u64) -> Option<u64>3 pub fn primitive_root(prime: u64) -> Option<u64> {
4 let test_exponents: Vec<u64> = distinct_prime_factors(prime - 1)
5 .iter()
6 .map(|factor| (prime - 1) / factor)
7 .collect();
8 'next: for potential_root in 2..prime {
9 // for each distinct factor, if potential_root^(p-1)/factor mod p is 1, reject it
10 for exp in &test_exponents {
11 if modular_exponent(potential_root, *exp, prime) == 1 {
12 continue 'next;
13 }
14 }
15
16 // if we reach this point, it means this root was not rejected, so return it
17 return Some(potential_root);
18 }
19 None
20 }
21
22 /// computes base^exponent % modulo using the standard exponentiation by squaring algorithm
modular_exponent<T: PrimInt>(mut base: T, mut exponent: T, modulo: T) -> T23 pub fn modular_exponent<T: PrimInt>(mut base: T, mut exponent: T, modulo: T) -> T {
24 let one = T::one();
25
26 let mut result = one;
27
28 while exponent > Zero::zero() {
29 if exponent & one == one {
30 result = result * base % modulo;
31 }
32 exponent = exponent >> One::one();
33 base = (base * base) % modulo;
34 }
35
36 result
37 }
38
39 /// return all of the prime factors of n, but omit duplicate prime factors
distinct_prime_factors(mut n: u64) -> Vec<u64>40 pub fn distinct_prime_factors(mut n: u64) -> Vec<u64> {
41 let mut result = Vec::new();
42
43 // handle 2 separately so we dont have to worry about adding 2 vs 1
44 if n % 2 == 0 {
45 while n % 2 == 0 {
46 n /= 2;
47 }
48 result.push(2);
49 }
50 if n > 1 {
51 let mut divisor = 3;
52 let mut limit = (n as f32).sqrt() as u64 + 1;
53 while divisor < limit {
54 if n % divisor == 0 {
55 // remove as many factors as possible from n
56 while n % divisor == 0 {
57 n /= divisor;
58 }
59 result.push(divisor);
60
61 // recalculate the limit to reduce the amount of work we need to do
62 limit = (n as f32).sqrt() as u64 + 1;
63 }
64
65 divisor += 2;
66 }
67
68 if n > 1 {
69 result.push(n);
70 }
71 }
72
73 result
74 }
75
76 #[derive(Debug, PartialEq, Eq, Copy, Clone)]
77 pub struct PrimeFactor {
78 pub value: usize,
79 pub count: u32,
80 }
81
82 #[derive(Clone, Debug)]
83 pub struct PrimeFactors {
84 other_factors: Vec<PrimeFactor>,
85 n: usize,
86 power_two: u32,
87 power_three: u32,
88 total_factor_count: u32,
89 distinct_factor_count: u32,
90 }
91 impl PrimeFactors {
compute(mut n: usize) -> Self92 pub fn compute(mut n: usize) -> Self {
93 let mut result = Self {
94 other_factors: Vec::new(),
95 n,
96 power_two: 0,
97 power_three: 0,
98 total_factor_count: 0,
99 distinct_factor_count: 0,
100 };
101
102 // compute powers of two separately
103 result.power_two = n.trailing_zeros();
104 result.total_factor_count += result.power_two;
105 n >>= result.power_two;
106 if result.power_two > 0 {
107 result.distinct_factor_count += 1;
108 }
109
110 // also compute powers of three separately
111 while n % 3 == 0 {
112 result.power_three += 1;
113 n /= 3;
114 }
115 result.total_factor_count += result.power_three;
116 if result.power_three > 0 {
117 result.distinct_factor_count += 1;
118 }
119
120 // if we have any other factors, gather them in the "other factors" vec
121 if n > 1 {
122 let mut divisor = 5;
123 // compute divisor limit. if our divisor goes above this limit, we know we won't find any more factors. we'll revise it downwards as we discover factors.
124 let mut limit = (n as f32).sqrt() as usize + 1;
125 while divisor < limit {
126 // Count how many times this divisor divesthe remaining input
127 let mut count = 0;
128 while n % divisor == 0 {
129 n /= divisor;
130 count += 1;
131 }
132
133 // If this entry is actually a divisor of the given number, add it to the array
134 if count > 0 {
135 result.other_factors.push(PrimeFactor {
136 value: divisor,
137 count,
138 });
139 result.total_factor_count += count;
140 result.distinct_factor_count += 1;
141
142 // recalculate the limit to reduce the amount of other factors we need to check
143 limit = (n as f32).sqrt() as usize + 1;
144 }
145
146 divisor += 2;
147 }
148
149 // because of our limit logic, there might be one factor left
150 if n > 1 {
151 result
152 .other_factors
153 .push(PrimeFactor { value: n, count: 1 });
154 result.total_factor_count += 1;
155 result.distinct_factor_count += 1;
156 }
157 }
158
159 result
160 }
161
is_prime(&self) -> bool162 pub fn is_prime(&self) -> bool {
163 self.total_factor_count == 1
164 }
get_product(&self) -> usize165 pub fn get_product(&self) -> usize {
166 self.n
167 }
168 #[allow(unused)]
get_total_factor_count(&self) -> u32169 pub fn get_total_factor_count(&self) -> u32 {
170 self.total_factor_count
171 }
172 #[allow(unused)]
get_distinct_factor_count(&self) -> u32173 pub fn get_distinct_factor_count(&self) -> u32 {
174 self.distinct_factor_count
175 }
176 #[allow(unused)]
get_power_of_two(&self) -> u32177 pub fn get_power_of_two(&self) -> u32 {
178 self.power_two
179 }
180 #[allow(unused)]
get_power_of_three(&self) -> u32181 pub fn get_power_of_three(&self) -> u32 {
182 self.power_three
183 }
184 #[allow(unused)]
get_other_factors(&self) -> &[PrimeFactor]185 pub fn get_other_factors(&self) -> &[PrimeFactor] {
186 &self.other_factors
187 }
188
189 // Divides the number by the given prime factor. Returns None if the resulting number is one.
remove_factors(mut self, factor: PrimeFactor) -> Option<Self>190 pub fn remove_factors(mut self, factor: PrimeFactor) -> Option<Self> {
191 if factor.count == 0 {
192 return Some(self);
193 }
194 if factor.value == 2 {
195 self.power_two = self.power_two.checked_sub(factor.count).unwrap();
196 self.n >>= factor.count;
197 self.total_factor_count -= factor.count;
198 if self.power_two == 0 {
199 self.distinct_factor_count -= 1;
200 }
201 if self.n > 1 {
202 return Some(self);
203 }
204 } else if factor.value == 3 {
205 self.power_three = self.power_three.checked_sub(factor.count).unwrap();
206 self.n /= 3.pow(factor.count);
207 self.total_factor_count -= factor.count;
208 if self.power_two == 0 {
209 self.distinct_factor_count -= 1;
210 }
211 if self.n > 1 {
212 return Some(self);
213 }
214 } else {
215 let found_factor = self
216 .other_factors
217 .iter_mut()
218 .find(|item| item.value == factor.value)
219 .unwrap();
220 found_factor.count = found_factor.count.checked_sub(factor.count).unwrap();
221 self.n /= factor.value.pow(factor.count);
222 self.total_factor_count -= factor.count;
223 if found_factor.count == 0 {
224 self.distinct_factor_count -= 1;
225 self.other_factors.retain(|item| item.value != factor.value);
226 }
227 if self.n > 1 {
228 return Some(self);
229 }
230 }
231 None
232 }
233
234 // Splits this set of prime factors into two different sets so that the products of the two sets are as close as possible
partition_factors(mut self) -> (Self, Self)235 pub fn partition_factors(mut self) -> (Self, Self) {
236 // Make sure this isn't a prime number
237 assert!(!self.is_prime());
238
239 // If the given length is a perfect square, put the square root into both returned arays
240 if self.power_two % 2 == 0
241 && self.power_three % 2 == 0
242 && self
243 .other_factors
244 .iter()
245 .all(|factor| factor.count % 2 == 0)
246 {
247 let mut new_product = 1;
248
249 // cut our power of two in half
250 self.power_two /= 2;
251 new_product <<= self.power_two;
252
253 // cout our power of three in half
254 self.power_three /= 2;
255 new_product *= 3.pow(self.power_three);
256
257 // cut all our other factors in half
258 for factor in self.other_factors.iter_mut() {
259 factor.count /= 2;
260 new_product *= factor.value.pow(factor.count);
261 }
262
263 // update our cached properties and return 2 copies of ourself
264 self.total_factor_count /= 2;
265 self.n = new_product;
266 (self.clone(), self)
267 } else if self.distinct_factor_count == 1 {
268 // If there's only one factor, just split it as evenly as possible
269 let mut half = Self {
270 other_factors: Vec::new(),
271 n: self.n,
272 power_two: self.power_two / 2,
273 power_three: self.power_three / 2,
274 total_factor_count: self.total_factor_count / 2,
275 distinct_factor_count: 1,
276 };
277
278 // We computed one half via integer division -- compute the other half by subtracting the divided values fro mthe original
279 self.power_two -= half.power_two;
280 self.power_three -= half.power_three;
281 self.total_factor_count -= half.total_factor_count;
282
283 // Update the product values for each half, with different logic depending on what kind of single factor we have
284 if let Some(first_factor) = self.other_factors.first_mut() {
285 // we actualyl skipped updating the "other factor" earlier, so cut it in half and do the subtraction now
286 assert!(first_factor.count > 1); // If this is only one, then we're prime. we passed the "is_prime" assert earlier, so that would be a contradiction
287 let half_factor = PrimeFactor {
288 value: first_factor.value,
289 count: first_factor.count / 2,
290 };
291 first_factor.count -= half_factor.count;
292 half.other_factors.push(half_factor);
293
294 self.n = first_factor.value.pow(first_factor.count);
295 half.n = half_factor.value.pow(half_factor.count);
296 } else if half.power_two > 0 {
297 half.n = 1 << half.power_two;
298 self.n = 1 << self.power_two;
299 } else if half.power_three > 0 {
300 half.n = 3.pow(half.power_three);
301 self.n = 3.pow(self.power_three);
302 }
303
304 (self, half)
305 } else {
306 // we have a mixed bag of products. we're going to greedily try to evenly distribute entire groups of factors in one direction or the other
307 let mut left_product = 1;
308 let mut right_product = 1;
309
310 // for each factor, put it in whichever cumulative half is smaller
311 for factor in self.other_factors {
312 let factor_product = factor.value.pow(factor.count as u32);
313 if left_product <= right_product {
314 left_product *= factor_product;
315 } else {
316 right_product *= factor_product;
317 }
318 }
319 if left_product <= right_product {
320 left_product <<= self.power_two;
321 } else {
322 right_product <<= self.power_two;
323 }
324 if self.power_three > 0 && left_product <= right_product {
325 left_product *= 3.pow(self.power_three);
326 } else {
327 right_product *= 3.pow(self.power_three);
328 }
329
330 // now that we have our two products, compute a prime factorization for them
331 // we could maintain factor lists internally to save some computation and an allocation, but it led to a lot of code and this is so much simpler
332 (Self::compute(left_product), Self::compute(right_product))
333 }
334 }
335 }
336
337 #[derive(Copy, Clone, Debug)]
338 pub struct PartialFactors {
339 power2: u32,
340 power3: u32,
341 power5: u32,
342 power7: u32,
343 power11: u32,
344 other_factors: usize,
345 }
346 impl PartialFactors {
347 #[allow(unused)]
compute(len: usize) -> Self348 pub fn compute(len: usize) -> Self {
349 let power2 = len.trailing_zeros();
350 let mut other_factors = len >> power2;
351
352 let mut power3 = 0;
353 while other_factors % 3 == 0 {
354 power3 += 1;
355 other_factors /= 3;
356 }
357
358 let mut power5 = 0;
359 while other_factors % 5 == 0 {
360 power5 += 1;
361 other_factors /= 5;
362 }
363
364 let mut power7 = 0;
365 while other_factors % 7 == 0 {
366 power7 += 1;
367 other_factors /= 7;
368 }
369
370 let mut power11 = 0;
371 while other_factors % 11 == 0 {
372 power11 += 1;
373 other_factors /= 11;
374 }
375
376 Self {
377 power2,
378 power3,
379 power5,
380 power7,
381 power11,
382 other_factors,
383 }
384 }
385
386 #[allow(unused)]
get_power2(&self) -> u32387 pub fn get_power2(&self) -> u32 {
388 self.power2
389 }
390 #[allow(unused)]
get_power3(&self) -> u32391 pub fn get_power3(&self) -> u32 {
392 self.power3
393 }
394 #[allow(unused)]
get_power5(&self) -> u32395 pub fn get_power5(&self) -> u32 {
396 self.power5
397 }
398 #[allow(unused)]
get_power7(&self) -> u32399 pub fn get_power7(&self) -> u32 {
400 self.power7
401 }
402 #[allow(unused)]
get_power11(&self) -> u32403 pub fn get_power11(&self) -> u32 {
404 self.power11
405 }
406 #[allow(unused)]
get_other_factors(&self) -> usize407 pub fn get_other_factors(&self) -> usize {
408 self.other_factors
409 }
410 #[allow(unused)]
product(&self) -> usize411 pub fn product(&self) -> usize {
412 (self.other_factors
413 * 3.pow(self.power3)
414 * 5.pow(self.power5)
415 * 7.pow(self.power7)
416 * 11.pow(self.power11))
417 << self.power2
418 }
419 #[allow(unused)]
product_power2power3(&self) -> usize420 pub fn product_power2power3(&self) -> usize {
421 3.pow(self.power3) << self.power2
422 }
423 #[allow(unused)]
divide_by(&self, divisor: &PartialFactors) -> Option<PartialFactors>424 pub fn divide_by(&self, divisor: &PartialFactors) -> Option<PartialFactors> {
425 let two_divides = self.power2 >= divisor.power2;
426 let three_divides = self.power3 >= divisor.power3;
427 let five_divides = self.power5 >= divisor.power5;
428 let seven_divides = self.power7 >= divisor.power7;
429 let eleven_divides = self.power11 >= divisor.power11;
430 let other_divides = self.other_factors % divisor.other_factors == 0;
431 if two_divides
432 && three_divides
433 && five_divides
434 && seven_divides
435 && eleven_divides
436 && other_divides
437 {
438 Some(Self {
439 power2: self.power2 - divisor.power2,
440 power3: self.power3 - divisor.power3,
441 power5: self.power5 - divisor.power5,
442 power7: self.power7 - divisor.power7,
443 power11: self.power11 - divisor.power11,
444 other_factors: if self.other_factors == divisor.other_factors {
445 1
446 } else {
447 self.other_factors / divisor.other_factors
448 },
449 })
450 } else {
451 None
452 }
453 }
454 }
455
456 #[cfg(test)]
457 mod unit_tests {
458 use super::*;
459
460 #[test]
test_modular_exponent()461 fn test_modular_exponent() {
462 // make sure to test something that would overflow under ordinary circumstances
463 // ie 3 ^ 416788 mod 47
464 let test_list = vec![
465 ((2, 8, 300), 256),
466 ((2, 9, 300), 212),
467 ((1, 9, 300), 1),
468 ((3, 416788, 47), 8),
469 ];
470
471 for (input, expected) in test_list {
472 let (base, exponent, modulo) = input;
473
474 let result = modular_exponent(base, exponent, modulo);
475
476 assert_eq!(result, expected);
477 }
478 }
479
480 #[test]
test_primitive_root()481 fn test_primitive_root() {
482 let test_list = vec![(3, 2), (7, 3), (11, 2), (13, 2), (47, 5), (7919, 7)];
483
484 for (input, expected) in test_list {
485 let root = primitive_root(input).unwrap();
486
487 assert_eq!(root, expected);
488 }
489 }
490
491 #[test]
test_distinct_prime_factors()492 fn test_distinct_prime_factors() {
493 let test_list = vec![
494 (46, vec![2, 23]),
495 (2, vec![2]),
496 (3, vec![3]),
497 (162, vec![2, 3]),
498 ];
499
500 for (input, expected) in test_list {
501 let factors = distinct_prime_factors(input);
502
503 assert_eq!(factors, expected);
504 }
505 }
506
507 use std::collections::HashMap;
508
509 macro_rules! map{
510 { $($key:expr => $value:expr),+ } => {
511 {
512 let mut m = HashMap::new();
513 $(
514 m.insert($key, $value);
515 )+
516 m
517 }
518 };
519 }
520
assert_internally_consistent(prime_factors: &PrimeFactors)521 fn assert_internally_consistent(prime_factors: &PrimeFactors) {
522 let mut cumulative_product = 1;
523 let mut discovered_distinct_factors = 0;
524 let mut discovered_total_factors = 0;
525
526 if prime_factors.get_power_of_two() > 0 {
527 cumulative_product <<= prime_factors.get_power_of_two();
528 discovered_distinct_factors += 1;
529 discovered_total_factors += prime_factors.get_power_of_two();
530 }
531 if prime_factors.get_power_of_three() > 0 {
532 cumulative_product *= 3.pow(prime_factors.get_power_of_three());
533 discovered_distinct_factors += 1;
534 discovered_total_factors += prime_factors.get_power_of_three();
535 }
536 for factor in prime_factors.get_other_factors() {
537 assert!(factor.count > 0);
538 cumulative_product *= factor.value.pow(factor.count);
539 discovered_distinct_factors += 1;
540 discovered_total_factors += factor.count;
541 }
542
543 assert_eq!(prime_factors.get_product(), cumulative_product);
544 assert_eq!(
545 prime_factors.get_distinct_factor_count(),
546 discovered_distinct_factors
547 );
548 assert_eq!(
549 prime_factors.get_total_factor_count(),
550 discovered_total_factors
551 );
552 assert_eq!(prime_factors.is_prime(), discovered_total_factors == 1);
553 }
554
555 #[test]
test_prime_factors()556 fn test_prime_factors() {
557 #[derive(Debug)]
558 struct ExpectedData {
559 len: usize,
560 factors: HashMap<usize, u32>,
561 total_factors: u32,
562 distinct_factors: u32,
563 is_prime: bool,
564 }
565 impl ExpectedData {
566 fn new(
567 len: usize,
568 factors: HashMap<usize, u32>,
569 total_factors: u32,
570 distinct_factors: u32,
571 is_prime: bool,
572 ) -> Self {
573 Self {
574 len,
575 factors,
576 total_factors,
577 distinct_factors,
578 is_prime,
579 }
580 }
581 }
582
583 let test_list = vec![
584 ExpectedData::new(2, map! { 2 => 1 }, 1, 1, true),
585 ExpectedData::new(128, map! { 2 => 7 }, 7, 1, false),
586 ExpectedData::new(3, map! { 3 => 1 }, 1, 1, true),
587 ExpectedData::new(81, map! { 3 => 4 }, 4, 1, false),
588 ExpectedData::new(5, map! { 5 => 1 }, 1, 1, true),
589 ExpectedData::new(125, map! { 5 => 3 }, 3, 1, false),
590 ExpectedData::new(97, map! { 97 => 1 }, 1, 1, true),
591 ExpectedData::new(6, map! { 2 => 1, 3 => 1 }, 2, 2, false),
592 ExpectedData::new(12, map! { 2 => 2, 3 => 1 }, 3, 2, false),
593 ExpectedData::new(36, map! { 2 => 2, 3 => 2 }, 4, 2, false),
594 ExpectedData::new(10, map! { 2 => 1, 5 => 1 }, 2, 2, false),
595 ExpectedData::new(100, map! { 2 => 2, 5 => 2 }, 4, 2, false),
596 ExpectedData::new(44100, map! { 2 => 2, 3 => 2, 5 => 2, 7 => 2 }, 8, 4, false),
597 ];
598
599 for expected in test_list {
600 let factors = PrimeFactors::compute(expected.len);
601
602 assert_eq!(factors.get_product(), expected.len);
603 assert_eq!(factors.is_prime(), expected.is_prime);
604 assert_eq!(
605 factors.get_distinct_factor_count(),
606 expected.distinct_factors
607 );
608 assert_eq!(factors.get_total_factor_count(), expected.total_factors);
609 assert_eq!(
610 factors.get_power_of_two(),
611 expected.factors.get(&2).map_or(0, |i| *i)
612 );
613 assert_eq!(
614 factors.get_power_of_three(),
615 expected.factors.get(&3).map_or(0, |i| *i)
616 );
617
618 // verify that every factor in the "other factors" array matches our expected map
619 for factor in factors.get_other_factors() {
620 assert_eq!(factor.count, *expected.factors.get(&factor.value).unwrap());
621 }
622
623 // finally, verify that every factor in the "other factors" array was present in the "other factors" array
624 let mut found_factors: Vec<usize> = factors
625 .get_other_factors()
626 .iter()
627 .map(|factor| factor.value)
628 .collect();
629 if factors.get_power_of_two() > 0 {
630 found_factors.push(2);
631 }
632 if factors.get_power_of_three() > 0 {
633 found_factors.push(3);
634 }
635 for key in expected.factors.keys() {
636 assert!(found_factors.contains(key as &usize));
637 }
638 }
639
640 // in addition to our precomputed list, go through a bunch of ofther factors and just make sure they're internally consistent
641 for n in 1..200 {
642 let factors = PrimeFactors::compute(n);
643 assert_eq!(factors.get_product(), n);
644
645 assert_internally_consistent(&factors);
646 }
647 }
648
649 #[test]
test_partition_factors()650 fn test_partition_factors() {
651 // We aren't going to verify the actual return value of "partition_factors", we're justgoing to make sure each half is internally consistent
652 for n in 4..200 {
653 let factors = PrimeFactors::compute(n);
654 if !factors.is_prime() {
655 let (left_factors, right_factors) = factors.partition_factors();
656
657 assert!(left_factors.get_product() > 1);
658 assert!(right_factors.get_product() > 1);
659
660 assert_eq!(left_factors.get_product() * right_factors.get_product(), n);
661
662 assert_internally_consistent(&left_factors);
663 assert_internally_consistent(&right_factors);
664 }
665 }
666 }
667
668 #[test]
test_remove_factors()669 fn test_remove_factors() {
670 // For every possible factor of a bunch of factors, they removing each and making sure the result is internally consistent
671 for n in 2..200 {
672 let factors = PrimeFactors::compute(n);
673
674 for i in 0..=factors.get_power_of_two() {
675 if let Some(removed_factors) = factors
676 .clone()
677 .remove_factors(PrimeFactor { value: 2, count: i })
678 {
679 assert_eq!(removed_factors.get_product(), factors.get_product() >> i);
680 assert_internally_consistent(&removed_factors);
681 } else {
682 // If the method returned None, this must be a power of two and i must be equal to the product
683 assert!(n.is_power_of_two());
684 assert!(i == factors.get_power_of_two());
685 }
686 }
687 }
688 }
689
690 #[test]
test_partial_factors()691 fn test_partial_factors() {
692 #[derive(Debug)]
693 struct ExpectedData {
694 len: usize,
695 power2: u32,
696 power3: u32,
697 power5: u32,
698 power7: u32,
699 power11: u32,
700 other: usize,
701 }
702
703 let test_list = vec![
704 ExpectedData {
705 len: 2,
706 power2: 1,
707 power3: 0,
708 power5: 0,
709 power7: 0,
710 power11: 0,
711 other: 1,
712 },
713 ExpectedData {
714 len: 128,
715 power2: 7,
716 power3: 0,
717 power5: 0,
718 power7: 0,
719 power11: 0,
720 other: 1,
721 },
722 ExpectedData {
723 len: 3,
724 power2: 0,
725 power3: 1,
726 power5: 0,
727 power7: 0,
728 power11: 0,
729 other: 1,
730 },
731 ExpectedData {
732 len: 81,
733 power2: 0,
734 power3: 4,
735 power5: 0,
736 power7: 0,
737 power11: 0,
738 other: 1,
739 },
740 ExpectedData {
741 len: 5,
742 power2: 0,
743 power3: 0,
744 power5: 1,
745 power7: 0,
746 power11: 0,
747 other: 1,
748 },
749 ExpectedData {
750 len: 125,
751 power2: 0,
752 power3: 0,
753 power5: 3,
754 power7: 0,
755 power11: 0,
756 other: 1,
757 },
758 ExpectedData {
759 len: 97,
760 power2: 0,
761 power3: 0,
762 power5: 0,
763 power7: 0,
764 power11: 0,
765 other: 97,
766 },
767 ExpectedData {
768 len: 6,
769 power2: 1,
770 power3: 1,
771 power5: 0,
772 power7: 0,
773 power11: 0,
774 other: 1,
775 },
776 ExpectedData {
777 len: 12,
778 power2: 2,
779 power3: 1,
780 power5: 0,
781 power7: 0,
782 power11: 0,
783 other: 1,
784 },
785 ExpectedData {
786 len: 36,
787 power2: 2,
788 power3: 2,
789 power5: 0,
790 power7: 0,
791 power11: 0,
792 other: 1,
793 },
794 ExpectedData {
795 len: 10,
796 power2: 1,
797 power3: 0,
798 power5: 1,
799 power7: 0,
800 power11: 0,
801 other: 1,
802 },
803 ExpectedData {
804 len: 100,
805 power2: 2,
806 power3: 0,
807 power5: 2,
808 power7: 0,
809 power11: 0,
810 other: 1,
811 },
812 ExpectedData {
813 len: 44100,
814 power2: 2,
815 power3: 2,
816 power5: 2,
817 power7: 2,
818 power11: 0,
819 other: 1,
820 },
821 ExpectedData {
822 len: 2310,
823 power2: 1,
824 power3: 1,
825 power5: 1,
826 power7: 1,
827 power11: 1,
828 other: 1,
829 },
830 ];
831
832 for expected in test_list {
833 let factors = PartialFactors::compute(expected.len);
834
835 assert_eq!(factors.get_power2(), expected.power2);
836 assert_eq!(factors.get_power3(), expected.power3);
837 assert_eq!(factors.get_power5(), expected.power5);
838 assert_eq!(factors.get_power7(), expected.power7);
839 assert_eq!(factors.get_power11(), expected.power11);
840 assert_eq!(factors.get_other_factors(), expected.other);
841
842 assert_eq!(
843 expected.len,
844 (1 << factors.get_power2())
845 * 3.pow(factors.get_power3())
846 * 5.pow(factors.get_power5())
847 * 7.pow(factors.get_power7())
848 * 11.pow(factors.get_power11())
849 * factors.get_other_factors()
850 );
851 assert_eq!(expected.len, factors.product());
852 assert_eq!(
853 (1 << factors.get_power2()) * 3.pow(factors.get_power3()),
854 factors.product_power2power3()
855 );
856 assert_eq!(factors.get_other_factors().trailing_zeros(), 0);
857 assert!(factors.get_other_factors() % 3 > 0);
858 }
859
860 // in addition to our precomputed list, go through a bunch of ofther factors and just make sure they're internally consistent
861 for n in 1..200 {
862 let factors = PartialFactors::compute(n);
863
864 assert_eq!(
865 n,
866 (1 << factors.get_power2())
867 * 3.pow(factors.get_power3())
868 * 5.pow(factors.get_power5())
869 * 7.pow(factors.get_power7())
870 * 11.pow(factors.get_power11())
871 * factors.get_other_factors()
872 );
873 assert_eq!(n, factors.product());
874 assert_eq!(
875 (1 << factors.get_power2()) * 3.pow(factors.get_power3()),
876 factors.product_power2power3()
877 );
878 assert_eq!(factors.get_other_factors().trailing_zeros(), 0);
879 assert!(factors.get_other_factors() % 3 > 0);
880 }
881 }
882
883 #[test]
test_partial_factors_divide_by()884 fn test_partial_factors_divide_by() {
885 for n in 2..200 {
886 let factors = PartialFactors::compute(n);
887
888 for power2 in 0..5 {
889 for power3 in 0..4 {
890 for power5 in 0..3 {
891 for power7 in 0..3 {
892 for power11 in 0..2 {
893 for power13 in 0..2 {
894 let divisor_product = (3.pow(power3)
895 * 5.pow(power5)
896 * 7.pow(power7)
897 * 11.pow(power11)
898 * 13.pow(power13))
899 << power2;
900 let divisor = PartialFactors::compute(divisor_product);
901 if let Some(quotient) = factors.divide_by(&divisor) {
902 assert_eq!(quotient.product(), n / divisor_product);
903 } else {
904 assert!(n % divisor_product > 0);
905 }
906 }
907 }
908 }
909 }
910 }
911 }
912 }
913 }
914 }
915