hmath/ubigint/arith/
mul.rs

1use crate::UBigInt;
2use crate::utils::{v64_to_v32, remove_suffix_0};
3
4const KARATSUBA_THRES: usize = 64;
5
6#[cfg(test)]
7const KARATSUBA_TEST: bool = crate::consts::RUN_ALL_TESTS & true;
8
9#[cfg(test)]
10static mut KARATSUBA_ENABLE: bool = true;
11
12impl UBigInt {
13
14    #[must_use = "method returns a new number and does not mutate the original value"]
15    pub fn mul_ubi(&self, other: &UBigInt) -> Self {
16
17        #[cfg(test)]
18        let go_kara = unsafe { KARATSUBA_ENABLE };
19        #[cfg(not(test))]
20        let go_kara = true;
21
22        // https://en.wikipedia.org/wiki/Karatsuba_algorithm
23        if self.len() > KARATSUBA_THRES && other.len() > KARATSUBA_THRES && go_kara {
24
25            // self: a, other: b
26            // naive: O(a * b)
27            // karatsuba: O(a + b + (a - m) * (b - m) + m * m + a1 * b1)
28            let m = (self.len() / 2).min(other.len() / 2);
29            let x1 = self.shift_right(m);   // O(a - m)
30            let x0 = self.slice_right(m);   // O(m)
31            let y1 = other.shift_right(m);  // O(b - m)
32            let y0 = other.slice_right(m);  // O(m)
33            let z2 = x1.mul_ubi(&y1);  // O((a - m) * (b - m))
34            let z0 = x0.mul_ubi(&y0);  // O(m * m)
35
36            // a1 = max(m, a - m), b1 = max(m, b - m)
37            let z1 = x1.add_ubi(&x0).mul_ubi(&y1.add_ubi(&y0)).sub_ubi(&z2).sub_ubi(&z0);  // O(a1 * b1 + 3 * (a1 + b1))
38
39            let result = z2.shift_left(2 * m).add_ubi(&z1.shift_left(m)).add_ubi(&z0);
40
41            #[cfg(test)] unsafe {
42
43                if KARATSUBA_TEST {
44                    KARATSUBA_ENABLE = false;
45                    let result2 = self.mul_ubi(&other);
46                    KARATSUBA_ENABLE = true;
47
48                    assert_eq!(result, result2);
49                }
50
51            }
52
53            return result;
54        }
55
56        let mut result = vec![0; self.len() + other.len()];
57
58        for i in 0..self.len() {
59
60            for j in 0..other.len() {
61                let curr = self.0[i] as u64 * other.0[j] as u64;
62                result[i + j] += curr % (1 << 32);
63                result[i + j + 1] += curr >> 32;
64            }
65
66        }
67
68        let mut result = v64_to_v32(result);
69        remove_suffix_0(&mut result);
70
71        let result = UBigInt::from_raw(result);
72
73        #[cfg(test)] assert!(result.is_valid());
74
75        result
76    }
77
78    pub fn mul_ubi_mut(&mut self, other: &UBigInt) {
79        let result = self.mul_ubi(other);
80        *self = result;
81    }
82
83    #[must_use = "method returns a new number and does not mutate the original value"]
84    pub fn mul_u32(&self, other: u32) -> Self {
85        let mut result = self.clone();
86        result.mul_u32_mut(other);
87
88        #[cfg(test)] {
89            let t = self.mul_ubi(&UBigInt::from_u32(other));
90            assert_eq!(t, result);
91            assert!(result.is_valid());
92        }
93
94        result
95    }
96
97    pub fn mul_u32_mut(&mut self, other: u32) {
98        let mut carry = 0;
99
100        for i in 0..self.len() {
101
102            match self.0[i].checked_mul(other) {
103                Some(n) => match n.checked_add(carry as u32) {
104                    Some(n) => {
105                        self.0[i] = n;
106                        carry = 0;
107                    }
108                    _ => {
109                        self.0[i] = ((n as u64 + carry) % (1 << 32)) as u32;
110                        carry = (n as u64 + carry) >> 32;
111                    }
112                }
113                _ => {
114                    let curr = self.0[i] as u64 * other as u64 + carry;
115                    carry = curr >> 32;
116                    self.0[i] = (curr % (1 << 32)) as u32;
117                }
118            }
119
120        }
121
122        if carry > 0 {
123            self.0.push(carry as u32);
124        }
125
126        remove_suffix_0(&mut self.0);
127        #[cfg(test)] assert!(self.is_valid());
128    }
129
130    /// multiplies 2^`exp`
131    // first multiply, then shift
132    #[must_use = "method returns a new number and does not mutate the original value"]
133    pub fn mul_pow2(&self, exp: u32) -> Self {
134        let mut result = self.clone();
135        result.mul_pow2_mut(exp);
136
137        result
138    }
139
140    /// multiplies 2^`exp`
141    // first multiply, then shift
142    pub fn mul_pow2_mut(&mut self, exp: u32) {
143        let small = 1 << (exp % 32);
144        let big = exp / 32;
145
146        self.mul_u32_mut(small);
147        self.shift_left_mut(big as usize);
148    }
149}
150
151#[cfg(test)]
152mod tests {
153    use crate::UBigInt;
154
155    #[test]
156    fn mul_pow2_test() {
157        let two = UBigInt::from_u32(2);
158        let three = UBigInt::from_u32(3);
159
160        for i in 16..64 {
161            assert_eq!(
162                three.mul_pow2(i * 8),
163                three.mul_ubi(&two.pow_u32(i * 8))
164            );
165        }
166
167    }
168
169}
hmath/ubigint/arith/mul.rs

hmath/ubigint/arith/
mul.rs
