malachite_base/num/arithmetic/
overflowing_sub_mul.rs

1// Copyright © 2025 Mikhail Hogrefe
2//
3// This file is part of Malachite.
4//
5// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
6// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
7// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
8
9use crate::num::arithmetic::traits::{
10    OverflowingSubAssign, OverflowingSubMul, OverflowingSubMulAssign, UnsignedAbs,
11};
12use crate::num::basic::signeds::PrimitiveSigned;
13use crate::num::basic::unsigneds::PrimitiveUnsigned;
14
15fn overflowing_sub_mul_unsigned<T: PrimitiveUnsigned>(x: T, y: T, z: T) -> (T, bool) {
16    let (product, overflow_1) = y.overflowing_mul(z);
17    let (result, overflow_2) = x.overflowing_sub(product);
18    (result, overflow_1 | overflow_2)
19}
20
21macro_rules! impl_overflowing_sub_mul_unsigned {
22    ($t:ident) => {
23        impl OverflowingSubMul<$t> for $t {
24            type Output = $t;
25
26            /// Subtracts a number by the product of two other numbers.
27            ///
28            /// Returns a tuple containing the result and a boolean indicating whether an arithmetic
29            /// overflow would occur. If an overflow would have occurred, then the wrapped value is
30            /// returned.
31            ///
32            /// # Worst-case complexity
33            /// Constant time and additional memory.
34            ///
35            /// # Examples
36            /// See [here](super::overflowing_sub_mul#overflowing_sub_mul).
37            #[inline]
38            fn overflowing_sub_mul(self, y: $t, z: $t) -> ($t, bool) {
39                overflowing_sub_mul_unsigned(self, y, z)
40            }
41        }
42
43        impl OverflowingSubMulAssign<$t> for $t {
44            /// Subtracts a number by the product of two other numbers, in place.
45            ///
46            /// Returns a boolean indicating whether an arithmetic overflow would occur. If an
47            /// overflow would have occurred, then the wrapped value is assigned.
48            ///
49            /// # Worst-case complexity
50            /// Constant time and additional memory.
51            ///
52            /// # Examples
53            /// See [here](super::overflowing_sub_mul#overflowing_sub_mul_assign).
54            #[inline]
55            fn overflowing_sub_mul_assign(&mut self, y: $t, z: $t) -> bool {
56                let (product, overflow) = y.overflowing_mul(z);
57                self.overflowing_sub_assign(product) | overflow
58            }
59        }
60    };
61}
62apply_to_unsigneds!(impl_overflowing_sub_mul_unsigned);
63
64fn overflowing_sub_mul<U: PrimitiveUnsigned, S: PrimitiveSigned + UnsignedAbs<Output = U>>(
65    x: S,
66    y: S,
67    z: S,
68) -> (S, bool) {
69    if y == S::ZERO || z == S::ZERO {
70        return (x, false);
71    }
72    let x_sign = x >= S::ZERO;
73    if x_sign == ((y >= S::ZERO) != (z >= S::ZERO)) {
74        let (product, overflow_1) = y.overflowing_mul(z);
75        let (result, overflow_2) = x.overflowing_sub(product);
76        (result, overflow_1 | overflow_2)
77    } else {
78        let result = x.wrapping_sub(y.wrapping_mul(z));
79        let overflow = {
80            let x = x.unsigned_abs();
81            match y.unsigned_abs().checked_mul(z.unsigned_abs()) {
82                Some(product) => {
83                    x < product
84                        && if x_sign {
85                            !x.wrapping_sub(product).get_highest_bit()
86                        } else {
87                            product.wrapping_sub(x).get_highest_bit()
88                        }
89                }
90                None => true,
91            }
92        };
93        (result, overflow)
94    }
95}
96
97macro_rules! impl_overflowing_sub_mul_signed {
98    ($t:ident) => {
99        impl OverflowingSubMul<$t> for $t {
100            type Output = $t;
101
102            /// Subtracts a number by the product of two other numbers.
103            ///
104            /// Returns a tuple containing the result and a boolean indicating whether an arithmetic
105            /// overflow occurred. If an overflow occurred, then the wrapped value is returned.
106            ///
107            /// # Worst-case complexity
108            /// Constant time and additional memory.
109            ///
110            /// # Examples
111            /// See [here](super::overflowing_sub_mul#overflowing_sub_mul).
112            #[inline]
113            fn overflowing_sub_mul(self, y: $t, z: $t) -> ($t, bool) {
114                overflowing_sub_mul(self, y, z)
115            }
116        }
117
118        impl OverflowingSubMulAssign<$t> for $t {
119            /// Subtracts a number by the product of two other numbers, in place.
120            ///
121            /// Returns a boolean indicating whether an arithmetic overflow would occur. If an
122            /// overflow would have occurred, then the wrapped value is assigned.
123            ///
124            /// # Worst-case complexity
125            /// Constant time and additional memory.
126            ///
127            /// # Examples
128            /// See [here](super::overflowing_sub_mul#overflowing_sub_mul_assign).
129            #[inline]
130            fn overflowing_sub_mul_assign(&mut self, y: $t, z: $t) -> bool {
131                let overflow;
132                (*self, overflow) = self.overflowing_sub_mul(y, z);
133                overflow
134            }
135        }
136    };
137}
138apply_to_signeds!(impl_overflowing_sub_mul_signed);
malachite_base/num/arithmetic/overflowing_sub_mul.rs

malachite_base/num/arithmetic/
overflowing_sub_mul.rs
