dsalgo 0.3.10

A package for Datastructures and Algorithms.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

/// compile time optimized version of MontgomeryMultiplication.
/// two times faster.

pub struct MontgomeryMultiplication64 {
    n: u128,
    r2: u128,
    n_dash: u128,
    nr: u128,
}

impl MontgomeryMultiplication64 {
    const MASK: u128 = std::u64::MAX as u128;

    const R: u128 = 1 << 64;

    pub fn new(modulus: u64) -> Self {
        assert!(modulus & 1 == 1 && modulus >= 3);

        let n = modulus as u128;

        let r2 = (Self::R % n).pow(2) % n;

        let mut n_dash = 0;

        let mut t = 0;

        for i in 0..64 {
            if t & 1 == 0 {
                t += n;

                n_dash |= 1 << i;
            }

            t >>= 1;
        }

        debug_assert_eq!(n * n_dash & Self::MASK, Self::MASK);

        let nr = n * Self::R;

        Self { n, r2, n_dash, nr }
    }

    fn reduce(
        &self,
        mut t: u128,
    ) -> u64 {
        assert!(t < self.nr);

        t = (t + ((t & Self::MASK) * self.n_dash & Self::MASK) * self.n) >> 64;

        if t >= self.n {
            t -= self.n;
        }

        debug_assert!(t < self.n);

        t as u64
    }

    #[allow(dead_code)]

    fn form(
        &self,
        x: u64,
    ) -> u128 {
        self.reduce(x as u128 * self.r2) as u128
    }

    pub fn mul(
        &self,
        x: u64,
        y: u64,
    ) -> u64 {
        self.reduce(self.reduce(x as u128 * y as u128) as u128 * self.r2) as u64
    }
}

#[cfg(test)]

mod tests {

    #[test]

    fn test() {}
}