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

dashu_int/
mul_ops.rs
