malachite_nz/integer/arithmetic/mod_op.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 core::ops::{Rem, RemAssign};
11use malachite_base::num::arithmetic::traits::{
12 CeilingMod, CeilingModAssign, Mod, ModAssign, NegMod, NegModAssign,
13};
14
15impl Mod<Self> for Integer {
16 type Output = Self;
17
18 /// Divides an [`Integer`] by another [`Integer`], taking both by value and returning just the
19 /// remainder. The remainder has the same sign as the second [`Integer`].
20 ///
21 /// If the quotient were computed, the quotient and remainder would satisfy $x = qy + r$ and $0
22 /// \leq |r| < |y|$.
23 ///
24 /// $$
25 /// f(x, y) = x - y\left \lfloor \frac{x}{y} \right \rfloor.
26 /// $$
27 ///
28 /// This function is called `mod_op` rather than `mod` because `mod` is a Rust keyword.
29 ///
30 /// # Worst-case complexity
31 /// $T(n) = O(n \log n \log\log n)$
32 ///
33 /// $M(n) = O(n \log n)$
34 ///
35 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
36 ///
37 /// # Panics
38 /// Panics if `other` is zero.
39 ///
40 /// # Examples
41 /// ```
42 /// use malachite_base::num::arithmetic::traits::Mod;
43 /// use malachite_nz::integer::Integer;
44 ///
45 /// // 2 * 10 + 3 = 23
46 /// assert_eq!(Integer::from(23).mod_op(Integer::from(10)), 3);
47 ///
48 /// // -3 * -10 + -7 = 23
49 /// assert_eq!(Integer::from(23).mod_op(Integer::from(-10)), -7);
50 ///
51 /// // -3 * 10 + 7 = -23
52 /// assert_eq!(Integer::from(-23).mod_op(Integer::from(10)), 7);
53 ///
54 /// // 2 * -10 + -3 = -23
55 /// assert_eq!(Integer::from(-23).mod_op(Integer::from(-10)), -3);
56 /// ```
57 #[inline]
58 fn mod_op(mut self, other: Self) -> Self {
59 self.mod_assign(other);
60 self
61 }
62}
63
64impl Mod<&Self> for Integer {
65 type Output = Self;
66
67 /// Divides an [`Integer`] by another [`Integer`], taking the first by value and the second by
68 /// reference and returning just the remainder. The remainder has the same sign as the second
69 /// [`Integer`].
70 ///
71 /// If the quotient were computed, the quotient and remainder would satisfy $x = qy + r$ and $0
72 /// \leq |r| < |y|$.
73 ///
74 /// $$
75 /// f(x, y) = x - y\left \lfloor \frac{x}{y} \right \rfloor.
76 /// $$
77 ///
78 /// This function is called `mod_op` rather than `mod` because `mod` is a Rust keyword.
79 ///
80 /// # Worst-case complexity
81 /// $T(n) = O(n \log n \log\log n)$
82 ///
83 /// $M(n) = O(n \log n)$
84 ///
85 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
86 ///
87 /// # Panics
88 /// Panics if `other` is zero.
89 ///
90 /// # Examples
91 /// ```
92 /// use malachite_base::num::arithmetic::traits::Mod;
93 /// use malachite_nz::integer::Integer;
94 ///
95 /// // 2 * 10 + 3 = 23
96 /// assert_eq!(Integer::from(23).mod_op(&Integer::from(10)), 3);
97 ///
98 /// // -3 * -10 + -7 = 23
99 /// assert_eq!(Integer::from(23).mod_op(&Integer::from(-10)), -7);
100 ///
101 /// // -3 * 10 + 7 = -23
102 /// assert_eq!(Integer::from(-23).mod_op(&Integer::from(10)), 7);
103 ///
104 /// // 2 * -10 + -3 = -23
105 /// assert_eq!(Integer::from(-23).mod_op(&Integer::from(-10)), -3);
106 /// ```
107 #[inline]
108 fn mod_op(mut self, other: &Self) -> Self {
109 self.mod_assign(other);
110 self
111 }
112}
113
114impl Mod<Integer> for &Integer {
115 type Output = Integer;
116
117 /// Divides an [`Integer`] by another [`Integer`], taking the first by reference and the second
118 /// by value and returning just the remainder. The remainder has the same sign as the second
119 /// [`Integer`].
120 ///
121 /// If the quotient were computed, the quotient and remainder would satisfy $x = qy + r$ and $0
122 /// \leq |r| < |y|$.
123 ///
124 /// $$
125 /// f(x, y) = x - y\left \lfloor \frac{x}{y} \right \rfloor.
126 /// $$
127 ///
128 /// This function is called `mod_op` rather than `mod` because `mod` is a Rust keyword.
129 ///
130 /// # Worst-case complexity
131 /// $T(n) = O(n \log n \log\log n)$
132 ///
133 /// $M(n) = O(n \log n)$
134 ///
135 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
136 ///
137 /// # Panics
138 /// Panics if `other` is zero.
139 ///
140 /// # Examples
141 /// ```
142 /// use malachite_base::num::arithmetic::traits::Mod;
143 /// use malachite_nz::integer::Integer;
144 ///
145 /// // 2 * 10 + 3 = 23
146 /// assert_eq!((&Integer::from(23)).mod_op(Integer::from(10)), 3);
147 ///
148 /// // -3 * -10 + -7 = 23
149 /// assert_eq!((&Integer::from(23)).mod_op(Integer::from(-10)), -7);
150 ///
151 /// // -3 * 10 + 7 = -23
152 /// assert_eq!((&Integer::from(-23)).mod_op(Integer::from(10)), 7);
153 ///
154 /// // 2 * -10 + -3 = -23
155 /// assert_eq!((&Integer::from(-23)).mod_op(Integer::from(-10)), -3);
156 /// ```
157 #[inline]
158 fn mod_op(self, other: Integer) -> Integer {
159 Integer::from_sign_and_abs(
160 other.sign,
161 if self.sign == other.sign {
162 &self.abs % other.abs
163 } else {
164 (&self.abs).neg_mod(other.abs)
165 },
166 )
167 }
168}
169
170impl Mod<&Integer> for &Integer {
171 type Output = Integer;
172
173 /// Divides an [`Integer`] by another [`Integer`], taking both by reference and returning just
174 /// the remainder. The remainder has the same sign as the second [`Integer`].
175 ///
176 /// If the quotient were computed, the quotient and remainder would satisfy $x = qy + r$ and $0
177 /// \leq |r| < |y|$.
178 ///
179 /// $$
180 /// f(x, y) = x - y\left \lfloor \frac{x}{y} \right \rfloor.
181 /// $$
182 ///
183 /// This function is called `mod_op` rather than `mod` because `mod` is a Rust keyword.
184 ///
185 /// # Worst-case complexity
186 /// $T(n) = O(n \log n \log\log n)$
187 ///
188 /// $M(n) = O(n \log n)$
189 ///
190 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
191 ///
192 /// # Panics
193 /// Panics if `other` is zero.
194 ///
195 /// # Examples
196 /// ```
197 /// use malachite_base::num::arithmetic::traits::Mod;
198 /// use malachite_nz::integer::Integer;
199 ///
200 /// // 2 * 10 + 3 = 23
201 /// assert_eq!((&Integer::from(23)).mod_op(&Integer::from(10)), 3);
202 ///
203 /// // -3 * -10 + -7 = 23
204 /// assert_eq!((&Integer::from(23)).mod_op(&Integer::from(-10)), -7);
205 ///
206 /// // -3 * 10 + 7 = -23
207 /// assert_eq!((&Integer::from(-23)).mod_op(&Integer::from(10)), 7);
208 ///
209 /// // 2 * -10 + -3 = -23
210 /// assert_eq!((&Integer::from(-23)).mod_op(&Integer::from(-10)), -3);
211 /// ```
212 #[inline]
213 fn mod_op(self, other: &Integer) -> Integer {
214 Integer::from_sign_and_abs(
215 other.sign,
216 if self.sign == other.sign {
217 &self.abs % &other.abs
218 } else {
219 (&self.abs).neg_mod(&other.abs)
220 },
221 )
222 }
223}
224
225impl ModAssign<Self> for Integer {
226 /// Divides an [`Integer`] by another [`Integer`], taking the second [`Integer`] by value and
227 /// replacing the first by the remainder. The remainder has the same sign as the second
228 /// [`Integer`].
229 ///
230 /// If the quotient were computed, he quotient and remainder would satisfy $x = qy + r$ and $0
231 /// \leq |r| < |y|$.
232 ///
233 /// $$
234 /// x \gets x - y\left \lfloor \frac{x}{y} \right \rfloor.
235 /// $$
236 ///
237 /// # Worst-case complexity
238 /// $T(n) = O(n \log n \log\log n)$
239 ///
240 /// $M(n) = O(n \log n)$
241 ///
242 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
243 ///
244 /// # Panics
245 /// Panics if `other` is zero.
246 ///
247 /// # Examples
248 /// ```
249 /// use malachite_base::num::arithmetic::traits::ModAssign;
250 /// use malachite_nz::integer::Integer;
251 ///
252 /// // 2 * 10 + 3 = 23
253 /// let mut x = Integer::from(23);
254 /// x.mod_assign(Integer::from(10));
255 /// assert_eq!(x, 3);
256 ///
257 /// // -3 * -10 + -7 = 23
258 /// let mut x = Integer::from(23);
259 /// x.mod_assign(Integer::from(-10));
260 /// assert_eq!(x, -7);
261 ///
262 /// // -3 * 10 + 7 = -23
263 /// let mut x = Integer::from(-23);
264 /// x.mod_assign(Integer::from(10));
265 /// assert_eq!(x, 7);
266 ///
267 /// // 2 * -10 + -3 = -23
268 /// let mut x = Integer::from(-23);
269 /// x.mod_assign(Integer::from(-10));
270 /// assert_eq!(x, -3);
271 /// ```
272 fn mod_assign(&mut self, other: Self) {
273 if self.sign == other.sign {
274 self.abs %= other.abs;
275 } else {
276 self.abs.neg_mod_assign(other.abs);
277 };
278 self.sign = other.sign || self.abs == 0;
279 }
280}
281
282impl ModAssign<&Self> for Integer {
283 /// Divides an [`Integer`] by another [`Integer`], taking the second [`Integer`] by reference
284 /// and replacing the first by the remainder. The remainder has the same sign as the second
285 /// [`Integer`].
286 ///
287 /// If the quotient were computed, he quotient and remainder would satisfy $x = qy + r$ and $0
288 /// \leq |r| < |y|$.
289 ///
290 /// $$
291 /// x \gets x - y\left \lfloor \frac{x}{y} \right \rfloor.
292 /// $$
293 ///
294 /// # Worst-case complexity
295 /// $T(n) = O(n \log n \log\log n)$
296 ///
297 /// $M(n) = O(n \log n)$
298 ///
299 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
300 ///
301 /// # Panics
302 /// Panics if `other` is zero.
303 ///
304 /// # Examples
305 /// ```
306 /// use malachite_base::num::arithmetic::traits::ModAssign;
307 /// use malachite_nz::integer::Integer;
308 ///
309 /// // 2 * 10 + 3 = 23
310 /// let mut x = Integer::from(23);
311 /// x.mod_assign(&Integer::from(10));
312 /// assert_eq!(x, 3);
313 ///
314 /// // -3 * -10 + -7 = 23
315 /// let mut x = Integer::from(23);
316 /// x.mod_assign(&Integer::from(-10));
317 /// assert_eq!(x, -7);
318 ///
319 /// // -3 * 10 + 7 = -23
320 /// let mut x = Integer::from(-23);
321 /// x.mod_assign(&Integer::from(10));
322 /// assert_eq!(x, 7);
323 ///
324 /// // 2 * -10 + -3 = -23
325 /// let mut x = Integer::from(-23);
326 /// x.mod_assign(&Integer::from(-10));
327 /// assert_eq!(x, -3);
328 /// ```
329 fn mod_assign(&mut self, other: &Self) {
330 if self.sign == other.sign {
331 self.abs %= &other.abs;
332 } else {
333 self.abs.neg_mod_assign(&other.abs);
334 };
335 self.sign = other.sign || self.abs == 0;
336 }
337}
338
339impl Rem<Self> for Integer {
340 type Output = Self;
341
342 /// Divides an [`Integer`] by another [`Integer`], taking both by value and returning just the
343 /// remainder. The remainder has the same sign as the first [`Integer`].
344 ///
345 /// If the quotient were computed, the quotient and remainder would satisfy $x = qy + r$ and $0
346 /// \leq |r| < |y|$.
347 ///
348 /// $$
349 /// f(x, y) = x - y \operatorname{sgn}(xy)
350 /// \left \lfloor \left | \frac{x}{y} \right | \right \rfloor.
351 /// $$
352 ///
353 /// # Worst-case complexity
354 /// $T(n) = O(n \log n \log\log n)$
355 ///
356 /// $M(n) = O(n \log n)$
357 ///
358 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
359 ///
360 /// # Panics
361 /// Panics if `other` is zero.
362 ///
363 /// # Examples
364 /// ```
365 /// use malachite_nz::integer::Integer;
366 ///
367 /// // 2 * 10 + 3 = 23
368 /// assert_eq!(Integer::from(23) % Integer::from(10), 3);
369 ///
370 /// // -3 * -10 + -7 = 23
371 /// assert_eq!(Integer::from(23) % Integer::from(-10), 3);
372 ///
373 /// // -3 * 10 + 7 = -23
374 /// assert_eq!(Integer::from(-23) % Integer::from(10), -3);
375 ///
376 /// // 2 * -10 + -3 = -23
377 /// assert_eq!(Integer::from(-23) % Integer::from(-10), -3);
378 /// ```
379 #[inline]
380 fn rem(mut self, other: Self) -> Self {
381 self %= other;
382 self
383 }
384}
385
386impl Rem<&Self> for Integer {
387 type Output = Self;
388
389 /// Divides an [`Integer`] by another [`Integer`], taking the first by value and the second by
390 /// reference and returning just the remainder. The remainder has the same sign as the first
391 /// [`Integer`].
392 ///
393 /// If the quotient were computed, the quotient and remainder would satisfy $x = qy + r$ and $0
394 /// \leq |r| < |y|$.
395 ///
396 /// $$
397 /// f(x, y) = x - y \operatorname{sgn}(xy)
398 /// \left \lfloor \left | \frac{x}{y} \right | \right \rfloor.
399 /// $$
400 ///
401 /// # Worst-case complexity
402 /// $T(n) = O(n \log n \log\log n)$
403 ///
404 /// $M(n) = O(n \log n)$
405 ///
406 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
407 ///
408 /// # Panics
409 /// Panics if `other` is zero.
410 ///
411 /// # Examples
412 /// ```
413 /// use malachite_nz::integer::Integer;
414 ///
415 /// // 2 * 10 + 3 = 23
416 /// assert_eq!(Integer::from(23) % &Integer::from(10), 3);
417 ///
418 /// // -3 * -10 + -7 = 23
419 /// assert_eq!(Integer::from(23) % &Integer::from(-10), 3);
420 ///
421 /// // -3 * 10 + 7 = -23
422 /// assert_eq!(Integer::from(-23) % &Integer::from(10), -3);
423 ///
424 /// // 2 * -10 + -3 = -23
425 /// assert_eq!(Integer::from(-23) % &Integer::from(-10), -3);
426 /// ```
427 #[inline]
428 fn rem(mut self, other: &Self) -> Self {
429 self %= other;
430 self
431 }
432}
433
434impl Rem<Integer> for &Integer {
435 type Output = Integer;
436
437 /// Divides an [`Integer`] by another [`Integer`], taking the first by reference and the second
438 /// by value and returning just the remainder. The remainder has the same sign as the first
439 /// [`Integer`].
440 ///
441 /// If the quotient were computed, the quotient and remainder would satisfy $x = qy + r$ and $0
442 /// \leq |r| < |y|$.
443 ///
444 /// $$
445 /// f(x, y) = x - y \operatorname{sgn}(xy)
446 /// \left \lfloor \left | \frac{x}{y} \right | \right \rfloor.
447 /// $$
448 ///
449 /// # Worst-case complexity
450 /// $T(n) = O(n \log n \log\log n)$
451 ///
452 /// $M(n) = O(n \log n)$
453 ///
454 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
455 ///
456 /// # Panics
457 /// Panics if `other` is zero.
458 ///
459 /// # Examples
460 /// ```
461 /// use malachite_nz::integer::Integer;
462 ///
463 /// // 2 * 10 + 3 = 23
464 /// assert_eq!(&Integer::from(23) % Integer::from(10), 3);
465 ///
466 /// // -3 * -10 + -7 = 23
467 /// assert_eq!(&Integer::from(23) % Integer::from(-10), 3);
468 ///
469 /// // -3 * 10 + 7 = -23
470 /// assert_eq!(&Integer::from(-23) % Integer::from(10), -3);
471 ///
472 /// // 2 * -10 + -3 = -23
473 /// assert_eq!(&Integer::from(-23) % Integer::from(-10), -3);
474 /// ```
475 #[inline]
476 fn rem(self, other: Integer) -> Integer {
477 Integer::from_sign_and_abs(self.sign, &self.abs % other.abs)
478 }
479}
480
481impl Rem<&Integer> for &Integer {
482 type Output = Integer;
483
484 /// Divides an [`Integer`] by another [`Integer`], taking both by reference and returning just
485 /// the remainder. The remainder has the same sign as the first [`Integer`].
486 ///
487 /// If the quotient were computed, the quotient and remainder would satisfy $x = qy + r$ and $0
488 /// \leq |r| < |y|$.
489 ///
490 /// $$
491 /// f(x, y) = x - y \operatorname{sgn}(xy)
492 /// \left \lfloor \left | \frac{x}{y} \right | \right \rfloor.
493 /// $$
494 ///
495 /// # Worst-case complexity
496 /// $T(n) = O(n \log n \log\log n)$
497 ///
498 /// $M(n) = O(n \log n)$
499 ///
500 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
501 ///
502 /// # Panics
503 /// Panics if `other` is zero.
504 ///
505 /// # Examples
506 /// ```
507 /// use malachite_nz::integer::Integer;
508 ///
509 /// // 2 * 10 + 3 = 23
510 /// assert_eq!(&Integer::from(23) % &Integer::from(10), 3);
511 ///
512 /// // -3 * -10 + -7 = 23
513 /// assert_eq!(&Integer::from(23) % &Integer::from(-10), 3);
514 ///
515 /// // -3 * 10 + 7 = -23
516 /// assert_eq!(&Integer::from(-23) % &Integer::from(10), -3);
517 ///
518 /// // 2 * -10 + -3 = -23
519 /// assert_eq!(&Integer::from(-23) % &Integer::from(-10), -3);
520 /// ```
521 #[inline]
522 fn rem(self, other: &Integer) -> Integer {
523 Integer::from_sign_and_abs(self.sign, &self.abs % &other.abs)
524 }
525}
526
527impl RemAssign<Self> for Integer {
528 /// Divides an [`Integer`] by another [`Integer`], taking the second [`Integer`] by value and
529 /// replacing the first by the remainder. The remainder has the same sign as the first
530 /// [`Integer`].
531 ///
532 /// If the quotient were computed, he quotient and remainder would satisfy $x = qy + r$ and $0
533 /// \leq |r| < |y|$.
534 ///
535 /// $$
536 /// x \gets x - y \operatorname{sgn}(xy)
537 /// \left \lfloor \left | \frac{x}{y} \right | \right \rfloor.
538 /// $$
539 ///
540 /// # Worst-case complexity
541 /// $T(n) = O(n \log n \log\log n)$
542 ///
543 /// $M(n) = O(n \log n)$
544 ///
545 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
546 ///
547 /// # Panics
548 /// Panics if `other` is zero.
549 ///
550 /// # Examples
551 /// ```
552 /// use malachite_nz::integer::Integer;
553 ///
554 /// // 2 * 10 + 3 = 23
555 /// let mut x = Integer::from(23);
556 /// x %= Integer::from(10);
557 /// assert_eq!(x, 3);
558 ///
559 /// // -3 * -10 + -7 = 23
560 /// let mut x = Integer::from(23);
561 /// x %= Integer::from(-10);
562 /// assert_eq!(x, 3);
563 ///
564 /// // -3 * 10 + 7 = -23
565 /// let mut x = Integer::from(-23);
566 /// x %= Integer::from(10);
567 /// assert_eq!(x, -3);
568 ///
569 /// // 2 * -10 + -3 = -23
570 /// let mut x = Integer::from(-23);
571 /// x %= Integer::from(-10);
572 /// assert_eq!(x, -3);
573 /// ```
574 #[inline]
575 fn rem_assign(&mut self, other: Self) {
576 self.abs %= other.abs;
577 self.sign = self.sign || self.abs == 0;
578 }
579}
580
581impl RemAssign<&Self> for Integer {
582 /// Divides an [`Integer`] by another [`Integer`], taking the second [`Integer`] by reference
583 /// and replacing the first by the remainder. The remainder has the same sign as the first
584 /// [`Integer`].
585 ///
586 /// If the quotient were computed, he quotient and remainder would satisfy $x = qy + r$ and $0
587 /// \leq |r| < |y|$.
588 ///
589 /// $$
590 /// x \gets x - y \operatorname{sgn}(xy)
591 /// \left \lfloor \left | \frac{x}{y} \right | \right \rfloor.
592 /// $$
593 ///
594 /// # Worst-case complexity
595 /// $T(n) = O(n \log n \log\log n)$
596 ///
597 /// $M(n) = O(n \log n)$
598 ///
599 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
600 ///
601 /// # Panics
602 /// Panics if `other` is zero.
603 ///
604 /// # Examples
605 /// ```
606 /// use malachite_nz::integer::Integer;
607 ///
608 /// // 2 * 10 + 3 = 23
609 /// let mut x = Integer::from(23);
610 /// x %= &Integer::from(10);
611 /// assert_eq!(x, 3);
612 ///
613 /// // -3 * -10 + -7 = 23
614 /// let mut x = Integer::from(23);
615 /// x %= &Integer::from(-10);
616 /// assert_eq!(x, 3);
617 ///
618 /// // -3 * 10 + 7 = -23
619 /// let mut x = Integer::from(-23);
620 /// x %= &Integer::from(10);
621 /// assert_eq!(x, -3);
622 ///
623 /// // 2 * -10 + -3 = -23
624 /// let mut x = Integer::from(-23);
625 /// x %= &Integer::from(-10);
626 /// assert_eq!(x, -3);
627 /// ```
628 #[inline]
629 fn rem_assign(&mut self, other: &Self) {
630 self.abs %= &other.abs;
631 self.sign = self.sign || self.abs == 0;
632 }
633}
634
635impl CeilingMod<Self> for Integer {
636 type Output = Self;
637
638 /// Divides an [`Integer`] by another [`Integer`], taking both by value and returning just the
639 /// remainder. The remainder has the opposite sign as the second [`Integer`].
640 ///
641 /// If the quotient were computed, the quotient and remainder would satisfy $x = qy + r$ and $0
642 /// \leq |r| < |y|$.
643 ///
644 /// $$
645 /// f(x, y) = x - y\left \lceil \frac{x}{y} \right \rceil.
646 /// $$
647 ///
648 /// # Worst-case complexity
649 /// $T(n) = O(n \log n \log\log n)$
650 ///
651 /// $M(n) = O(n \log n)$
652 ///
653 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
654 ///
655 /// # Panics
656 /// Panics if `other` is zero.
657 ///
658 /// # Examples
659 /// ```
660 /// use malachite_base::num::arithmetic::traits::CeilingMod;
661 /// use malachite_nz::integer::Integer;
662 ///
663 /// // 2 * 10 + 3 = 23
664 /// assert_eq!(Integer::from(23).ceiling_mod(Integer::from(10)), -7);
665 ///
666 /// // -3 * -10 + -7 = 23
667 /// assert_eq!(Integer::from(23).ceiling_mod(Integer::from(-10)), 3);
668 ///
669 /// // -3 * 10 + 7 = -23
670 /// assert_eq!(Integer::from(-23).ceiling_mod(Integer::from(10)), -3);
671 ///
672 /// // 2 * -10 + -3 = -23
673 /// assert_eq!(Integer::from(-23).ceiling_mod(Integer::from(-10)), 7);
674 /// ```
675 #[inline]
676 fn ceiling_mod(mut self, other: Self) -> Self {
677 self.ceiling_mod_assign(other);
678 self
679 }
680}
681
682impl CeilingMod<&Self> for Integer {
683 type Output = Self;
684
685 /// Divides an [`Integer`] by another [`Integer`], taking the first by value and the second by
686 /// reference and returning just the remainder. The remainder has the opposite sign as the
687 /// second [`Integer`].
688 ///
689 /// If the quotient were computed, the quotient and remainder would satisfy $x = qy + r$ and $0
690 /// \leq |r| < |y|$.
691 ///
692 /// $$
693 /// f(x, y) = x - y\left \lceil \frac{x}{y} \right \rceil.
694 /// $$
695 ///
696 /// # Worst-case complexity
697 /// $T(n) = O(n \log n \log\log n)$
698 ///
699 /// $M(n) = O(n \log n)$
700 ///
701 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
702 ///
703 /// # Panics
704 /// Panics if `other` is zero.
705 ///
706 /// # Examples
707 /// ```
708 /// use malachite_base::num::arithmetic::traits::CeilingMod;
709 /// use malachite_nz::integer::Integer;
710 ///
711 /// // 2 * 10 + 3 = 23
712 /// assert_eq!(Integer::from(23).ceiling_mod(&Integer::from(10)), -7);
713 ///
714 /// // -3 * -10 + -7 = 23
715 /// assert_eq!(Integer::from(23).ceiling_mod(&Integer::from(-10)), 3);
716 ///
717 /// // -3 * 10 + 7 = -23
718 /// assert_eq!(Integer::from(-23).ceiling_mod(&Integer::from(10)), -3);
719 ///
720 /// // 2 * -10 + -3 = -23
721 /// assert_eq!(Integer::from(-23).ceiling_mod(&Integer::from(-10)), 7);
722 /// ```
723 #[inline]
724 fn ceiling_mod(mut self, other: &Self) -> Self {
725 self.ceiling_mod_assign(other);
726 self
727 }
728}
729
730impl CeilingMod<Integer> for &Integer {
731 type Output = Integer;
732
733 /// Divides an [`Integer`] by another [`Integer`], taking the first by reference and the second
734 /// by value and returning just the remainder. The remainder has the opposite sign as the second
735 /// [`Integer`].
736 ///
737 /// If the quotient were computed, the quotient and remainder would satisfy $x = qy + r$ and $0
738 /// \leq |r| < |y|$.
739 ///
740 /// $$
741 /// f(x, y) = x - y\left \lceil \frac{x}{y} \right \rceil.
742 /// $$
743 ///
744 /// # Worst-case complexity
745 /// $T(n) = O(n \log n \log\log n)$
746 ///
747 /// $M(n) = O(n \log n)$
748 ///
749 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
750 ///
751 /// # Panics
752 /// Panics if `other` is zero.
753 ///
754 /// # Examples
755 /// ```
756 /// use malachite_base::num::arithmetic::traits::CeilingMod;
757 /// use malachite_nz::integer::Integer;
758 ///
759 /// // 2 * 10 + 3 = 23
760 /// assert_eq!((&Integer::from(23)).ceiling_mod(Integer::from(10)), -7);
761 ///
762 /// // -3 * -10 + -7 = 23
763 /// assert_eq!((&Integer::from(23)).ceiling_mod(Integer::from(-10)), 3);
764 ///
765 /// // -3 * 10 + 7 = -23
766 /// assert_eq!((&Integer::from(-23)).ceiling_mod(Integer::from(10)), -3);
767 ///
768 /// // 2 * -10 + -3 = -23
769 /// assert_eq!((&Integer::from(-23)).ceiling_mod(Integer::from(-10)), 7);
770 /// ```
771 #[inline]
772 fn ceiling_mod(self, other: Integer) -> Integer {
773 Integer::from_sign_and_abs(
774 !other.sign,
775 if self.sign == other.sign {
776 (&self.abs).neg_mod(other.abs)
777 } else {
778 &self.abs % other.abs
779 },
780 )
781 }
782}
783
784impl CeilingMod<&Integer> for &Integer {
785 type Output = Integer;
786
787 /// Divides an [`Integer`] by another [`Integer`], taking both by reference and returning just
788 /// the remainder. The remainder has the opposite sign as the second [`Integer`].
789 ///
790 /// If the quotient were computed, the quotient and remainder would satisfy $x = qy + r$ and $0
791 /// \leq |r| < |y|$.
792 ///
793 /// $$
794 /// f(x, y) = x - y\left \lceil \frac{x}{y} \right \rceil.
795 /// $$
796 ///
797 /// # Worst-case complexity
798 /// $T(n) = O(n \log n \log\log n)$
799 ///
800 /// $M(n) = O(n \log n)$
801 ///
802 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
803 ///
804 /// # Panics
805 /// Panics if `other` is zero.
806 ///
807 /// # Examples
808 /// ```
809 /// use malachite_base::num::arithmetic::traits::CeilingMod;
810 /// use malachite_nz::integer::Integer;
811 ///
812 /// // 2 * 10 + 3 = 23
813 /// assert_eq!((&Integer::from(23)).ceiling_mod(&Integer::from(10)), -7);
814 ///
815 /// // -3 * -10 + -7 = 23
816 /// assert_eq!((&Integer::from(23)).ceiling_mod(&Integer::from(-10)), 3);
817 ///
818 /// // -3 * 10 + 7 = -23
819 /// assert_eq!((&Integer::from(-23)).ceiling_mod(&Integer::from(10)), -3);
820 ///
821 /// // 2 * -10 + -3 = -23
822 /// assert_eq!((&Integer::from(-23)).ceiling_mod(&Integer::from(-10)), 7);
823 /// ```
824 #[inline]
825 fn ceiling_mod(self, other: &Integer) -> Integer {
826 Integer::from_sign_and_abs(
827 !other.sign,
828 if self.sign == other.sign {
829 (&self.abs).neg_mod(&other.abs)
830 } else {
831 &self.abs % &other.abs
832 },
833 )
834 }
835}
836
837impl CeilingModAssign<Self> for Integer {
838 /// Divides an [`Integer`] by another [`Integer`], taking the [`Integer`] on the right-hand side
839 /// by value and replacing the first number by the remainder. The remainder has the opposite
840 /// sign as the second number.
841 ///
842 /// If the quotient were computed, the quotient and remainder would satisfy $x = qy + r$ and $0
843 /// \leq |r| < |y|$.
844 ///
845 /// $$
846 /// x \gets x - y\left \lceil\frac{x}{y} \right \rceil.
847 /// $$
848 ///
849 /// # Worst-case complexity
850 /// $T(n) = O(n \log n \log\log n)$
851 ///
852 /// $M(n) = O(n \log n)$
853 ///
854 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
855 ///
856 /// # Panics
857 /// Panics if `other` is zero.
858 ///
859 /// # Examples
860 /// ```
861 /// use malachite_base::num::arithmetic::traits::CeilingModAssign;
862 /// use malachite_nz::integer::Integer;
863 ///
864 /// // 2 * 10 + 3 = 23
865 /// let mut x = Integer::from(23);
866 /// x.ceiling_mod_assign(Integer::from(10));
867 /// assert_eq!(x, -7);
868 ///
869 /// // -3 * -10 + -7 = 23
870 /// let mut x = Integer::from(23);
871 /// x.ceiling_mod_assign(Integer::from(-10));
872 /// assert_eq!(x, 3);
873 ///
874 /// // -3 * 10 + 7 = -23
875 /// let mut x = Integer::from(-23);
876 /// x.ceiling_mod_assign(Integer::from(10));
877 /// assert_eq!(x, -3);
878 ///
879 /// // 2 * -10 + -3 = -23
880 /// let mut x = Integer::from(-23);
881 /// x.ceiling_mod_assign(Integer::from(-10));
882 /// assert_eq!(x, 7);
883 /// ```
884 fn ceiling_mod_assign(&mut self, other: Self) {
885 if self.sign == other.sign {
886 self.abs.neg_mod_assign(other.abs);
887 } else {
888 self.abs %= other.abs;
889 };
890 self.sign = !other.sign || self.abs == 0;
891 }
892}
893
894impl CeilingModAssign<&Self> for Integer {
895 /// Divides an [`Integer`] by another [`Integer`], taking the [`Integer`] on the right-hand side
896 /// by reference and replacing the first number by the remainder. The remainder has the opposite
897 /// sign as the second number.
898 ///
899 /// If the quotient were computed, the quotient and remainder would satisfy $x = qy + r$ and $0
900 /// \leq |r| < |y|$.
901 ///
902 /// $$
903 /// x \gets x - y\left \lceil\frac{x}{y} \right \rceil.
904 /// $$
905 ///
906 /// # Worst-case complexity
907 /// $T(n) = O(n \log n \log\log n)$
908 ///
909 /// $M(n) = O(n \log n)$
910 ///
911 /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
912 ///
913 /// # Panics
914 /// Panics if `other` is zero.
915 ///
916 /// # Examples
917 /// ```
918 /// use malachite_base::num::arithmetic::traits::CeilingModAssign;
919 /// use malachite_nz::integer::Integer;
920 ///
921 /// // 2 * 10 + 3 = 23
922 /// let mut x = Integer::from(23);
923 /// x.ceiling_mod_assign(&Integer::from(10));
924 /// assert_eq!(x, -7);
925 ///
926 /// // -3 * -10 + -7 = 23
927 /// let mut x = Integer::from(23);
928 /// x.ceiling_mod_assign(&Integer::from(-10));
929 /// assert_eq!(x, 3);
930 ///
931 /// // -3 * 10 + 7 = -23
932 /// let mut x = Integer::from(-23);
933 /// x.ceiling_mod_assign(&Integer::from(10));
934 /// assert_eq!(x, -3);
935 ///
936 /// // 2 * -10 + -3 = -23
937 /// let mut x = Integer::from(-23);
938 /// x.ceiling_mod_assign(&Integer::from(-10));
939 /// assert_eq!(x, 7);
940 /// ```
941 fn ceiling_mod_assign(&mut self, other: &Self) {
942 if self.sign == other.sign {
943 self.abs.neg_mod_assign(&other.abs);
944 } else {
945 self.abs %= &other.abs;
946 };
947 self.sign = !other.sign || self.abs == 0;
948 }
949}