dashu_int/
mul_ops.rs

1//! Multiplication and squaring operators.
2
3use crate::{helper_macros, ibig::IBig, ubig::UBig};
4use core::ops::{Mul, MulAssign};
5
6helper_macros::forward_ubig_binop_to_repr!(impl Mul, mul);
7helper_macros::impl_binop_assign_by_taking!(impl MulAssign<UBig> for UBig, mul_assign, mul);
8
9macro_rules! impl_ibig_mul {
10    ($sign0:ident, $mag0:ident, $sign1:ident, $mag1:ident) => {
11        IBig($mag0.mul($mag1).with_sign($sign0 * $sign1))
12    };
13}
14helper_macros::forward_ibig_binop_to_repr!(impl Mul, mul, Output = IBig, impl_ibig_mul);
15helper_macros::impl_binop_assign_by_taking!(impl MulAssign<IBig> for IBig, mul_assign, mul);
16
17macro_rules! impl_ubig_ibig_mul {
18    ($mag0:ident, $sign1:ident, $mag1:ident) => {
19        IBig($mag0.mul($mag1).with_sign($sign1))
20    };
21}
22helper_macros::forward_ubig_ibig_binop_to_repr!(impl Mul, mul, Output = IBig, impl_ubig_ibig_mul);
23
24macro_rules! impl_ibig_ubig_mul {
25    ($sign0:ident, $mag0:ident, $mag1:ident) => {
26        IBig($mag0.mul($mag1).with_sign($sign0))
27    };
28}
29helper_macros::forward_ibig_ubig_binop_to_repr!(impl Mul, mul, Output = IBig, impl_ibig_ubig_mul);
30helper_macros::impl_binop_assign_by_taking!(impl MulAssign<UBig> for IBig, mul_assign, mul);
31
32// Ops with primitives
33
34macro_rules! impl_div_primitive_with_ubig {
35    ($($t:ty)*) => {$(
36        helper_macros::impl_commutative_binop_with_primitive!(impl Mul<$t> for UBig, mul);
37        helper_macros::impl_binop_assign_with_primitive!(impl MulAssign<$t> for UBig, mul_assign);
38    )*};
39}
40impl_div_primitive_with_ubig!(u8 u16 u32 u64 u128 usize);
41
42macro_rules! impl_div_primitive_with_ibig {
43    ($($t:ty)*) => {$(
44        helper_macros::impl_commutative_binop_with_primitive!(impl Mul<$t> for IBig, mul);
45        helper_macros::impl_binop_assign_with_primitive!(impl MulAssign<$t> for IBig, mul_assign);
46    )*};
47}
48impl_div_primitive_with_ibig!(u8 u16 u32 u64 u128 usize i8 i16 i32 i64 i128 isize);
49
50impl UBig {
51    /// Calculate the square of the number (`x * x`).
52    ///
53    /// # Examples
54    ///
55    /// ```
56    /// # use dashu_int::UBig;
57    /// assert_eq!(UBig::from(3u8).sqr(), UBig::from(9u8));
58    /// ```
59    #[inline]
60    pub fn sqr(&self) -> UBig {
61        UBig(self.repr().sqr())
62    }
63
64    /// Compute the cubic of the number (`self * self * self`).
65    ///
66    /// # Examples
67    ///
68    /// ```
69    /// # use dashu_int::UBig;
70    /// assert_eq!(UBig::from(3u8).cubic(), UBig::from(27u8));
71    /// ```
72    #[inline]
73    pub fn cubic(&self) -> UBig {
74        self * self.sqr()
75    }
76}
77
78impl IBig {
79    /// Compute the square of the number (`self * self`).
80    ///
81    /// # Examples
82    ///
83    /// ```
84    /// # use dashu_int::{UBig, IBig};
85    /// assert_eq!(IBig::from(-3).sqr(), UBig::from(9u8));
86    /// ```
87    #[inline]
88    pub fn sqr(&self) -> UBig {
89        UBig(self.as_sign_repr().1.sqr())
90    }
91
92    /// Compute the cubic of the number (`self * self * self`).
93    ///
94    /// # Examples
95    ///
96    /// ```
97    /// # use dashu_int::IBig;
98    /// assert_eq!(IBig::from(-3).cubic(), IBig::from(-27));
99    /// ```
100    #[inline]
101    pub fn cubic(&self) -> IBig {
102        self * self.sqr()
103    }
104}
105
106pub(crate) mod repr {
107    use super::*;
108    use crate::{
109        arch::word::{DoubleWord, Word},
110        buffer::Buffer,
111        cmp::cmp_in_place,
112        math,
113        memory::MemoryAllocation,
114        mul,
115        primitive::{extend_word, shrink_dword, split_dword},
116        repr::{
117            Repr,
118            TypedRepr::{self, *},
119            TypedReprRef::{self, *},
120        },
121        shift, sqr,
122    };
123
124    impl Mul<TypedRepr> for TypedRepr {
125        type Output = Repr;
126
127        #[inline]
128        fn mul(self, rhs: TypedRepr) -> Repr {
129            match (self, rhs) {
130                (Small(dword0), Small(dword1)) => mul_dword(dword0, dword1),
131                (Small(dword0), Large(buffer1)) => mul_large_dword(buffer1, dword0),
132                (Large(buffer0), Small(dword1)) => mul_large_dword(buffer0, dword1),
133                (Large(buffer0), Large(buffer1)) => mul_large(&buffer0, &buffer1),
134            }
135        }
136    }
137
138    impl<'l> Mul<TypedRepr> for TypedReprRef<'l> {
139        type Output = Repr;
140
141        #[inline]
142        fn mul(self, rhs: TypedRepr) -> Repr {
143            match (self, rhs) {
144                (RefSmall(dword0), Small(dword1)) => mul_dword(dword0, dword1),
145                (RefSmall(dword0), Large(buffer1)) => mul_large_dword(buffer1, dword0),
146                (RefLarge(buffer0), Small(dword1)) => mul_large_dword(buffer0.into(), dword1),
147                (RefLarge(buffer0), Large(buffer1)) => mul_large(buffer0, &buffer1),
148            }
149        }
150    }
151
152    impl<'r> Mul<TypedReprRef<'r>> for TypedRepr {
153        type Output = Repr;
154
155        #[inline]
156        fn mul(self, rhs: TypedReprRef) -> Self::Output {
157            // mul is commutative
158            rhs.mul(self)
159        }
160    }
161
162    impl<'l, 'r> Mul<TypedReprRef<'r>> for TypedReprRef<'l> {
163        type Output = Repr;
164
165        #[inline]
166        fn mul(self, rhs: TypedReprRef) -> Repr {
167            match (self, rhs) {
168                (RefSmall(dword0), RefSmall(dword1)) => mul_dword(dword0, dword1),
169                (RefSmall(dword0), RefLarge(buffer1)) => mul_large_dword(buffer1.into(), dword0),
170                (RefLarge(buffer0), RefSmall(dword1)) => mul_large_dword(buffer0.into(), dword1),
171                (RefLarge(buffer0), RefLarge(buffer1)) => mul_large(buffer0, buffer1),
172            }
173        }
174    }
175
176    /// Multiply two `DoubleWord`s.
177    #[inline]
178    fn mul_dword(a: DoubleWord, b: DoubleWord) -> Repr {
179        if a <= Word::MAX as DoubleWord && b <= Word::MAX as DoubleWord {
180            Repr::from_dword(a * b)
181        } else {
182            mul_dword_spilled(a, b)
183        }
184    }
185
186    fn mul_dword_spilled(lhs: DoubleWord, rhs: DoubleWord) -> Repr {
187        let (lo, hi) = math::mul_add_carry_dword(lhs, rhs, 0);
188        let mut buffer = Buffer::allocate(4);
189        let (n0, n1) = split_dword(lo);
190        buffer.push(n0);
191        buffer.push(n1);
192        let (n2, n3) = split_dword(hi);
193        buffer.push(n2);
194        buffer.push(n3);
195        Repr::from_buffer(buffer)
196    }
197
198    /// Multiply a large number by a `DoubleWord`.
199    pub(crate) fn mul_large_dword(mut buffer: Buffer, rhs: DoubleWord) -> Repr {
200        match rhs {
201            0 => Repr::zero(),
202            1 => Repr::from_buffer(buffer),
203            dw => {
204                if let Some(word) = shrink_dword(dw) {
205                    let carry = if dw.is_power_of_two() {
206                        shift::shl_in_place(&mut buffer, dw.trailing_zeros())
207                    } else {
208                        mul::mul_word_in_place(&mut buffer, word)
209                    };
210                    buffer.push_resizing(carry);
211                    Repr::from_buffer(buffer)
212                } else {
213                    let carry = mul::mul_dword_in_place(&mut buffer, dw);
214                    if carry != 0 {
215                        let (lo, hi) = split_dword(carry);
216                        buffer.ensure_capacity(buffer.len() + 2);
217                        buffer.push(lo);
218                        buffer.push(hi);
219                    }
220                    Repr::from_buffer(buffer)
221                }
222            }
223        }
224    }
225
226    /// Multiply two large numbers.
227    pub(crate) fn mul_large(lhs: &[Word], rhs: &[Word]) -> Repr {
228        debug_assert!(lhs.len() >= 2 && rhs.len() >= 2);
229
230        // shortcut to square if two operands are equal
231        if cmp_in_place(lhs, rhs).is_eq() {
232            return square_large(lhs);
233        }
234
235        let res_len = lhs.len() + rhs.len();
236        let mut buffer = Buffer::allocate(res_len);
237        buffer.push_zeros(res_len);
238
239        let mut allocation =
240            MemoryAllocation::new(mul::memory_requirement_exact(res_len, lhs.len().min(rhs.len())));
241        mul::multiply(&mut buffer, lhs, rhs, &mut allocation.memory());
242        Repr::from_buffer(buffer)
243    }
244
245    impl TypedReprRef<'_> {
246        pub fn sqr(&self) -> Repr {
247            match self {
248                TypedReprRef::RefSmall(dword) => {
249                    if let Some(word) = shrink_dword(*dword) {
250                        Repr::from_dword(extend_word(word) * extend_word(word))
251                    } else {
252                        square_dword_spilled(*dword)
253                    }
254                }
255                TypedReprRef::RefLarge(words) => square_large(words),
256            }
257        }
258    }
259
260    fn square_dword_spilled(dw: DoubleWord) -> Repr {
261        let (lo, hi) = math::mul_add_carry_dword(dw, dw, 0);
262        let mut buffer = Buffer::allocate(4);
263        let (n0, n1) = split_dword(lo);
264        buffer.push(n0);
265        buffer.push(n1);
266        let (n2, n3) = split_dword(hi);
267        buffer.push(n2);
268        buffer.push(n3);
269        Repr::from_buffer(buffer)
270    }
271
272    pub(crate) fn square_large(words: &[Word]) -> Repr {
273        debug_assert!(words.len() >= 2);
274
275        let mut buffer = Buffer::allocate(words.len() * 2);
276        buffer.push_zeros(words.len() * 2);
277
278        let mut allocation = MemoryAllocation::new(sqr::memory_requirement_exact(words.len()));
279        sqr::sqr(&mut buffer, words, &mut allocation.memory());
280        Repr::from_buffer(buffer)
281    }
282}
dashu_int/mul_ops.rs

dashu_int/
mul_ops.rs
