malachite_base/num/arithmetic/
overflowing_add_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    OverflowingAddAssign, OverflowingAddMul, OverflowingAddMulAssign, UnsignedAbs,
11};
12use crate::num::basic::signeds::PrimitiveSigned;
13use crate::num::basic::unsigneds::PrimitiveUnsigned;
14
15fn overflowing_add_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_add(product);
18    (result, overflow_1 | overflow_2)
19}
20
21macro_rules! impl_overflowing_add_mul_unsigned {
22    ($t:ident) => {
23        impl OverflowingAddMul<$t> for $t {
24            type Output = $t;
25
26            /// Adds a number and the product of two other numbers.
27            ///
28            /// Returns a tuple containing the result and a boolean indicating whether an arithmetic
29            /// overflow occured. If an overflow occurred, then the wrapped value is returned.
30            ///
31            /// # Worst-case complexity
32            /// Constant time and additional memory.
33            ///
34            /// # Examples
35            /// See [here](super::overflowing_add_mul#overflowing_add_mul).
36            #[inline]
37            fn overflowing_add_mul(self, y: $t, z: $t) -> ($t, bool) {
38                overflowing_add_mul_unsigned(self, y, z)
39            }
40        }
41
42        impl OverflowingAddMulAssign<$t> for $t {
43            /// Adds a number and the product of two other numbers, in place.
44            ///
45            /// Returns a boolean indicating whether an arithmetic overflow occurred. If an overflow
46            /// occurred, then the wrapped value is assigned.
47            ///
48            /// # Worst-case complexity
49            /// Constant time and additional memory.
50            ///
51            /// # Examples
52            /// See [here](super::overflowing_add_mul#overflowing_add_mul_assign).
53            #[inline]
54            fn overflowing_add_mul_assign(&mut self, y: $t, z: $t) -> bool {
55                let (product, overflow) = y.overflowing_mul(z);
56                self.overflowing_add_assign(product) | overflow
57            }
58        }
59    };
60}
61apply_to_unsigneds!(impl_overflowing_add_mul_unsigned);
62
63fn overflowing_add_mul_signed<
64    U: PrimitiveUnsigned,
65    S: PrimitiveSigned + UnsignedAbs<Output = U>,
66>(
67    x: S,
68    y: S,
69    z: S,
70) -> (S, bool) {
71    if y == S::ZERO || z == S::ZERO {
72        return (x, false);
73    }
74    let x_sign = x >= S::ZERO;
75    if x_sign == ((y >= S::ZERO) == (z >= S::ZERO)) {
76        let (product, overflow_1) = y.overflowing_mul(z);
77        let (result, overflow_2) = x.overflowing_add(product);
78        (result, overflow_1 | overflow_2)
79    } else {
80        let result = x.wrapping_add(y.wrapping_mul(z));
81        let overflow = {
82            let x = x.unsigned_abs();
83            match y.unsigned_abs().checked_mul(z.unsigned_abs()) {
84                Some(product) => {
85                    x < product
86                        && if x_sign {
87                            !x.wrapping_sub(product).get_highest_bit()
88                        } else {
89                            product.wrapping_sub(x).get_highest_bit()
90                        }
91                }
92                None => true,
93            }
94        };
95        (result, overflow)
96    }
97}
98
99macro_rules! impl_overflowing_add_mul_signed {
100    ($t:ident) => {
101        impl OverflowingAddMul<$t> for $t {
102            type Output = $t;
103
104            /// Adds a number and the product of two other numbers.
105            ///
106            /// Returns a tuple containing the result and a boolean indicating whether an arithmetic
107            /// overflow occurred. If an overflow occurred, then the wrapped value is returned.
108            ///
109            /// # Worst-case complexity
110            /// Constant time and additional memory.
111            ///
112            /// # Examples
113            /// See [here](super::overflowing_add_mul#overflowing_add_mul).
114            #[inline]
115            fn overflowing_add_mul(self, y: $t, z: $t) -> ($t, bool) {
116                overflowing_add_mul_signed(self, y, z)
117            }
118        }
119
120        impl OverflowingAddMulAssign<$t> for $t {
121            /// Adds a number and the product of two other numbers, in place.
122            ///
123            /// Returns a boolean indicating whether an arithmetic overflow occurred. If an overflow
124            /// occurred, then the wrapped value is assigned.
125            ///
126            /// # Worst-case complexity
127            /// Constant time and additional memory.
128            ///
129            /// # Examples
130            /// See [here](super::overflowing_add_mul#overflowing_add_mul_assign).
131            #[inline]
132            fn overflowing_add_mul_assign(&mut self, y: $t, z: $t) -> bool {
133                let overflow;
134                (*self, overflow) = self.overflowing_add_mul(y, z);
135                overflow
136            }
137        }
138    };
139}
140apply_to_signeds!(impl_overflowing_add_mul_signed);
malachite_base/num/arithmetic/overflowing_add_mul.rs

malachite_base/num/arithmetic/
overflowing_add_mul.rs
