use num_bigint::BigInt;
use num_traits::{Signed, ToPrimitive, Zero};
use super::source::RandomSource;
#[derive(Clone, Debug)]
pub(crate) struct SubsetIndices {
n: i64,
k: i64,
i: i64,
index: i64,
a: i64,
m: i64,
c: i64,
}
impl SubsetIndices {
pub(crate) fn new(count: i32, size: i32, src: &mut dyn RandomSource) -> Self {
if size <= 0 {
return Self {
n: 0,
k: 0,
i: 0,
index: 0,
a: 0,
m: 1,
c: 0,
};
}
let (modulus, multiplier) = optimal_m_and_a(size);
let index = i64::from(src.next_int_bounded(size).unwrap_or(0));
let increment = i64::from(src.next_prime());
Self {
n: i64::from(size),
k: i64::from(count),
i: 0,
index,
a: multiplier,
m: modulus,
c: increment,
}
}
pub(crate) fn next_index(&mut self) -> Option<usize> {
if self.i >= self.k {
return None;
}
self.i += 1;
loop {
self.index = (self.a * self.index + self.c) % self.m;
if self.index < self.n {
break;
}
}
usize::try_from(self.index).ok()
}
}
fn optimal_m_and_a(size: i32) -> (i64, i64) {
let mut n = i64::from(size.max(9));
let mut factors = prime_factors(n);
while n % 4 == 0 || is_square_free(&factors) {
n += 1;
factors = prime_factors(n);
}
let mut distinct = factors.clone();
distinct.dedup();
let a = distinct.iter().product::<i64>() + 1;
(n, a)
}
fn prime_factors(mut n: i64) -> Vec<i64> {
let mut out = Vec::new();
let mut p = 2;
while p * p <= n {
while n % p == 0 {
out.push(p);
n /= p;
}
p += if p == 2 { 1 } else { 2 };
}
if n > 1 {
out.push(n);
}
out
}
fn is_square_free(sorted_factors: &[i64]) -> bool {
sorted_factors.windows(2).all(|w| w[0] != w[1])
}
#[derive(Clone, Debug)]
pub(crate) struct BigIndices {
a: BigInt,
size: BigInt,
k: i64,
i: i64,
}
impl BigIndices {
pub(crate) fn new(k: i32, size: BigInt, src: &mut dyn RandomSource) -> Self {
let r = src.next_long();
let a = BigInt::from(r.wrapping_abs());
Self {
a,
size,
k: i64::from(k),
i: 0,
}
}
pub(crate) fn next_index(&mut self) -> Option<BigInt> {
if self.i >= self.k || self.size.is_zero() {
return None;
}
let x = BigInt::from(i64::MAX - 24);
let v = x * BigInt::from(self.i) + &self.a;
self.i += 1;
let mut r = v % &self.size;
if r.is_negative() {
r += &self.size;
}
Some(r)
}
}
pub(crate) fn big_digit(idx: &BigInt, rescale: &BigInt, radix: usize) -> usize {
let r = BigInt::from(radix);
let mut d = (idx / rescale) % &r;
if d.is_negative() {
d += r;
}
d.to_usize().unwrap_or(0)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn m_and_a_follow_tlc() {
assert_eq!(optimal_m_and_a(1), (9, 4));
assert_eq!(optimal_m_and_a(9), (9, 4));
assert_eq!(optimal_m_and_a(10), (18, 7));
for (size, m, a) in [
(1, 9, 4),
(2, 9, 4),
(8, 9, 4),
(11, 18, 7),
(100, 117, 40),
(1000, 1014, 79),
(65_536, 65_538, 21_847),
(1_000_000, 1_000_017, 333_340),
(1_000_003, 1_000_017, 333_340),
(999_999_937, 999_999_938, 142_857_135),
(2_147_483_646, 2_147_483_646, 715_827_883),
(i32::MAX, 2_147_483_650, 429_496_731),
] {
assert_eq!(optimal_m_and_a(size), (m, a), "size {size}");
}
}
#[test]
fn first_n_indices_are_a_permutation() {
let mut src = super::super::source::JavaRandom::new(3);
for n in [1, 2, 5, 9, 10, 37, 100] {
let mut e = SubsetIndices::new(n, n, &mut src);
let mut seen: Vec<usize> = std::iter::from_fn(|| e.next_index()).collect();
seen.sort_unstable();
assert_eq!(
seen,
(0..usize::try_from(n).unwrap_or(0)).collect::<Vec<_>>()
);
}
}
}