Debian Codegraph @

.cargo/vendor/rustfft/src/math_utils.rs

raw
1 use num_traits::{One, PrimInt, Zero};
2
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
23 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
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 {
92 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
162 pub fn is_prime(&self) -> bool {
163 self.total_factor_count == 1
164 }
165 pub fn get_product(&self) -> usize {
166 self.n
167 }
168 #[allow(unused)]
169 pub fn get_total_factor_count(&self) -> u32 {
170 self.total_factor_count
171 }
172 #[allow(unused)]
173 pub fn get_distinct_factor_count(&self) -> u32 {
174 self.distinct_factor_count
175 }
176 #[allow(unused)]
177 pub fn get_power_of_two(&self) -> u32 {
178 self.power_two
179 }
180 #[allow(unused)]
181 pub fn get_power_of_three(&self) -> u32 {
182 self.power_three
183 }
184 #[allow(unused)]
185 pub fn get_other_factors(&self) -> &[PrimeFactor] {
186 &self.other_factors
187 }
188
189 pub fn is_power_of_three(&self) -> bool {
190 self.power_three > 0 && self.power_two == 0 && self.other_factors.len() == 0
191 }
192
193 // Divides the number by the given prime factor. Returns None if the resulting number is one.
194 pub fn remove_factors(mut self, factor: PrimeFactor) -> Option<Self> {
195 if factor.count == 0 {
196 return Some(self);
197 }
198 if factor.value == 2 {
199 self.power_two = self.power_two.checked_sub(factor.count).unwrap();
200 self.n >>= factor.count;
201 self.total_factor_count -= factor.count;
202 if self.power_two == 0 {
203 self.distinct_factor_count -= 1;
204 }
205 if self.n > 1 {
206 return Some(self);
207 }
208 } else if factor.value == 3 {
209 self.power_three = self.power_three.checked_sub(factor.count).unwrap();
210 self.n /= 3.pow(factor.count);
211 self.total_factor_count -= factor.count;
212 if self.power_two == 0 {
213 self.distinct_factor_count -= 1;
214 }
215 if self.n > 1 {
216 return Some(self);
217 }
218 } else {
219 let found_factor = self
220 .other_factors
221 .iter_mut()
222 .find(|item| item.value == factor.value)
223 .unwrap();
224 found_factor.count = found_factor.count.checked_sub(factor.count).unwrap();
225 self.n /= factor.value.pow(factor.count);
226 self.total_factor_count -= factor.count;
227 if found_factor.count == 0 {
228 self.distinct_factor_count -= 1;
229 self.other_factors.retain(|item| item.value != factor.value);
230 }
231 if self.n > 1 {
232 return Some(self);
233 }
234 }
235 None
236 }
237
238 // Splits this set of prime factors into two different sets so that the products of the two sets are as close as possible
239 pub fn partition_factors(mut self) -> (Self, Self) {
240 // Make sure this isn't a prime number
241 assert!(!self.is_prime());
242
243 // If the given length is a perfect square, put the square root into both returned arays
244 if self.power_two % 2 == 0
245 && self.power_three % 2 == 0
246 && self
247 .other_factors
248 .iter()
249 .all(|factor| factor.count % 2 == 0)
250 {
251 let mut new_product = 1;
252
253 // cut our power of two in half
254 self.power_two /= 2;
255 new_product <<= self.power_two;
256
257 // cout our power of three in half
258 self.power_three /= 2;
259 new_product *= 3.pow(self.power_three);
260
261 // cut all our other factors in half
262 for factor in self.other_factors.iter_mut() {
263 factor.count /= 2;
264 new_product *= factor.value.pow(factor.count);
265 }
266
267 // update our cached properties and return 2 copies of ourself
268 self.total_factor_count /= 2;
269 self.n = new_product;
270 (self.clone(), self)
271 } else if self.distinct_factor_count == 1 {
272 // If there's only one factor, just split it as evenly as possible
273 let mut half = Self {
274 other_factors: Vec::new(),
275 n: self.n,
276 power_two: self.power_two / 2,
277 power_three: self.power_three / 2,
278 total_factor_count: self.total_factor_count / 2,
279 distinct_factor_count: 1,
280 };
281
282 // We computed one half via integer division -- compute the other half by subtracting the divided values fro mthe original
283 self.power_two -= half.power_two;
284 self.power_three -= half.power_three;
285 self.total_factor_count -= half.total_factor_count;
286
287 // Update the product values for each half, with different logic depending on what kind of single factor we have
288 if let Some(first_factor) = self.other_factors.first_mut() {
289 // we actualyl skipped updating the "other factor" earlier, so cut it in half and do the subtraction now
290 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
291 let half_factor = PrimeFactor {
292 value: first_factor.value,
293 count: first_factor.count / 2,
294 };
295 first_factor.count -= half_factor.count;
296 half.other_factors.push(half_factor);
297
298 self.n = first_factor.value.pow(first_factor.count);
299 half.n = half_factor.value.pow(half_factor.count);
300 } else if half.power_two > 0 {
301 half.n = 1 << half.power_two;
302 self.n = 1 << self.power_two;
303 } else if half.power_three > 0 {
304 half.n = 3.pow(half.power_three);
305 self.n = 3.pow(self.power_three);
306 }
307
308 (self, half)
309 } else {
310 // 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
311 let mut left_product = 1;
312 let mut right_product = 1;
313
314 // for each factor, put it in whichever cumulative half is smaller
315 for factor in self.other_factors {
316 let factor_product = factor.value.pow(factor.count as u32);
317 if left_product <= right_product {
318 left_product *= factor_product;
319 } else {
320 right_product *= factor_product;
321 }
322 }
323 if left_product <= right_product {
324 left_product <<= self.power_two;
325 } else {
326 right_product <<= self.power_two;
327 }
328 if self.power_three > 0 && left_product <= right_product {
329 left_product *= 3.pow(self.power_three);
330 } else {
331 right_product *= 3.pow(self.power_three);
332 }
333
334 // now that we have our two products, compute a prime factorization for them
335 // 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
336 (Self::compute(left_product), Self::compute(right_product))
337 }
338 }
339 }
340
341 #[derive(Copy, Clone, Debug)]
342 pub struct PartialFactors {
343 power2: u32,
344 power3: u32,
345 power5: u32,
346 power7: u32,
347 power11: u32,
348 other_factors: usize,
349 }
350 impl PartialFactors {
351 #[allow(unused)]
352 pub fn compute(len: usize) -> Self {
353 let power2 = len.trailing_zeros();
354 let mut other_factors = len >> power2;
355
356 let mut power3 = 0;
357 while other_factors % 3 == 0 {
358 power3 += 1;
359 other_factors /= 3;
360 }
361
362 let mut power5 = 0;
363 while other_factors % 5 == 0 {
364 power5 += 1;
365 other_factors /= 5;
366 }
367
368 let mut power7 = 0;
369 while other_factors % 7 == 0 {
370 power7 += 1;
371 other_factors /= 7;
372 }
373
374 let mut power11 = 0;
375 while other_factors % 11 == 0 {
376 power11 += 1;
377 other_factors /= 11;
378 }
379
380 Self {
381 power2,
382 power3,
383 power5,
384 power7,
385 power11,
386 other_factors,
387 }
388 }
389
390 #[allow(unused)]
391 pub fn get_power2(&self) -> u32 {
392 self.power2
393 }
394 #[allow(unused)]
395 pub fn get_power3(&self) -> u32 {
396 self.power3
397 }
398 #[allow(unused)]
399 pub fn get_power5(&self) -> u32 {
400 self.power5
401 }
402 #[allow(unused)]
403 pub fn get_power7(&self) -> u32 {
404 self.power7
405 }
406 #[allow(unused)]
407 pub fn get_power11(&self) -> u32 {
408 self.power11
409 }
410 #[allow(unused)]
411 pub fn get_other_factors(&self) -> usize {
412 self.other_factors
413 }
414 #[allow(unused)]
415 pub fn product(&self) -> usize {
416 (self.other_factors
417 * 3.pow(self.power3)
418 * 5.pow(self.power5)
419 * 7.pow(self.power7)
420 * 11.pow(self.power11))
421 << self.power2
422 }
423 #[allow(unused)]
424 pub fn product_power2power3(&self) -> usize {
425 3.pow(self.power3) << self.power2
426 }
427 #[allow(unused)]
428 pub fn divide_by(&self, divisor: &PartialFactors) -> Option<PartialFactors> {
429 let two_divides = self.power2 >= divisor.power2;
430 let three_divides = self.power3 >= divisor.power3;
431 let five_divides = self.power5 >= divisor.power5;
432 let seven_divides = self.power7 >= divisor.power7;
433 let eleven_divides = self.power11 >= divisor.power11;
434 let other_divides = self.other_factors % divisor.other_factors == 0;
435 if two_divides
436 && three_divides
437 && five_divides
438 && seven_divides
439 && eleven_divides
440 && other_divides
441 {
442 Some(Self {
443 power2: self.power2 - divisor.power2,
444 power3: self.power3 - divisor.power3,
445 power5: self.power5 - divisor.power5,
446 power7: self.power7 - divisor.power7,
447 power11: self.power11 - divisor.power11,
448 other_factors: if self.other_factors == divisor.other_factors {
449 1
450 } else {
451 self.other_factors / divisor.other_factors
452 },
453 })
454 } else {
455 None
456 }
457 }
458 }
459
460 #[cfg(test)]
461 mod unit_tests {
462 use super::*;
463
464 #[test]
465 fn test_modular_exponent() {
466 // make sure to test something that would overflow under ordinary circumstances
467 // ie 3 ^ 416788 mod 47
468 let test_list = vec![
469 ((2, 8, 300), 256),
470 ((2, 9, 300), 212),
471 ((1, 9, 300), 1),
472 ((3, 416788, 47), 8),
473 ];
474
475 for (input, expected) in test_list {
476 let (base, exponent, modulo) = input;
477
478 let result = modular_exponent(base, exponent, modulo);
479
480 assert_eq!(result, expected);
481 }
482 }
483
484 #[test]
485 fn test_primitive_root() {
486 let test_list = vec![(3, 2), (7, 3), (11, 2), (13, 2), (47, 5), (7919, 7)];
487
488 for (input, expected) in test_list {
489 let root = primitive_root(input).unwrap();
490
491 assert_eq!(root, expected);
492 }
493 }
494
495 #[test]
496 fn test_distinct_prime_factors() {
497 let test_list = vec![
498 (46, vec![2, 23]),
499 (2, vec![2]),
500 (3, vec![3]),
501 (162, vec![2, 3]),
502 ];
503
504 for (input, expected) in test_list {
505 let factors = distinct_prime_factors(input);
506
507 assert_eq!(factors, expected);
508 }
509 }
510
511 use std::collections::HashMap;
512
513 macro_rules! map{
514 { $($key:expr => $value:expr),+ } => {
515 {
516 let mut m = HashMap::new();
517 $(
518 m.insert($key, $value);
519 )+
520 m
521 }
522 };
523 }
524
525 fn assert_internally_consistent(prime_factors: &PrimeFactors) {
526 let mut cumulative_product = 1;
527 let mut discovered_distinct_factors = 0;
528 let mut discovered_total_factors = 0;
529
530 if prime_factors.get_power_of_two() > 0 {
531 cumulative_product <<= prime_factors.get_power_of_two();
532 discovered_distinct_factors += 1;
533 discovered_total_factors += prime_factors.get_power_of_two();
534 }
535 if prime_factors.get_power_of_three() > 0 {
536 cumulative_product *= 3.pow(prime_factors.get_power_of_three());
537 discovered_distinct_factors += 1;
538 discovered_total_factors += prime_factors.get_power_of_three();
539 }
540 for factor in prime_factors.get_other_factors() {
541 assert!(factor.count > 0);
542 cumulative_product *= factor.value.pow(factor.count);
543 discovered_distinct_factors += 1;
544 discovered_total_factors += factor.count;
545 }
546
547 assert_eq!(prime_factors.get_product(), cumulative_product);
548 assert_eq!(
549 prime_factors.get_distinct_factor_count(),
550 discovered_distinct_factors
551 );
552 assert_eq!(
553 prime_factors.get_total_factor_count(),
554 discovered_total_factors
555 );
556 assert_eq!(prime_factors.is_prime(), discovered_total_factors == 1);
557 }
558
559 #[test]
560 fn test_prime_factors() {
561 #[derive(Debug)]
562 struct ExpectedData {
563 len: usize,
564 factors: HashMap<usize, u32>,
565 total_factors: u32,
566 distinct_factors: u32,
567 is_prime: bool,
568 }
569 impl ExpectedData {
570 fn new(
571 len: usize,
572 factors: HashMap<usize, u32>,
573 total_factors: u32,
574 distinct_factors: u32,
575 is_prime: bool,
576 ) -> Self {
577 Self {
578 len,
579 factors,
580 total_factors,
581 distinct_factors,
582 is_prime,
583 }
584 }
585 }
586
587 let test_list = vec![
588 ExpectedData::new(2, map! { 2 => 1 }, 1, 1, true),
589 ExpectedData::new(128, map! { 2 => 7 }, 7, 1, false),
590 ExpectedData::new(3, map! { 3 => 1 }, 1, 1, true),
591 ExpectedData::new(81, map! { 3 => 4 }, 4, 1, false),
592 ExpectedData::new(5, map! { 5 => 1 }, 1, 1, true),
593 ExpectedData::new(125, map! { 5 => 3 }, 3, 1, false),
594 ExpectedData::new(97, map! { 97 => 1 }, 1, 1, true),
595 ExpectedData::new(6, map! { 2 => 1, 3 => 1 }, 2, 2, false),
596 ExpectedData::new(12, map! { 2 => 2, 3 => 1 }, 3, 2, false),
597 ExpectedData::new(36, map! { 2 => 2, 3 => 2 }, 4, 2, false),
598 ExpectedData::new(10, map! { 2 => 1, 5 => 1 }, 2, 2, false),
599 ExpectedData::new(100, map! { 2 => 2, 5 => 2 }, 4, 2, false),
600 ExpectedData::new(44100, map! { 2 => 2, 3 => 2, 5 => 2, 7 => 2 }, 8, 4, false),
601 ];
602
603 for expected in test_list {
604 let factors = PrimeFactors::compute(expected.len);
605
606 assert_eq!(factors.get_product(), expected.len);
607 assert_eq!(factors.is_prime(), expected.is_prime);
608 assert_eq!(
609 factors.get_distinct_factor_count(),
610 expected.distinct_factors
611 );
612 assert_eq!(factors.get_total_factor_count(), expected.total_factors);
613 assert_eq!(
614 factors.get_power_of_two(),
615 expected.factors.get(&2).map_or(0, |i| *i)
616 );
617 assert_eq!(
618 factors.get_power_of_three(),
619 expected.factors.get(&3).map_or(0, |i| *i)
620 );
621
622 // verify that every factor in the "other factors" array matches our expected map
623 for factor in factors.get_other_factors() {
624 assert_eq!(factor.count, *expected.factors.get(&factor.value).unwrap());
625 }
626
627 // finally, verify that every factor in the "other factors" array was present in the "other factors" array
628 let mut found_factors: Vec<usize> = factors
629 .get_other_factors()
630 .iter()
631 .map(|factor| factor.value)
632 .collect();
633 if factors.get_power_of_two() > 0 {
634 found_factors.push(2);
635 }
636 if factors.get_power_of_three() > 0 {
637 found_factors.push(3);
638 }
639 for key in expected.factors.keys() {
640 assert!(found_factors.contains(key as &usize));
641 }
642 }
643
644 // in addition to our precomputed list, go through a bunch of ofther factors and just make sure they're internally consistent
645 for n in 1..200 {
646 let factors = PrimeFactors::compute(n);
647 assert_eq!(factors.get_product(), n);
648
649 assert_internally_consistent(&factors);
650 }
651 }
652
653 #[test]
654 fn test_partition_factors() {
655 // We aren't going to verify the actual return value of "partition_factors", we're justgoing to make sure each half is internally consistent
656 for n in 4..200 {
657 let factors = PrimeFactors::compute(n);
658 if !factors.is_prime() {
659 let (left_factors, right_factors) = factors.partition_factors();
660
661 assert!(left_factors.get_product() > 1);
662 assert!(right_factors.get_product() > 1);
663
664 assert_eq!(left_factors.get_product() * right_factors.get_product(), n);
665
666 assert_internally_consistent(&left_factors);
667 assert_internally_consistent(&right_factors);
668 }
669 }
670 }
671
672 #[test]
673 fn test_remove_factors() {
674 // For every possible factor of a bunch of factors, they removing each and making sure the result is internally consistent
675 for n in 2..200 {
676 let factors = PrimeFactors::compute(n);
677
678 for i in 0..=factors.get_power_of_two() {
679 if let Some(removed_factors) = factors
680 .clone()
681 .remove_factors(PrimeFactor { value: 2, count: i })
682 {
683 assert_eq!(removed_factors.get_product(), factors.get_product() >> i);
684 assert_internally_consistent(&removed_factors);
685 } else {
686 // If the method returned None, this must be a power of two and i must be equal to the product
687 assert!(n.is_power_of_two());
688 assert!(i == factors.get_power_of_two());
689 }
690 }
691 }
692 }
693
694 #[test]
695 fn test_partial_factors() {
696 #[derive(Debug)]
697 struct ExpectedData {
698 len: usize,
699 power2: u32,
700 power3: u32,
701 power5: u32,
702 power7: u32,
703 power11: u32,
704 other: usize,
705 }
706
707 let test_list = vec![
708 ExpectedData {
709 len: 2,
710 power2: 1,
711 power3: 0,
712 power5: 0,
713 power7: 0,
714 power11: 0,
715 other: 1,
716 },
717 ExpectedData {
718 len: 128,
719 power2: 7,
720 power3: 0,
721 power5: 0,
722 power7: 0,
723 power11: 0,
724 other: 1,
725 },
726 ExpectedData {
727 len: 3,
728 power2: 0,
729 power3: 1,
730 power5: 0,
731 power7: 0,
732 power11: 0,
733 other: 1,
734 },
735 ExpectedData {
736 len: 81,
737 power2: 0,
738 power3: 4,
739 power5: 0,
740 power7: 0,
741 power11: 0,
742 other: 1,
743 },
744 ExpectedData {
745 len: 5,
746 power2: 0,
747 power3: 0,
748 power5: 1,
749 power7: 0,
750 power11: 0,
751 other: 1,
752 },
753 ExpectedData {
754 len: 125,
755 power2: 0,
756 power3: 0,
757 power5: 3,
758 power7: 0,
759 power11: 0,
760 other: 1,
761 },
762 ExpectedData {
763 len: 97,
764 power2: 0,
765 power3: 0,
766 power5: 0,
767 power7: 0,
768 power11: 0,
769 other: 97,
770 },
771 ExpectedData {
772 len: 6,
773 power2: 1,
774 power3: 1,
775 power5: 0,
776 power7: 0,
777 power11: 0,
778 other: 1,
779 },
780 ExpectedData {
781 len: 12,
782 power2: 2,
783 power3: 1,
784 power5: 0,
785 power7: 0,
786 power11: 0,
787 other: 1,
788 },
789 ExpectedData {
790 len: 36,
791 power2: 2,
792 power3: 2,
793 power5: 0,
794 power7: 0,
795 power11: 0,
796 other: 1,
797 },
798 ExpectedData {
799 len: 10,
800 power2: 1,
801 power3: 0,
802 power5: 1,
803 power7: 0,
804 power11: 0,
805 other: 1,
806 },
807 ExpectedData {
808 len: 100,
809 power2: 2,
810 power3: 0,
811 power5: 2,
812 power7: 0,
813 power11: 0,
814 other: 1,
815 },
816 ExpectedData {
817 len: 44100,
818 power2: 2,
819 power3: 2,
820 power5: 2,
821 power7: 2,
822 power11: 0,
823 other: 1,
824 },
825 ExpectedData {
826 len: 2310,
827 power2: 1,
828 power3: 1,
829 power5: 1,
830 power7: 1,
831 power11: 1,
832 other: 1,
833 },
834 ];
835
836 for expected in test_list {
837 let factors = PartialFactors::compute(expected.len);
838
839 assert_eq!(factors.get_power2(), expected.power2);
840 assert_eq!(factors.get_power3(), expected.power3);
841 assert_eq!(factors.get_power5(), expected.power5);
842 assert_eq!(factors.get_power7(), expected.power7);
843 assert_eq!(factors.get_power11(), expected.power11);
844 assert_eq!(factors.get_other_factors(), expected.other);
845
846 assert_eq!(
847 expected.len,
848 (1 << factors.get_power2())
849 * 3.pow(factors.get_power3())
850 * 5.pow(factors.get_power5())
851 * 7.pow(factors.get_power7())
852 * 11.pow(factors.get_power11())
853 * factors.get_other_factors()
854 );
855 assert_eq!(expected.len, factors.product());
856 assert_eq!(
857 (1 << factors.get_power2()) * 3.pow(factors.get_power3()),
858 factors.product_power2power3()
859 );
860 assert_eq!(factors.get_other_factors().trailing_zeros(), 0);
861 assert!(factors.get_other_factors() % 3 > 0);
862 }
863
864 // in addition to our precomputed list, go through a bunch of ofther factors and just make sure they're internally consistent
865 for n in 1..200 {
866 let factors = PartialFactors::compute(n);
867
868 assert_eq!(
869 n,
870 (1 << factors.get_power2())
871 * 3.pow(factors.get_power3())
872 * 5.pow(factors.get_power5())
873 * 7.pow(factors.get_power7())
874 * 11.pow(factors.get_power11())
875 * factors.get_other_factors()
876 );
877 assert_eq!(n, factors.product());
878 assert_eq!(
879 (1 << factors.get_power2()) * 3.pow(factors.get_power3()),
880 factors.product_power2power3()
881 );
882 assert_eq!(factors.get_other_factors().trailing_zeros(), 0);
883 assert!(factors.get_other_factors() % 3 > 0);
884 }
885 }
886
887 #[test]
888 fn test_partial_factors_divide_by() {
889 for n in 2..200 {
890 let factors = PartialFactors::compute(n);
891
892 for power2 in 0..5 {
893 for power3 in 0..4 {
894 for power5 in 0..3 {
895 for power7 in 0..3 {
896 for power11 in 0..2 {
897 for power13 in 0..2 {
898 let divisor_product = (3.pow(power3)
899 * 5.pow(power5)
900 * 7.pow(power7)
901 * 11.pow(power11)
902 * 13.pow(power13))
903 << power2;
904 let divisor = PartialFactors::compute(divisor_product);
905 if let Some(quotient) = factors.divide_by(&divisor) {
906 assert_eq!(quotient.product(), n / divisor_product);
907 } else {
908 assert!(n % divisor_product > 0);
909 }
910 }
911 }
912 }
913 }
914 }
915 }
916 }
917 }
918 }