malachite_nz/integer/arithmetic/divisible_by.rs
1// Copyright © 2026 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::integer::Integer;
10use malachite_base::num::arithmetic::traits::DivisibleBy;
11
12impl DivisibleBy<Self> for Integer {
13 /// Returns whether an [`Integer`] is divisible by another [`Integer`]; in other words, whether
14 /// the first is a multiple of the second. Both [`Integer`]s are taken by value.
15 ///
16 /// This means that zero is divisible by any [`Integer`], including zero; but a nonzero
17 /// [`Integer`] is never divisible by zero.
18 ///
19 /// It's more efficient to use this function than to compute the remainder and check whether
20 /// it's zero.
21 ///
22 /// # Worst-case complexity
23 /// $T(n) = O(n \log n \log \log n)$
24 ///
25 /// $M(n) = O(n \log n)$
26 ///
27 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
28 ///
29 /// # Examples
30 /// ```
31 /// use core::str::FromStr;
32 /// use malachite_base::num::arithmetic::traits::DivisibleBy;
33 /// use malachite_base::num::basic::traits::Zero;
34 /// use malachite_nz::integer::Integer;
35 ///
36 /// assert_eq!(Integer::ZERO.divisible_by(Integer::ZERO), true);
37 /// assert_eq!(Integer::from(-100).divisible_by(Integer::from(-3)), false);
38 /// assert_eq!(Integer::from(102).divisible_by(Integer::from(-3)), true);
39 /// assert_eq!(
40 /// Integer::from_str("-1000000000000000000000000")
41 /// .unwrap()
42 /// .divisible_by(Integer::from_str("1000000000000").unwrap()),
43 /// true
44 /// );
45 /// ```
46 #[inline]
47 fn divisible_by(self, other: Self) -> bool {
48 self.abs.divisible_by(other.abs)
49 }
50}
51
52impl DivisibleBy<&Self> for Integer {
53 /// Returns whether an [`Integer`] is divisible by another [`Integer`]; in other words, whether
54 /// the first is a multiple of the second. The first [`Integer`] is taken by value and the
55 /// second by reference.
56 ///
57 /// This means that zero is divisible by any [`Integer`], including zero; but a nonzero
58 /// [`Integer`] is never divisible by zero.
59 ///
60 /// It's more efficient to use this function than to compute the remainder and check whether
61 /// it's zero.
62 ///
63 /// # Worst-case complexity
64 /// $T(n) = O(n \log n \log \log n)$
65 ///
66 /// $M(n) = O(n \log n)$
67 ///
68 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
69 ///
70 /// # Examples
71 /// ```
72 /// use core::str::FromStr;
73 /// use malachite_base::num::arithmetic::traits::DivisibleBy;
74 /// use malachite_base::num::basic::traits::Zero;
75 /// use malachite_nz::integer::Integer;
76 ///
77 /// assert_eq!(Integer::ZERO.divisible_by(&Integer::ZERO), true);
78 /// assert_eq!(Integer::from(-100).divisible_by(&Integer::from(-3)), false);
79 /// assert_eq!(Integer::from(102).divisible_by(&Integer::from(-3)), true);
80 /// assert_eq!(
81 /// Integer::from_str("-1000000000000000000000000")
82 /// .unwrap()
83 /// .divisible_by(&Integer::from_str("1000000000000").unwrap()),
84 /// true
85 /// );
86 /// ```
87 #[inline]
88 fn divisible_by(self, other: &Self) -> bool {
89 self.abs.divisible_by(&other.abs)
90 }
91}
92
93impl DivisibleBy<Integer> for &Integer {
94 /// Returns whether an [`Integer`] is divisible by another [`Integer`]; in other words, whether
95 /// the first is a multiple of the second. The first [`Integer`] is taken by reference and the
96 /// second by value.
97 ///
98 /// This means that zero is divisible by any [`Integer`], including zero; but a nonzero
99 /// [`Integer`] is never divisible by zero.
100 ///
101 /// It's more efficient to use this function than to compute the remainder and check whether
102 /// it's zero.
103 ///
104 /// # Worst-case complexity
105 /// $T(n) = O(n \log n \log \log n)$
106 ///
107 /// $M(n) = O(n \log n)$
108 ///
109 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
110 ///
111 /// # Examples
112 /// ```
113 /// use core::str::FromStr;
114 /// use malachite_base::num::arithmetic::traits::DivisibleBy;
115 /// use malachite_base::num::basic::traits::Zero;
116 /// use malachite_nz::integer::Integer;
117 ///
118 /// assert_eq!((&Integer::ZERO).divisible_by(Integer::ZERO), true);
119 /// assert_eq!(
120 /// (&Integer::from(-100)).divisible_by(Integer::from(-3)),
121 /// false
122 /// );
123 /// assert_eq!((&Integer::from(102)).divisible_by(Integer::from(-3)), true);
124 /// assert_eq!(
125 /// (&Integer::from_str("-1000000000000000000000000").unwrap())
126 /// .divisible_by(Integer::from_str("1000000000000").unwrap()),
127 /// true
128 /// );
129 /// ```
130 #[inline]
131 fn divisible_by(self, other: Integer) -> bool {
132 (&self.abs).divisible_by(other.abs)
133 }
134}
135
136impl DivisibleBy<&Integer> for &Integer {
137 /// Returns whether an [`Integer`] is divisible by another [`Integer`]; in other words, whether
138 /// the first is a multiple of the second. Both [`Integer`]s are taken by reference.
139 ///
140 /// This means that zero is divisible by any [`Integer`], including zero; but a nonzero
141 /// [`Integer`] is never divisible by zero.
142 ///
143 /// It's more efficient to use this function than to compute the remainder and check whether
144 /// it's zero.
145 ///
146 /// # Worst-case complexity
147 /// $T(n) = O(n \log n \log \log n)$
148 ///
149 /// $M(n) = O(n \log n)$
150 ///
151 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
152 ///
153 /// # Examples
154 /// ```
155 /// use core::str::FromStr;
156 /// use malachite_base::num::arithmetic::traits::DivisibleBy;
157 /// use malachite_base::num::basic::traits::Zero;
158 /// use malachite_nz::integer::Integer;
159 ///
160 /// assert_eq!((&Integer::ZERO).divisible_by(&Integer::ZERO), true);
161 /// assert_eq!(
162 /// (&Integer::from(-100)).divisible_by(&Integer::from(-3)),
163 /// false
164 /// );
165 /// assert_eq!((&Integer::from(102)).divisible_by(&Integer::from(-3)), true);
166 /// assert_eq!(
167 /// (&Integer::from_str("-1000000000000000000000000").unwrap())
168 /// .divisible_by(&Integer::from_str("1000000000000").unwrap()),
169 /// true
170 /// );
171 /// ```
172 #[inline]
173 fn divisible_by(self, other: &Integer) -> bool {
174 (&self.abs).divisible_by(&other.abs)
175 }
176}