| 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 |
} |