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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

use crate::{
    matrix_addition_i64::add,
    matrix_multiplication_i64::mul,
    matrix_subtraction_i64::sub,
};

pub fn mod_mul(
    modulus: i64,
    a: &[Vec<i64>],
    b: &[Vec<i64>],
) -> Vec<Vec<i64>> {
    const B: u8 = 16;

    const M: i64 = (1 << B) - 1;

    assert!(modulus < 1 << (B << 1));

    let split = |a: &[Vec<i64>]| -> (Vec<Vec<i64>>, Vec<Vec<i64>>) {
        // a = a1 * B^1 + a0 * B^0
        let h = a.len();

        let w = a[0].len();

        let mut a0 = vec![vec![0; w]; h];

        let mut a1 = vec![vec![0; w]; h];

        for (i, row) in a.iter().enumerate() {
            for (j, x) in row.iter().enumerate() {
                a0[i][j] = x & M;

                a1[i][j] = x >> B;
            }
        }

        (a0, a1)
    };

    let merge =
        |a0: &[Vec<i64>], a1: &[Vec<i64>], a2: &[Vec<i64>]| -> Vec<Vec<i64>> {
            let h = a0.len();

            let w = a0[0].len();

            let mut a = vec![vec![0; w]; h];

            for i in 0..h {
                for j in 0..w {
                    let x = &mut a[i][j];

                    *x += a2[i][j] << (B << 1);

                    *x += a1[i][j] << B;

                    *x += a0[i][j];
                }
            }

            a
        };

    let take_mod = |a: &mut [Vec<i64>]| {
        for row in a.iter_mut() {
            for x in row.iter_mut() {
                *x %= modulus;

                if *x < 0 {
                    *x += modulus;
                }
            }
        }
    };

    let (a0, a1) = split(a);

    let (b0, b1) = split(b);

    let mut c0 = mul(&a0, &b0);

    take_mod(&mut c0);

    let mut c2 = mul(&a1, &b1);

    take_mod(&mut c2);

    let mut c1 = mul(&add(&a0, &a1), &add(&b0, &b1));

    c1 = sub(&sub(&c1, &c0), &c2);

    take_mod(&mut c1);

    let mut c = merge(&c0, &c1, &c2);

    take_mod(&mut c);

    c
}

#[cfg(test)]

mod tests {

    use super::*;

    #[test]

    fn test() {
        let a = vec![vec![0, 1], vec![2, 3], vec![4, 5]];

        let b = vec![vec![0, 1, 2], vec![3, 4, 5]];

        let c = mod_mul(1_000_000_007, &a, &b);

        assert_eq!(c, [[3, 4, 5,], [9, 14, 19,], [15, 24, 33,]]);
    }
}