malachite_base/num/arithmetic/
x_mul_y_to_zz.rs

1// Copyright © 2025 Mikhail Hogrefe
2//
3// Uses code adopted from the GNU MP Library.
4//
5//      Copyright © 1991-1994, 1996, 1997, 1999-2005, 2007-2009, 2011-2020 Free Software
6//      Foundation, Inc.
7//
8// This file is part of Malachite.
9//
10// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
11// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
12// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
13
14use crate::num::arithmetic::traits::XMulYToZZ;
15use crate::num::basic::integers::USIZE_IS_U32;
16use crate::num::basic::unsigneds::PrimitiveUnsigned;
17use crate::num::conversion::half::{wide_join_halves, wide_split_in_half, wide_upper_half};
18use crate::num::conversion::traits::{HasHalf, SplitInHalf, WrappingFrom};
19
20fn implicit_x_mul_y_to_zz<T, DT: From<T> + HasHalf<Half = T> + PrimitiveUnsigned + SplitInHalf>(
21    x: T,
22    y: T,
23) -> (T, T) {
24    (DT::from(x) * DT::from(y)).split_in_half()
25}
26
27pub_test! {explicit_x_mul_y_to_zz<T: PrimitiveUnsigned>(x: T, y: T) -> (T, T) {
28    let (x_1, x_0) = wide_split_in_half(x);
29    let (y_1, y_0) = wide_split_in_half(y);
30    let x_0_y_0 = x_0 * y_0;
31    let mut x_0_y_1 = x_0 * y_1;
32    let x_1_y_0 = x_1 * y_0;
33    let mut x_1_y_1 = x_1 * y_1;
34    let (x_0_y_0_1, x_0_y_0_0) = wide_split_in_half(x_0_y_0);
35    x_0_y_1.wrapping_add_assign(x_0_y_0_1);
36    if x_0_y_1.overflowing_add_assign(x_1_y_0) {
37        x_1_y_1.wrapping_add_assign(T::power_of_2(T::WIDTH >> 1));
38    }
39    let z_1 = x_1_y_1.wrapping_add(wide_upper_half(x_0_y_1));
40    let z_0 = wide_join_halves(x_0_y_1, x_0_y_0_0);
41    (z_1, z_0)
42}}
43
44macro_rules! implicit_x_mul_y_to_zz {
45    ($t:ident, $dt:ident) => {
46        impl XMulYToZZ for $t {
47            /// Multiplies two numbers, returning the product as a pair of `Self` values.
48            ///
49            /// The more significant value always comes first.
50            ///
51            /// $$
52            /// f(x, y) = (z_1, z_0),
53            /// $$
54            /// where $W$ is `Self::WIDTH`,
55            ///
56            /// $x, y, z_1, z_0 < 2^W$, and
57            /// $$
58            /// xy = 2^Wz_1 + z_0.
59            /// $$
60            ///
61            /// # Worst-case complexity
62            /// Constant time and additional memory.
63            ///
64            /// # Examples
65            /// See [here](super::x_mul_y_to_zz#x_mul_y_to_zz).
66            ///
67            /// This is equivalent to `umul_ppmm` from `longlong.h`, GMP 6.2.1, where `(w1, w0)` is
68            /// returned.
69            #[inline]
70            fn x_mul_y_to_zz(x: $t, y: $t) -> ($t, $t) {
71                implicit_x_mul_y_to_zz::<$t, $dt>(x, y)
72            }
73        }
74    };
75}
76
77implicit_x_mul_y_to_zz!(u8, u16);
78implicit_x_mul_y_to_zz!(u16, u32);
79implicit_x_mul_y_to_zz!(u32, u64);
80implicit_x_mul_y_to_zz!(u64, u128);
81
82impl XMulYToZZ for usize {
83    /// Multiplies two numbers, returning the product as a pair of [`usize`] values.
84    ///
85    /// The more significant value always comes first.
86    ///
87    /// $$
88    /// f(x, y) = (z_1, z_0),
89    /// $$
90    /// where $W$ is `Self::WIDTH`,
91    ///
92    /// $x, y, z_1, z_0 < 2^W$, and
93    /// $$
94    /// xy = 2^Wz_1 + z_0.
95    /// $$
96    ///
97    /// # Worst-case complexity
98    /// Constant time and additional memory.
99    ///
100    /// # Examples
101    /// See [here](super::x_mul_y_to_zz#x_mul_y_to_zz).
102    ///
103    /// This is equivalent to `umul_ppmm` from `longlong.h`, GMP 6.2.1, where `(w1, w0)` is
104    /// returned.
105    fn x_mul_y_to_zz(x: usize, y: usize) -> (usize, usize) {
106        if USIZE_IS_U32 {
107            let (z_1, z_0) = u32::x_mul_y_to_zz(u32::wrapping_from(x), u32::wrapping_from(y));
108            (usize::wrapping_from(z_1), usize::wrapping_from(z_0))
109        } else {
110            let (z_1, z_0) = u64::x_mul_y_to_zz(u64::wrapping_from(x), u64::wrapping_from(y));
111            (usize::wrapping_from(z_1), usize::wrapping_from(z_0))
112        }
113    }
114}
115
116impl XMulYToZZ for u128 {
117    /// Multiplies two numbers, returning the product as a pair of [`u128`] values.
118    ///
119    /// The more significant value always comes first.
120    ///
121    /// $$
122    /// f(x, y) = (z_1, z_0),
123    /// $$
124    /// where $W$ is `Self::WIDTH`,
125    ///
126    /// $x, y, z_1, z_0 < 2^W$, and
127    /// $$
128    /// xy = 2^Wz_1 + z_0.
129    /// $$
130    ///
131    /// # Worst-case complexity
132    /// Constant time and additional memory.
133    ///
134    /// # Examples
135    /// See [here](super::x_mul_y_to_zz#x_mul_y_to_zz).
136    ///
137    /// This is equivalent to `umul_ppmm` from `longlong.h`, GMP 6.2.1, where `(w1, w0)` is
138    /// returned.
139    #[inline]
140    fn x_mul_y_to_zz(x: u128, y: u128) -> (u128, u128) {
141        explicit_x_mul_y_to_zz(x, y)
142    }
143}
malachite_base/num/arithmetic/x_mul_y_to_zz.rs

malachite_base/num/arithmetic/
x_mul_y_to_zz.rs
