haar_lib/math/
garner.rs

1//! Garner's algorithm
2use crate::math::mod_ops::inv::mod_inv;
3
4/// $$ \begin{aligned}
5/// x \equiv r_1 \pmod {m_1} \\\\
6/// x \equiv r_2 \pmod {m_2} \\\\
7/// \vdots \\\\
8/// x \equiv r_n \pmod {m_n}
9/// \end{aligned} $$
10/// を満たす$x \pmod {modulo}$を求める。
11/// そのような$x$が存在しなければ`None`を返す。
12pub fn garner(r: Vec<u64>, mut m: Vec<u64>, modulo: u64) -> Option<u64> {
13    assert_eq!(r.len(), m.len());
14    assert!(!r.is_empty());
15
16    m.push(modulo);
17
18    let n = r.len();
19    let mut coeffs = vec![1; n + 1];
20    let mut constants = vec![0; n + 1];
21
22    for k in 0..n {
23        let t = ((r[k] + m[k] - constants[k]) % m[k] * mod_inv(coeffs[k], m[k])?) % m[k];
24
25        for i in k + 1..n + 1 {
26            constants[i] += t * coeffs[i] % m[i];
27            constants[i] %= m[i];
28            coeffs[i] *= m[k];
29            coeffs[i] %= m[i];
30        }
31    }
32
33    Some(*constants.last().unwrap())
34}
35
36#[cfg(test)]
37mod tests {
38    use crate::iter::collect::CollectVec;
39
40    use super::*;
41
42    #[test]
43    fn test() {
44        let m = vec![17, 23, 29, 35];
45        let modulo = 31;
46
47        for x in 0..=1000 {
48            let r = m.iter().map(|&m| x % m).collect_vec();
49            assert_eq!(garner(r, m.clone(), modulo).unwrap(), x % modulo);
50        }
51    }
52
53    #[test]
54    fn test_failure() {
55        assert_eq!(garner(vec![1, 2], vec![6, 8], 100), None);
56    }
57}
haar_lib/math/garner.rs

haar_lib/math/
garner.rs
