1use super::{Bounded, One, Scan, ScanSource, Zero};
2use std::{
3 convert::TryFrom,
4 fmt::{self, Display},
5 iter::{Product, Sum},
6 ops::{
7 Add, AddAssign, BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Div,
8 DivAssign, Mul, MulAssign, Neg, Not, Rem, RemAssign, Shl, ShlAssign, Shr, ShrAssign, Sub,
9 SubAssign,
10 },
11 str::FromStr,
12};
13
14pub trait IntBase:
19 Copy
20 + Bounded
21 + Zero
22 + One
23 + Eq
24 + Ord
25 + Default
26 + FromStr
27 + Display
28 + Add<Output = Self>
29 + Sub<Output = Self>
30 + Mul<Output = Self>
31 + Div<Output = Self>
32 + Rem<Output = Self>
33 + AddAssign
34 + SubAssign
35 + MulAssign
36 + DivAssign
37 + RemAssign
38 + Sum
39 + Product
40{
41 type Error;
42 fn div_euclid(self, rhs: Self) -> Self;
43 fn rem_euclid(self, rhs: Self) -> Self;
44 fn pow(self, exp: u32) -> Self;
45 fn from_str_radix(src: &str, radix: u32) -> Result<Self, Self::Error>;
46 fn ilog(self, base: Self) -> u32;
47 fn ilog2(self) -> u32;
48 fn ilog10(self) -> u32;
49 fn isqrt(self) -> Self;
50 fn midpoint(self, rhs: Self) -> Self;
51}
52macro_rules! impl_int_base {
53 ($($t:ty)*) => {
54 $(
55 impl IntBase for $t {
56 type Error = std::num::ParseIntError;
57 fn div_euclid(self, rhs: Self) -> Self { self.div_euclid(rhs) }
58 fn rem_euclid(self, rhs: Self) -> Self { self.rem_euclid(rhs) }
59 fn pow(self, exp: u32) -> Self { self.pow(exp) }
60 fn from_str_radix(src: &str, radix: u32) -> Result<Self, Self::Error> { Self::from_str_radix(src, radix) }
61 fn ilog(self, base: Self) -> u32 { self.ilog(base) }
62 fn ilog2(self) -> u32 { self.ilog2() }
63 fn ilog10(self) -> u32 { self.ilog10() }
64 fn isqrt(self) -> Self { self.isqrt() }
65 fn midpoint(self, rhs: Self) -> Self { self.midpoint(rhs) }
66 }
67 )*
68 };
69}
70impl_int_base!(u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize);
71
72pub struct ExtendedGcd<T: Signed> {
74 pub g: T::Unsigned,
76 pub x: T,
77 pub y: T,
78}
79
80pub trait Unsigned: IntBase {
82 type Signed: Signed<Unsigned = Self>;
83 fn signed(self) -> Self::Signed;
84 fn abs_diff(self, other: Self) -> Self;
85 fn div_ceil(self, rhs: Self) -> Self;
86 fn is_power_of_two(self) -> bool;
87 fn next_power_of_two(self) -> Self;
88 fn is_multiple_of(self, rhs: Self) -> bool;
89 fn next_multiple_of(self, rhs: Self) -> Self;
90 fn gcd(self, other: Self) -> Self;
91 fn lcm(self, other: Self) -> Self {
92 if self.is_zero() && other.is_zero() {
93 Self::zero()
94 } else {
95 self / self.gcd(other) * other
96 }
97 }
98 fn mod_inv(self, modulo: Self) -> Self {
99 debug_assert!(!modulo.is_zero(), "modulo must be non-zero");
100 let extgcd = self.signed().extgcd(modulo.signed());
101 debug_assert!(extgcd.g.is_one(), "not coprime");
102 extgcd.x.rem_euclid(modulo.signed()).unsigned()
103 }
104 fn mod_add(self, rhs: Self, modulo: Self) -> Self;
105 fn mod_sub(self, rhs: Self, modulo: Self) -> Self;
106 fn mod_mul(self, rhs: Self, modulo: Self) -> Self;
107 fn mod_neg(self, modulo: Self) -> Self {
108 debug_assert!(!modulo.is_zero(), "modulo must be non-zero");
109 debug_assert!(self < modulo, "self must be less than modulo");
110 if self.is_zero() {
111 Self::zero()
112 } else {
113 modulo - self
114 }
115 }
116}
117
118pub trait Signed: IntBase + Neg<Output = Self> {
120 type Unsigned: Unsigned<Signed = Self>;
121 fn unsigned(self) -> Self::Unsigned;
122 fn abs(self) -> Self;
123 fn abs_diff(self, other: Self) -> Self::Unsigned;
124 fn is_negative(self) -> bool;
125 fn is_positive(self) -> bool;
126 fn signum(self) -> Self;
127 fn extgcd(self, other: Self) -> ExtendedGcd<Self> {
128 let (mut a, mut b) = (self, other);
129 let (mut u, mut v, mut x, mut y) = (Self::one(), Self::zero(), Self::zero(), Self::one());
130 while !a.is_zero() {
131 let k = b / a;
132 x -= k * u;
133 y -= k * v;
134 b -= k * a;
135 std::mem::swap(&mut x, &mut u);
136 std::mem::swap(&mut y, &mut v);
137 std::mem::swap(&mut b, &mut a);
138 }
139 if b.is_negative() {
140 b = -b;
141 x = -x;
142 y = -y;
143 }
144 ExtendedGcd {
145 g: b.unsigned(),
146 x,
147 y,
148 }
149 }
150}
151
152macro_rules! impl_unsigned_signed {
153 ($([$($tt:tt)*])*) => {
154 $(impl_unsigned_signed!($($tt)*);)*
155 };
156 ($unsigned:ident $signed:ident $upperty:ident) => {
157 impl_unsigned_signed!(
158 @inner $unsigned $signed
159 fn mod_mul(self, rhs: Self, modulo: Self) -> Self {
160 debug_assert!(!modulo.is_zero(), "modulo must be non-zero");
161 (self as $upperty * rhs as $upperty % modulo as $upperty) as $unsigned
162 }
163 );
164 };
165 (u128 i128) => {
166 impl_unsigned_signed!(
167 @inner u128 i128
168 fn mod_mul(self, rhs: Self, modulo: Self) -> Self {
169 debug_assert!(!modulo.is_zero(), "modulo must be non-zero");
170 const MASK64: u128 = 0xffff_ffff_ffff_ffff;
171 let (au, ad) = (self >> 64, self & MASK64);
172 let (bu, bd) = (rhs >> 64, rhs & MASK64);
173 let p0 = ad * bd % modulo;
174 let p2 = au * bu % modulo;
175 let mut x = [
176 p0 as u64,
177 (p0 >> 64) as u64,
178 p2 as u64,
179 (p2 >> 64) as u64,
180 ];
181 let p1 = (au * bd % modulo).mod_add(ad * bu % modulo, modulo);
182 let (p1_lo, p1_hi) = ((p1 & MASK64) as u64, (p1 >> 64) as u64);
183 let (s1, c1) = x[1].overflowing_add(p1_lo);
184 x[1] = s1 as u64;
185 let (s2, c2) = x[2].overflowing_add(p1_hi + c1 as u64);
186 x[2] = s2 as u64;
187 let (s3, _) = x[3].overflowing_add(c2 as u64);
188 x[3] = s3 as u64;
189 rem_u256_by_u128(x, modulo)
190 }
191 );
192 };
193 (@inner $unsigned:ident $signed:ident $mod_mul:item) => {
194 impl Unsigned for $unsigned {
195 type Signed = $signed;
196 fn signed(self) -> Self::Signed { self as Self::Signed }
197 fn abs_diff(self, other: Self) -> Self { self.abs_diff(other) }
198 fn div_ceil(self, rhs: Self) -> Self { self.div_ceil(rhs) }
199 fn is_power_of_two(self) -> bool { self.is_power_of_two() }
200 fn next_power_of_two(self) -> Self { self.next_power_of_two() }
201 fn is_multiple_of(self, rhs: Self) -> bool { self.is_multiple_of(rhs) }
202 fn next_multiple_of(self, rhs: Self) -> Self { self.next_multiple_of(rhs) }
203 fn gcd(self, other: Self) -> Self {
204 let (mut a, mut b) = (self, other);
205 if a.is_zero() || b.is_zero() {
206 return a | b;
207 }
208 let u = a.trailing_zeros();
209 let v = b.trailing_zeros();
210 a >>= u;
211 b >>= v;
212 let k = u.min(v);
213 while a != b {
214 if a < b {
215 std::mem::swap(&mut a, &mut b);
216 }
217 a -= b;
218 a >>= a.trailing_zeros();
219 }
220 a << k
221 }
222 fn mod_add(self, rhs: Self, modulo: Self) -> Self {
223 debug_assert!(!modulo.is_zero(), "modulo must be non-zero");
224 debug_assert!(self < modulo, "self must be less than modulo");
225 debug_assert!(rhs < modulo, "rhs must be less than modulo");
226 let s = self.wrapping_add(rhs);
227 if (s < self) || (s >= modulo) { s.wrapping_sub(modulo) } else { s }
228 }
229 fn mod_sub(self, rhs: Self, modulo: Self) -> Self {
230 debug_assert!(!modulo.is_zero(), "modulo must be non-zero");
231 debug_assert!(self < modulo, "self must be less than modulo");
232 debug_assert!(rhs < modulo, "rhs must be less than modulo");
233 let d = self.wrapping_sub(rhs);
234 if self < rhs { d.wrapping_add(modulo) } else { d }
235 }
236 $mod_mul
237 }
238 impl Signed for $signed {
239 type Unsigned = $unsigned;
240 fn unsigned(self) -> Self::Unsigned { self as Self::Unsigned }
241 fn abs_diff(self, other: Self) -> Self::Unsigned { self.abs_diff(other) }
242 fn abs(self) -> Self { self.abs() }
243 fn is_negative(self) -> bool { self.is_negative() }
244 fn is_positive(self) -> bool { self.is_positive() }
245 fn signum(self) -> Self { self.signum() }
246 }
247 };
248}
249impl_unsigned_signed!([u8 i8 u16] [u16 i16 u32] [u32 i32 u64] [u64 i64 u128] [u128 i128] [usize isize u128]);
250
251fn rem_u256_by_u128(u: [u64; 4], v: u128) -> u128 {
252 #[inline(always)]
254 fn sub_with_borrow_u64(lhs: u64, rhs: u64, borrow: bool) -> (u64, bool) {
255 let (res, overflow) = lhs.overflowing_sub(rhs);
256 if borrow {
257 let (res, overflow_borrow) = res.overflowing_sub(1);
258 (res, overflow | overflow_borrow)
259 } else {
260 (res, overflow)
261 }
262 }
263
264 debug_assert!(v != 0);
265 let v_hi = (v >> 64) as u64;
266 if v_hi == 0 {
267 let d = v as u64 as u128;
268 let mut rem: u128 = 0;
269 for &w in u.iter().rev() {
270 rem = (rem << 64 | w as u128) % d;
271 }
272 return rem;
273 }
274
275 let v_lo = v as u64;
276 let v_shift = v_hi.leading_zeros();
277 let (vn1, vn0) = if v_shift == 0 {
278 (v_hi, v_lo)
279 } else {
280 let hi = v_hi << v_shift | v_lo >> (64 - v_shift);
281 let lo = v_lo << v_shift;
282 (hi, lo)
283 };
284
285 let mut un = [0u64; 5];
286 if v_shift == 0 {
287 un[0] = u[0];
288 un[1] = u[1];
289 un[2] = u[2];
290 un[3] = u[3];
291 } else {
292 un[0] = u[0] << v_shift;
293 un[1] = u[1] << v_shift | u[0] >> (64 - v_shift);
294 un[2] = u[2] << v_shift | u[1] >> (64 - v_shift);
295 un[3] = u[3] << v_shift | u[2] >> (64 - v_shift);
296 un[4] = u[3] >> (64 - v_shift);
297 }
298
299 for j in (0..=2).rev() {
300 let num = (un[j + 2] as u128) << 64 | un[j + 1] as u128;
301 let (mut qhat, mut rhat) = {
302 let d = vn1 as u128;
303 let q = (num / d).min(u64::MAX as u128);
304 (q as u64, (num - q * d).min(u64::MAX as u128) as u64)
305 };
306 while qhat as u128 * vn0 as u128 > (rhat as u128) << 64 | un[j] as u128 {
307 qhat -= 1;
308 let t = rhat as u128 + vn1 as u128;
309 if t >= 1u128 << 64 {
310 break;
311 }
312 rhat = t as u64;
313 }
314
315 let p0 = qhat as u128 * vn0 as u128;
316 let p1 = qhat as u128 * vn1 as u128;
317 let (p0_hi, p0_lo) = ((p0 >> 64) as u64, p0 as u64);
318 let (p1_hi, p1_lo) = ((p1 >> 64) as u64, p1 as u64);
319
320 let (r0, borrow) = sub_with_borrow_u64(un[j], p0_lo, false);
321 un[j] = r0;
322
323 let (r1, borrow1) = sub_with_borrow_u64(un[j + 1], p0_hi, borrow);
324 let (r1, borrow2) = sub_with_borrow_u64(r1, p1_lo, false);
325 let borrow = borrow1 || borrow2;
326 un[j + 1] = r1;
327
328 let (r2, borrow) = sub_with_borrow_u64(un[j + 2], p1_hi, borrow);
329 un[j + 2] = r2;
330 assert!(!borrow);
331 }
332
333 ((un[1] as u128) << 64 | un[0] as u128) >> v_hi.leading_zeros()
334}
335
336pub trait BinaryRepr<Size = u32>:
338 Sized
339 + Not<Output = Self>
340 + BitAnd<Output = Self>
341 + BitOr<Output = Self>
342 + BitXor<Output = Self>
343 + Shl<Size, Output = Self>
344 + Shr<Size, Output = Self>
345 + BitAndAssign
346 + BitOrAssign
347 + BitXorAssign
348 + ShlAssign<Size>
349 + ShrAssign<Size>
350{
351 fn count_ones(self) -> Size;
352 fn count_zeros(self) -> Size;
353 fn leading_ones(self) -> Size;
354 fn leading_zeros(self) -> Size;
355 fn reverse_bits(self) -> Self;
356 fn rotate_left(self, n: Size) -> Self;
357 fn rotate_right(self, n: Size) -> Self;
358 fn swap_bytes(self) -> Self;
359 fn trailing_ones(self) -> Size;
360 fn trailing_zeros(self) -> Size;
361}
362
363macro_rules! impl_binary_repr {
364 ($($t:ty)*) => {
365 $(
366 impl BinaryRepr for $t {
367 fn count_ones(self) -> u32 { self.count_ones() }
368 fn count_zeros(self) -> u32 { self.count_zeros() }
369 fn leading_ones(self) -> u32 { self.leading_ones() }
370 fn leading_zeros(self) -> u32 { self.leading_zeros() }
371 fn reverse_bits(self) -> Self { self.reverse_bits() }
372 fn rotate_left(self, n: u32) -> Self { self.rotate_left(n) }
373 fn rotate_right(self, n: u32) -> Self { self.rotate_right(n) }
374 fn swap_bytes(self) -> Self { self.swap_bytes() }
375 fn trailing_ones(self) -> u32 { self.trailing_ones() }
376 fn trailing_zeros(self) -> u32 { self.trailing_zeros() }
377 }
378 )*
379 };
380}
381impl_binary_repr!(u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize);
382
383macro_rules! impl_binop {
384 (impl<$T:ident> $Trait:ident $impl:ident for $t:ty) => {
385 impl<$T> $Trait for $t
386 where
387 $T: $Trait<Output = $T>,
388 {
389 type Output = Self;
390 fn $impl(self, rhs: Self) -> Self::Output {
391 Self($Trait::$impl(self.0, rhs.0))
392 }
393 }
394 impl<$T> $Trait<$T> for $t
395 where
396 $T: $Trait<Output = $T>,
397 {
398 type Output = Self;
399 fn $impl(self, rhs: $T) -> Self::Output {
400 Self($Trait::$impl(self.0, rhs))
401 }
402 }
403 };
404}
405macro_rules! impl_opassign {
406 (impl<$T:ident> $Trait:ident $impl:ident for $t:ty) => {
407 impl<$T> $Trait for $t
408 where
409 $T: $Trait,
410 {
411 fn $impl(&mut self, rhs: Self) {
412 $Trait::$impl(&mut self.0, rhs.0)
413 }
414 }
415 impl<$T> $Trait<$T> for $t
416 where
417 $T: $Trait,
418 {
419 fn $impl(&mut self, rhs: $T) {
420 $Trait::$impl(&mut self.0, rhs)
421 }
422 }
423 };
424 (impl<$T:ident> $Trait:ident $impl:ident for $t:ty => $F:ident $f:ident) => {
425 impl<$T> $Trait for $t
426 where
427 $t: $F<Output = $t> + Copy,
428 {
429 fn $impl(&mut self, rhs: Self) {
430 *self = $F::$f(*self, rhs);
431 }
432 }
433 impl<$T> $Trait<$T> for $t
434 where
435 $t: $F<$T, Output = $t> + Copy,
436 {
437 fn $impl(&mut self, rhs: $T) {
438 *self = $F::$f(*self, rhs);
439 }
440 }
441 };
442}
443
444#[derive(Default, PartialEq, Eq, PartialOrd, Ord, Hash, Clone, Copy)]
445#[repr(transparent)]
446pub struct Saturating<T>(pub T);
448pub trait Saturatingable: Sized
449where
450 Saturating<Self>: Copy
451 + Bounded
452 + Zero
453 + One
454 + Eq
455 + Ord
456 + Default
457 + FromStr
458 + Display
459 + Add<Output = Saturating<Self>>
460 + Sub<Output = Saturating<Self>>
461 + Mul<Output = Saturating<Self>>
462 + Div<Output = Saturating<Self>>
463 + Rem<Output = Saturating<Self>>
464 + BitAnd<Output = Saturating<Self>>
465 + BitOr<Output = Saturating<Self>>
466 + BitXor<Output = Saturating<Self>>
467 + Shl<u32, Output = Saturating<Self>>
468 + Shr<u32, Output = Saturating<Self>>
469 + AddAssign
470 + SubAssign
471 + MulAssign
472 + DivAssign
473 + RemAssign
474 + BitAndAssign
475 + BitOrAssign
476 + BitXorAssign
477 + ShlAssign<u32>
478 + ShrAssign<u32>
479 + Not<Output = Saturating<Self>>
480 + Add<Self, Output = Saturating<Self>>
481 + Sub<Self, Output = Saturating<Self>>
482 + Mul<Self, Output = Saturating<Self>>
483 + Div<Self, Output = Saturating<Self>>
484 + Rem<Self, Output = Saturating<Self>>
485 + BitAnd<Self, Output = Saturating<Self>>
486 + BitOr<Self, Output = Saturating<Self>>
487 + BitXor<Self, Output = Saturating<Self>>
488 + AddAssign<Self>
489 + SubAssign<Self>
490 + MulAssign<Self>
491 + DivAssign<Self>
492 + RemAssign<Self>
493 + BitAndAssign<Self>
494 + BitOrAssign<Self>
495 + BitXorAssign<Self>,
496{
497 fn to_saturating(self) -> Saturating<Self> {
498 Saturating(self)
499 }
500 fn from_saturating(s: Saturating<Self>) -> Self {
501 s.0
502 }
503}
504
505impl<T> fmt::Debug for Saturating<T>
506where
507 T: fmt::Debug,
508{
509 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
510 T::fmt(&self.0, f)
511 }
512}
513impl<T> Bounded for Saturating<T>
514where
515 T: Bounded,
516{
517 fn maximum() -> Self {
518 Self(T::maximum())
519 }
520 fn minimum() -> Self {
521 Self(T::minimum())
522 }
523}
524impl<T> Zero for Saturating<T>
525where
526 T: Zero,
527{
528 fn zero() -> Self {
529 Self(T::zero())
530 }
531}
532impl<T> One for Saturating<T>
533where
534 T: One,
535{
536 fn one() -> Self {
537 Self(T::one())
538 }
539}
540impl<T> FromStr for Saturating<T>
541where
542 T: FromStr,
543{
544 type Err = T::Err;
545 fn from_str(s: &str) -> Result<Self, Self::Err> {
546 T::from_str(s).map(Self)
547 }
548}
549impl<T> Display for Saturating<T>
550where
551 T: Display,
552{
553 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
554 T::fmt(&self.0, f)
555 }
556}
557
558impl<T> Scan for Saturating<T>
559where
560 T: Scan<Output = T>,
561{
562 type Output = Self;
563 fn scan<I: ScanSource>(iter: &mut I) -> Option<Self::Output> {
564 T::scan(iter).map(Self)
565 }
566}
567impl_binop!(impl<T> Div div for Saturating<T>);
568impl_binop!(impl<T> Rem rem for Saturating<T>);
569impl_binop!(impl<T> BitAnd bitand for Saturating<T>);
570impl_binop!(impl<T> BitOr bitor for Saturating<T>);
571impl_binop!(impl<T> BitXor bitxor for Saturating<T>);
572impl_opassign!(impl<T> AddAssign add_assign for Saturating<T> => Add add);
573impl_opassign!(impl<T> SubAssign sub_assign for Saturating<T> => Sub sub);
574impl_opassign!(impl<T> MulAssign mul_assign for Saturating<T> => Mul mul);
575impl_opassign!(impl<T> DivAssign div_assign for Saturating<T>);
576impl_opassign!(impl<T> RemAssign rem_assign for Saturating<T>);
577impl_opassign!(impl<T> BitAndAssign bitand_assign for Saturating<T>);
578impl_opassign!(impl<T> BitOrAssign bitor_assign for Saturating<T>);
579impl_opassign!(impl<T> BitXorAssign bitxor_assign for Saturating<T>);
580impl<T> Not for Saturating<T>
581where
582 T: Not<Output = T>,
583{
584 type Output = Self;
585 fn not(self) -> Self::Output {
586 Self(Not::not(self.0))
587 }
588}
589
590macro_rules! impl_int_base_for_saturating {
591 ($($t:ty)*) => {
592 $(
593 impl Saturatingable for $t {}
594 impl Add for Saturating<$t> {
595 type Output = Self;
596 fn add(self, rhs: Self) -> Self::Output {
597 Self(self.0.saturating_add(rhs.0))
598 }
599 }
600 impl Add<$t> for Saturating<$t> {
601 type Output = Self;
602 fn add(self, rhs: $t) -> Self::Output {
603 Self(self.0.saturating_add(rhs))
604 }
605 }
606 impl Sub for Saturating<$t> {
607 type Output = Self;
608 fn sub(self, rhs: Self) -> Self::Output {
609 Self(self.0.saturating_sub(rhs.0))
610 }
611 }
612 impl Sub<$t> for Saturating<$t> {
613 type Output = Self;
614 fn sub(self, rhs: $t) -> Self::Output {
615 Self(self.0.saturating_sub(rhs))
616 }
617 }
618 impl Mul for Saturating<$t> {
619 type Output = Self;
620 fn mul(self, rhs: Self) -> Self::Output {
621 Self(self.0.saturating_mul(rhs.0))
622 }
623 }
624 impl Mul<$t> for Saturating<$t> {
625 type Output = Self;
626 fn mul(self, rhs: $t) -> Self::Output {
627 Self(self.0.saturating_mul(rhs))
628 }
629 }
630 impl Sum for Saturating<$t> {
631 fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
632 iter.fold(Self::zero(), |acc, x| acc + x)
633 }
634 }
635 impl Product for Saturating<$t> {
636 fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
637 iter.fold(Self::one(), |acc, x| acc * x)
638 }
639 }
640 impl IntBase for Saturating<$t> {
641 type Error = <$t as IntBase>::Error;
642 fn div_euclid(self, rhs: Self) -> Self { Self(self.0.div_euclid(rhs.0)) }
643 fn rem_euclid(self, rhs: Self) -> Self { Self(self.0.rem_euclid(rhs.0)) }
644 fn pow(self, exp: u32) -> Self { Self(self.0.saturating_pow(exp)) }
645 fn from_str_radix(src: &str, radix: u32) -> Result<Self, Self::Error> { <$t as IntBase>::from_str_radix(src, radix).map(Self) }
646 fn ilog(self, base: Self) -> u32 { self.0.ilog(base.0) }
647 fn ilog2(self) -> u32 { self.0.ilog2() }
648 fn ilog10(self) -> u32 { self.0.ilog10() }
649 fn isqrt(self) -> Self { Self(self.0.isqrt()) }
650 fn midpoint(self, rhs: Self) -> Self { Self(self.0.midpoint(rhs.0)) }
651 }
652 impl From<$t> for Saturating<$t> {
653 fn from(t: $t) -> Self {
654 Self(t)
655 }
656 }
657 )*
658 };
659}
660impl_int_base_for_saturating!(u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize);
661
662macro_rules! impl_unsigned_signed_for_saturating {
663 ($($unsigned:ident $signed:ident)*) => {
664 $(
665 impl Unsigned for Saturating<$unsigned> {
666 type Signed = Saturating<$signed>;
667 fn signed(self) -> Self::Signed { Saturating(TryFrom::try_from(self.0).ok().unwrap_or_else($signed::maximum)) }
668 fn abs_diff(self, other: Self) -> Self { Self(self.0.abs_diff(other.0)) }
669 fn div_ceil(self, rhs: Self) -> Self { Self(self.0.div_ceil(rhs.0)) }
670 fn is_power_of_two(self) -> bool { self.0.is_power_of_two() }
671 fn next_power_of_two(self) -> Self { Self(self.0.next_power_of_two()) }
672 fn is_multiple_of(self, rhs: Self) -> bool { self.0.is_multiple_of(rhs.0) }
673 fn next_multiple_of(self, rhs: Self) -> Self { Self(self.0.next_multiple_of(rhs.0)) }
674 fn gcd(self, other: Self) -> Self { Self(self.0.gcd(other.0)) }
675 fn mod_add(self, rhs: Self, modulo: Self) -> Self { Self(self.0.mod_add(rhs.0, modulo.0)) }
676 fn mod_sub(self, rhs: Self, modulo: Self) -> Self { Self(self.0.mod_sub(rhs.0, modulo.0)) }
677 fn mod_mul(self, rhs: Self, modulo: Self) -> Self { Self(self.0.mod_mul(rhs.0, modulo.0)) }
678 }
679 impl Signed for Saturating<$signed> {
680 type Unsigned = Saturating<$unsigned>;
681 fn unsigned(self) -> Self::Unsigned { Saturating(TryFrom::try_from(self.0).ok().unwrap_or_else($unsigned::minimum)) }
682 fn abs(self) -> Self { Self(self.0.saturating_abs()) }
683 fn abs_diff(self, other: Self) -> Self::Unsigned { Saturating(self.0.abs_diff(other.0)) }
684 fn is_negative(self) -> bool { self.0.is_negative() }
685 fn is_positive(self) -> bool { self.0.is_positive() }
686 fn signum(self) -> Self { Self(self.0.signum()) }
687 }
688 impl Neg for Saturating<$signed> {
689 type Output = Self;
690 fn neg(self) -> Self::Output {
691 Self(self.0.saturating_neg())
692 }
693 }
694 )*
695 };
696}
697impl_unsigned_signed_for_saturating!(u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize);
698
699macro_rules! impl_binary_repr_for_saturating {
700 ($($t:ty)*) => {
701 $(
702 impl Shl<u32> for Saturating<$t> {
703 type Output = Self;
704 fn shl(self, rhs: u32) -> Self::Output {
705 Self(self.0.checked_shl(rhs).unwrap_or(0))
706 }
707 }
708 impl Shr<u32> for Saturating<$t> {
709 type Output = Self;
710 fn shr(self, rhs: u32) -> Self::Output {
711 Self(self.0.checked_shr(rhs).unwrap_or(0))
712 }
713 }
714 impl ShlAssign<u32> for Saturating<$t> {
715 fn shl_assign(&mut self, rhs: u32) {
716 *self = Shl::shl(*self, rhs);
717 }
718 }
719 impl ShrAssign<u32> for Saturating<$t> {
720 fn shr_assign(&mut self, rhs: u32) {
721 *self = Shr::shr(*self, rhs);
722 }
723 }
724 impl BinaryRepr for Saturating<$t> {
725 fn count_ones(self) -> u32 { self.0.count_ones() }
726 fn count_zeros(self) -> u32 { self.0.count_zeros() }
727 fn leading_ones(self) -> u32 { self.0.leading_ones() }
728 fn leading_zeros(self) -> u32 { self.0.leading_zeros() }
729 fn reverse_bits(self) -> Self { Self(self.0.reverse_bits()) }
730 fn rotate_left(self, n: u32) -> Self { Self(self.0.rotate_left(n)) }
731 fn rotate_right(self, n: u32) -> Self { Self(self.0.rotate_right(n)) }
732 fn swap_bytes(self) -> Self { Self(self.0.swap_bytes()) }
733 fn trailing_ones(self) -> u32 { self.0.trailing_ones() }
734 fn trailing_zeros(self) -> u32 { self.0.trailing_zeros() }
735 }
736 )*
737 };
738}
739impl_binary_repr_for_saturating!(u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize);
740
741#[derive(Default, PartialEq, Eq, PartialOrd, Ord, Hash, Clone, Copy)]
742#[repr(transparent)]
743pub struct Wrapping<T>(pub T);
745pub trait Wrappingable: Sized
746where
747 Wrapping<Self>: Copy
748 + Bounded
749 + Zero
750 + One
751 + Eq
752 + Ord
753 + Default
754 + FromStr
755 + Display
756 + Add<Output = Wrapping<Self>>
757 + Sub<Output = Wrapping<Self>>
758 + Mul<Output = Wrapping<Self>>
759 + Div<Output = Wrapping<Self>>
760 + Rem<Output = Wrapping<Self>>
761 + BitAnd<Output = Wrapping<Self>>
762 + BitOr<Output = Wrapping<Self>>
763 + BitXor<Output = Wrapping<Self>>
764 + Shl<u32, Output = Wrapping<Self>>
765 + Shr<u32, Output = Wrapping<Self>>
766 + AddAssign
767 + SubAssign
768 + MulAssign
769 + DivAssign
770 + RemAssign
771 + BitAndAssign
772 + BitOrAssign
773 + BitXorAssign
774 + ShlAssign<u32>
775 + ShrAssign<u32>
776 + Not<Output = Wrapping<Self>>
777 + Add<Self, Output = Wrapping<Self>>
778 + Sub<Self, Output = Wrapping<Self>>
779 + Mul<Self, Output = Wrapping<Self>>
780 + Div<Self, Output = Wrapping<Self>>
781 + Rem<Self, Output = Wrapping<Self>>
782 + BitAnd<Self, Output = Wrapping<Self>>
783 + BitOr<Self, Output = Wrapping<Self>>
784 + BitXor<Self, Output = Wrapping<Self>>
785 + AddAssign<Self>
786 + SubAssign<Self>
787 + MulAssign<Self>
788 + DivAssign<Self>
789 + RemAssign<Self>
790 + BitAndAssign<Self>
791 + BitOrAssign<Self>
792 + BitXorAssign<Self>,
793{
794 fn to_wrapping(self) -> Wrapping<Self> {
795 Wrapping(self)
796 }
797 fn from_wrapping(w: Wrapping<Self>) -> Self {
798 w.0
799 }
800}
801
802impl<T> fmt::Debug for Wrapping<T>
803where
804 T: fmt::Debug,
805{
806 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
807 T::fmt(&self.0, f)
808 }
809}
810impl<T> Bounded for Wrapping<T>
811where
812 T: Bounded,
813{
814 fn maximum() -> Self {
815 Self(T::maximum())
816 }
817 fn minimum() -> Self {
818 Self(T::minimum())
819 }
820}
821impl<T> Zero for Wrapping<T>
822where
823 T: Zero,
824{
825 fn zero() -> Self {
826 Self(T::zero())
827 }
828}
829impl<T> One for Wrapping<T>
830where
831 T: One,
832{
833 fn one() -> Self {
834 Self(T::one())
835 }
836}
837impl<T> FromStr for Wrapping<T>
838where
839 T: FromStr,
840{
841 type Err = T::Err;
842 fn from_str(s: &str) -> Result<Self, Self::Err> {
843 T::from_str(s).map(Self)
844 }
845}
846impl<T> Display for Wrapping<T>
847where
848 T: Display,
849{
850 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
851 T::fmt(&self.0, f)
852 }
853}
854impl<T> Scan for Wrapping<T>
855where
856 T: Scan<Output = T>,
857{
858 type Output = Self;
859 fn scan<I: ScanSource>(iter: &mut I) -> Option<Self::Output> {
860 T::scan(iter).map(Self)
861 }
862}
863impl_binop!(impl<T> BitAnd bitand for Wrapping<T>);
864impl_binop!(impl<T> BitOr bitor for Wrapping<T>);
865impl_binop!(impl<T> BitXor bitxor for Wrapping<T>);
866impl_opassign!(impl<T> AddAssign add_assign for Wrapping<T> => Add add);
867impl_opassign!(impl<T> SubAssign sub_assign for Wrapping<T> => Sub sub);
868impl_opassign!(impl<T> MulAssign mul_assign for Wrapping<T> => Mul mul);
869impl_opassign!(impl<T> DivAssign div_assign for Wrapping<T> => Div div);
870impl_opassign!(impl<T> RemAssign rem_assign for Wrapping<T> => Rem rem);
871impl_opassign!(impl<T> BitAndAssign bitand_assign for Wrapping<T>);
872impl_opassign!(impl<T> BitOrAssign bitor_assign for Wrapping<T>);
873impl_opassign!(impl<T> BitXorAssign bitxor_assign for Wrapping<T>);
874impl<T> Not for Wrapping<T>
875where
876 T: Not<Output = T>,
877{
878 type Output = Self;
879 fn not(self) -> Self::Output {
880 Self(Not::not(self.0))
881 }
882}
883
884macro_rules! impl_int_base_for_wrapping {
885 ($($t:ty)*) => {
886 $(
887 impl Wrappingable for $t {}
888 impl Add for Wrapping<$t> {
889 type Output = Self;
890 fn add(self, rhs: Self) -> Self::Output {
891 Self(self.0.wrapping_add(rhs.0))
892 }
893 }
894 impl Add<$t> for Wrapping<$t> {
895 type Output = Self;
896 fn add(self, rhs: $t) -> Self::Output {
897 Self(self.0.wrapping_add(rhs))
898 }
899 }
900 impl Sub for Wrapping<$t> {
901 type Output = Self;
902 fn sub(self, rhs: Self) -> Self::Output {
903 Self(self.0.wrapping_sub(rhs.0))
904 }
905 }
906 impl Sub<$t> for Wrapping<$t> {
907 type Output = Self;
908 fn sub(self, rhs: $t) -> Self::Output {
909 Self(self.0.wrapping_sub(rhs))
910 }
911 }
912 impl Mul for Wrapping<$t> {
913 type Output = Self;
914 fn mul(self, rhs: Self) -> Self::Output {
915 Self(self.0.wrapping_mul(rhs.0))
916 }
917 }
918 impl Mul<$t> for Wrapping<$t> {
919 type Output = Self;
920 fn mul(self, rhs: $t) -> Self::Output {
921 Self(self.0.wrapping_mul(rhs))
922 }
923 }
924 impl Div for Wrapping<$t> {
925 type Output = Self;
926 fn div(self, rhs: Self) -> Self::Output {
927 Self(self.0.wrapping_div(rhs.0))
928 }
929 }
930 impl Div<$t> for Wrapping<$t> {
931 type Output = Self;
932 fn div(self, rhs: $t) -> Self::Output {
933 Self(self.0.wrapping_div(rhs))
934 }
935 }
936 impl Rem for Wrapping<$t> {
937 type Output = Self;
938 fn rem(self, rhs: Self) -> Self::Output {
939 Self(self.0.wrapping_rem(rhs.0))
940 }
941 }
942 impl Rem<$t> for Wrapping<$t> {
943 type Output = Self;
944 fn rem(self, rhs: $t) -> Self::Output {
945 Self(self.0.wrapping_rem(rhs))
946 }
947 }
948 impl Sum for Wrapping<$t> {
949 fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
950 iter.fold(Self::zero(), |acc, x| acc + x)
951 }
952 }
953 impl Product for Wrapping<$t> {
954 fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
955 iter.fold(Self::one(), |acc, x| acc * x)
956 }
957 }
958 impl IntBase for Wrapping<$t> {
959 type Error = <$t as IntBase>::Error;
960 fn div_euclid(self, rhs: Self) -> Self { Self(self.0.wrapping_div_euclid(rhs.0)) }
961 fn rem_euclid(self, rhs: Self) -> Self { Self(self.0.wrapping_rem_euclid(rhs.0)) }
962 fn pow(self, exp: u32) -> Self { Self(self.0.wrapping_pow(exp)) }
963 fn from_str_radix(src: &str, radix: u32) -> Result<Self, Self::Error> { <$t as IntBase>::from_str_radix(src, radix).map(Self) }
964 fn ilog(self, base: Self) -> u32 { self.0.ilog(base.0) }
965 fn ilog2(self) -> u32 { self.0.ilog2() }
966 fn ilog10(self) -> u32 { self.0.ilog10() }
967 fn isqrt(self) -> Self { Self(self.0.isqrt()) }
968 fn midpoint(self, rhs: Self) -> Self { Self(self.0.midpoint(rhs.0)) }
969 }
970 impl From<$t> for Wrapping<$t> {
971 fn from(t: $t) -> Self {
972 Self(t)
973 }
974 }
975 )*
976 };
977}
978impl_int_base_for_wrapping!(u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize);
979
980macro_rules! impl_unsigned_signed_for_wrapping {
981 ($($unsigned:ident $signed:ident)*) => {
982 $(
983 impl Unsigned for Wrapping<$unsigned> {
984 type Signed = Wrapping<$signed>;
985 fn signed(self) -> Self::Signed { Wrapping(self.0.signed()) }
986 fn abs_diff(self, other: Self) -> Self { Self(self.0.abs_diff(other.0)) }
987 fn div_ceil(self, rhs: Self) -> Self { Self(self.0.div_ceil(rhs.0)) }
988 fn is_power_of_two(self) -> bool { self.0.is_power_of_two() }
989 fn next_power_of_two(self) -> Self { Self(self.0.next_power_of_two()) }
990 fn is_multiple_of(self, rhs: Self) -> bool { self.0.is_multiple_of(rhs.0) }
991 fn next_multiple_of(self, rhs: Self) -> Self { Self(self.0.next_multiple_of(rhs.0)) }
992 fn gcd(self, other: Self) -> Self { Self(self.0.gcd(other.0)) }
993 fn mod_add(self, rhs: Self, modulo: Self) -> Self { Self(self.0.mod_add(rhs.0, modulo.0)) }
994 fn mod_sub(self, rhs: Self, modulo: Self) -> Self { Self(self.0.mod_sub(rhs.0, modulo.0)) }
995 fn mod_mul(self, rhs: Self, modulo: Self) -> Self { Self(self.0.mod_mul(rhs.0, modulo.0)) }
996 }
997 impl Signed for Wrapping<$signed> {
998 type Unsigned = Wrapping<$unsigned>;
999 fn unsigned(self) -> Self::Unsigned { Wrapping(self.0.unsigned()) }
1000 fn abs(self) -> Self { Self(self.0.wrapping_abs()) }
1001 fn abs_diff(self, other: Self) -> Self::Unsigned { Wrapping(self.0.abs_diff(other.0)) }
1002 fn is_negative(self) -> bool { self.0.is_negative() }
1003 fn is_positive(self) -> bool { self.0.is_positive() }
1004 fn signum(self) -> Self { Self(self.0.signum()) }
1005 }
1006 impl Neg for Wrapping<$signed> {
1007 type Output = Self;
1008 fn neg(self) -> Self::Output {
1009 Self(self.0.wrapping_neg())
1010 }
1011 }
1012 )*
1013 };
1014}
1015impl_unsigned_signed_for_wrapping!(u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize);
1016
1017macro_rules! impl_binary_repr_for_wrapping {
1018 ($($t:ty)*) => {
1019 $(
1020 impl Shl<u32> for Wrapping<$t> {
1021 type Output = Self;
1022 fn shl(self, rhs: u32) -> Self::Output {
1023 Self(self.0.wrapping_shl(rhs))
1024 }
1025 }
1026 impl Shr<u32> for Wrapping<$t> {
1027 type Output = Self;
1028 fn shr(self, rhs: u32) -> Self::Output {
1029 Self(self.0.wrapping_shr(rhs))
1030 }
1031 }
1032 impl ShlAssign<u32> for Wrapping<$t> {
1033 fn shl_assign(&mut self, rhs: u32) {
1034 *self = Shl::shl(*self, rhs);
1035 }
1036 }
1037 impl ShrAssign<u32> for Wrapping<$t> {
1038 fn shr_assign(&mut self, rhs: u32) {
1039 *self = Shr::shr(*self, rhs);
1040 }
1041 }
1042 impl BinaryRepr for Wrapping<$t> {
1043 fn count_ones(self) -> u32 { self.0.count_ones() }
1044 fn count_zeros(self) -> u32 { self.0.count_zeros() }
1045 fn leading_ones(self) -> u32 { self.0.leading_ones() }
1046 fn leading_zeros(self) -> u32 { self.0.leading_zeros() }
1047 fn reverse_bits(self) -> Self { Self(self.0.reverse_bits()) }
1048 fn rotate_left(self, n: u32) -> Self { Self(self.0.rotate_left(n)) }
1049 fn rotate_right(self, n: u32) -> Self { Self(self.0.rotate_right(n)) }
1050 fn swap_bytes(self) -> Self { Self(self.0.swap_bytes()) }
1051 fn trailing_ones(self) -> u32 { self.0.trailing_ones() }
1052 fn trailing_zeros(self) -> u32 { self.0.trailing_zeros() }
1053 }
1054 )*
1055 };
1056}
1057impl_binary_repr_for_wrapping!(u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize);
1058
1059#[cfg(test)]
1060mod tests {
1061 use super::*;
1062 use crate::tools::{Scanner, Xorshift, testutil::integer_boundary_values};
1063 use std::array;
1064 const Q: usize = 10_000;
1065
1066 mod int_base {
1067 macro_rules! test_intbase {
1068 ($($t:ident)*) => {
1069 $(
1070 mod $t {
1071 use super::super::*;
1072
1073 #[test]
1074 fn test_intbase() {
1075 let mut rng = Xorshift::default();
1076 let mut values = integer_boundary_values!($t);
1077 values.extend((0..=u8::MAX).map(|a| a as $t));
1078 values.sort_unstable();
1079 values.dedup();
1080 let pairs: Vec<_> = values.iter().flat_map(|&a| values.iter().map(move |&b| (a, b)))
1081 .chain(rng.random_iter((.., ..)).take(Q)).collect();
1082 for (a, b) in pairs {
1083 if let Some(expected) = a.checked_div_euclid(b) {
1084 assert_eq!(<$t as IntBase>::div_euclid(a, b), expected);
1085 assert_eq!(<$t as IntBase>::rem_euclid(a, b), a.rem_euclid(b));
1086 }
1087 if a > 0 && b > 1 {
1088 assert_eq!(<$t as IntBase>::ilog(a, b), a.ilog(b));
1089 }
1090 assert_eq!(<$t as IntBase>::midpoint(a, b), a.midpoint(b));
1091 }
1092 for a in values.into_iter().chain(rng.random_iter(..).take(Q)) {
1093 for n in (0..=8).chain([$t::BITS - 1, $t::BITS, $t::BITS + 1]) {
1094 if let Some(expected) = a.checked_pow(n) {
1095 assert_eq!(<$t as IntBase>::pow(a, n), expected);
1096 }
1097 }
1098 assert_eq!(<$t as IntBase>::from_str_radix(&a.to_string(), 10).unwrap(), a);
1099 if a >= <$t>::zero() {
1100 assert_eq!(<$t as IntBase>::from_str_radix(&format!("{a:x}"), 16).unwrap(), a);
1101 assert_eq!(<$t as IntBase>::from_str_radix(&format!("{a:b}"), 2).unwrap(), a);
1102 assert_eq!(<$t as IntBase>::isqrt(a), a.isqrt());
1103 }
1104 if a > 0 {
1105 assert_eq!(<$t as IntBase>::ilog2(a), a.ilog2());
1106 assert_eq!(<$t as IntBase>::ilog10(a), a.ilog10());
1107 }
1108 }
1109 }
1110 }
1111 )*
1112 };
1113 }
1114 test_intbase!(u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize);
1115 }
1116
1117 mod unsigned {
1118 use super::*;
1119
1120 macro_rules! test_unsigned {
1121 ($($t:ident)*) => {
1122 $(
1123 mod $t {
1124 use super::super::*;
1125 const A: $t = $t::MAX / 2;
1126 fn gcd(mut a: $t, mut b: $t) -> $t {
1127 while b != 0 {
1128 a %= b;
1129 std::mem::swap(&mut a, &mut b);
1130 }
1131 a
1132 }
1133 #[test]
1134 fn test_gcd() {
1135 let mut rng = Xorshift::default();
1136 for (a, b) in (0..=15).flat_map(|a| (0..=15).map(move |b| (a, b))).chain(rng.random_iter((0..=A, 0..=A)).take(Q)) {
1137 assert_eq!(a.gcd(b), gcd(a, b));
1138 }
1139
1140 }
1141 #[test]
1142 fn test_mod_inv() {
1143 let mut rng = Xorshift::default();
1144 for _ in 0..Q {
1145 let m = rng.random(2..=A);
1146 let a = rng.random(1..m);
1147 let g = a.gcd(m);
1148 let m = m / g;
1149 let a = a / g;
1150 let x = a.mod_inv(m);
1151 assert!(x < m);
1152 assert_eq!(a as u128 * x as u128 % m as u128, 1);
1153 }
1154 }
1155 #[test]
1156 fn test_mod_operate() {
1157 let mut rng = Xorshift::default();
1158 for _ in 0..Q {
1159 for ub in [10, A] {
1160 let m = rng.random(2..=ub);
1161 let a = rng.random(0..m);
1162 let b = rng.random(0..m);
1163 assert_eq!(a.mod_add(b, m), ((a as u128 + b as u128) % m as u128) as $t);
1164 assert_eq!(a.mod_sub(b, m), ((a as u128 + m as u128 - b as u128) % m as u128) as $t);
1165 assert_eq!(a.mod_mul(b, m), (a as u128 * b as u128 % m as u128) as $t);
1166 assert_eq!(a.mod_mul(b, m), (a as u128).mod_mul(b as u128, m as u128) as $t);
1167 assert_eq!(a.mod_neg(m), ((m as u128 - a as u128) % m as u128) as $t);
1168 }
1169 }
1170 }
1171 #[test]
1172 fn test_unsigned() {
1173 let mut rng = Xorshift::default();
1174 let mut values = integer_boundary_values!($t);
1175 if $t::BITS == 8 { values = ($t::MIN..=$t::MAX).collect(); }
1176 let pairs: Vec<_> = values.iter().flat_map(|&a| values.iter().map(move |&b| (a, b))).chain(rng.random_iter((.., ..)).take(Q)).collect();
1177 for (a, b) in pairs {
1178 assert_eq!(<$t as Unsigned>::abs_diff(a, b), a.abs_diff(b));
1179 assert_eq!(<$t as Unsigned>::is_power_of_two(a), a.is_power_of_two());
1180 assert_eq!(<$t as Unsigned>::is_multiple_of(a, b), a.is_multiple_of(b));
1181 assert_eq!(<$t as Unsigned>::gcd(a, b), gcd(a, b));
1182 if b != 0 {
1183 assert_eq!(<$t as Unsigned>::div_ceil(a, b), a.div_ceil(b));
1184 }
1185 if let Some(expected) = a.checked_next_power_of_two() {
1186 assert_eq!(<$t as Unsigned>::next_power_of_two(a), expected);
1187 }
1188 if let Some(expected) = a.checked_next_multiple_of(b) {
1189 assert_eq!(<$t as Unsigned>::next_multiple_of(a, b), expected);
1190 }
1191 let a: $t = rng.random(0..=15);
1192 let b: $t = rng.random(0..=15);
1193 let expected = (1..=a * b).find(|x| x % a == 0 && x % b == 0).unwrap_or(0);
1194 assert_eq!(<$t as Unsigned>::lcm(a, b), expected);
1195 assert_eq!(<$t as Unsigned>::signed(a) as $t, a);
1196 }
1197 }
1198 }
1199 )*
1200 };
1201 }
1202 test_unsigned!(u8 u16 u32 u64 usize);
1203
1204 #[test]
1205 fn test_mod_mul_u128() {
1206 fn naive_mod_mul(a: u128, b: u128, m: u128) -> u128 {
1207 assert!(m != 0);
1208 let a = [a as u64, (a >> 64) as u64];
1209 let b = [b as u64, (b >> 64) as u64];
1210 let mut res = 0u128;
1211 for (i, &a) in a.iter().enumerate() {
1212 for (j, &b) in b.iter().enumerate() {
1213 let mut x = (a as u128) * (b as u128) % m;
1214 for _ in 0..(i + j) * 64 {
1215 x = x.mod_add(x, m);
1216 }
1217 res = res.mod_add(x, m);
1218 }
1219 }
1220 res
1221 }
1222
1223 let mut rng = Xorshift::default();
1224 for _ in 0..100 {
1225 for a in [1, 10, u32::MAX as _, u64::MAX as _, u128::MAX] {
1226 for b in [1, 10, u32::MAX as _, u64::MAX as _, u128::MAX] {
1227 for c in [1, 10, u32::MAX as _, u64::MAX as _, u128::MAX] {
1228 let m = rng.random(1..=c);
1229 let x = rng.random(0..a.min(m));
1230 let y = rng.random(0..b.min(m));
1231 assert_eq!(x.mod_mul(y, m), naive_mod_mul(x, y, m));
1232 let x = rng.random(0..a);
1233 let y = rng.random(0..b);
1234 assert_eq!(x.mod_mul(y, m), naive_mod_mul(x, y, m));
1235 }
1236 }
1237 }
1238 }
1239 }
1240
1241 #[test]
1242 fn test_rem() {
1243 fn naive_rem(u: [u64; 4], v: u128) -> u128 {
1244 assert!(v != 0);
1245 let mut u = [
1246 ((u[1] as u128) << 64) | (u[0] as u128),
1247 ((u[3] as u128) << 64) | (u[2] as u128),
1248 ];
1249 let mut v_mul_2 = vec![[v, 0]];
1250 while v_mul_2.last().unwrap()[1].leading_zeros() != 0 {
1251 let [v_lo, v_hi] = *v_mul_2.last().unwrap();
1252 v_mul_2.push([v_lo << 1, v_hi << 1 | (v_lo >> 127)]);
1253 }
1254 v_mul_2.reverse();
1255 for [v_lo, v_hi] in v_mul_2 {
1256 let [u_lo, u_hi] = u;
1257 if (u_hi > v_hi) || (u_hi == v_hi && u_lo >= v_lo) {
1258 let (new_lo, carry) = u_lo.overflowing_sub(v_lo);
1259 let new_hi = u_hi - v_hi - (carry as u128);
1260 u = [new_lo, new_hi];
1261 }
1262 }
1263 u[0]
1264 }
1265 let mut rng = Xorshift::default();
1266 for _ in 0..1000 {
1267 let mut u = [0u64; 4];
1268 for k in 0..4 {
1269 for a in [1, 10, u32::MAX as _, u64::MAX] {
1270 u[k] = rng.random(..a);
1271 for b in [1, 10, u128::MAX] {
1272 let v = rng.random(1..=b);
1273 assert_eq!(rem_u256_by_u128(u, v), naive_rem(u, v));
1274 }
1275 }
1276 }
1277 }
1278 for _ in 0..1000 {
1279 let u = array::from_fn(|_| rng.random(..));
1280 let v = rng.random(1..);
1281 assert_eq!(rem_u256_by_u128(u, v), naive_rem(u, v));
1282 }
1283 }
1284 }
1285
1286 mod signed {
1287 macro_rules! test_signed {
1288 ($($t:ident)*) => {
1289 $(
1290 mod $t {
1291 use super::super::*;
1292 const A: $t = $t::MAX / 2;
1293 #[test]
1294 fn test_extgcd() {
1295 let mut rng = Xorshift::default();
1296 for (a, b) in rng.random_iter((-A..=A, -A..=A)).take(Q) {
1297 let ExtendedGcd { g, x, y } = a.extgcd(b);
1298 assert_eq!(g, a.abs().unsigned().gcd(b.abs().unsigned()));
1299 assert_eq!(a as i128 * x as i128 + b as i128 * y as i128, g.signed() as i128);
1300 }
1301 }
1302 #[test]
1303 fn test_signed() {
1304 let mut rng = Xorshift::default();
1305 let mut values = integer_boundary_values!($t);
1306 if $t::BITS == 8 { values = ($t::MIN..=$t::MAX).collect(); }
1307 let pairs: Vec<_> = values.iter().flat_map(|&a| values.iter().map(move |&b| (a, b))).chain(rng.random_iter((.., ..)).take(Q)).collect();
1308 for (a, b) in pairs {
1309 if let Some(expected) = a.checked_abs() {
1310 assert_eq!(<$t as Signed>::abs(a), expected);
1311 }
1312 assert_eq!(<$t as Signed>::abs_diff(a, b), a.abs_diff(b));
1313 assert_eq!(<$t as Signed>::is_negative(a), a < 0);
1314 assert_eq!(<$t as Signed>::is_positive(a), a > 0);
1315 assert_eq!(<$t as Signed>::signum(a), a.signum());
1316 let a = rng.random(0..=$t::MAX);
1317 assert_eq!(<$t as Signed>::unsigned(a) as $t, a);
1318 }
1319 }
1320 }
1321 )*
1322 };
1323 }
1324 test_signed!(i8 i16 i32 i64 isize);
1325 }
1326
1327 macro_rules! test_binary_repr {
1328 ($($t:ident)*) => {
1329 $(
1330 mod $t {
1331 use super::super::*;
1332 #[test]
1333 fn test_binary_repr() {
1334 let mut rng = Xorshift::default();
1335 for a in integer_boundary_values!($t).into_iter().chain(rng.random_iter(..).take(Q)).collect::<Vec<_>>() {
1336 let n = rng.random(0..=2 * $t::BITS);
1337 assert_eq!(<$t as BinaryRepr>::count_ones(a), a.count_ones());
1338 assert_eq!(<$t as BinaryRepr>::count_zeros(a), a.count_zeros());
1339 assert_eq!(<$t as BinaryRepr>::leading_ones(a), a.leading_ones());
1340 assert_eq!(<$t as BinaryRepr>::leading_zeros(a), a.leading_zeros());
1341 assert_eq!(<$t as BinaryRepr>::reverse_bits(a), a.reverse_bits());
1342 assert_eq!(<$t as BinaryRepr>::swap_bytes(a), a.swap_bytes());
1343 assert_eq!(<$t as BinaryRepr>::trailing_ones(a), a.trailing_ones());
1344 assert_eq!(<$t as BinaryRepr>::trailing_zeros(a), a.trailing_zeros());
1345 assert_eq!(<$t as BinaryRepr>::rotate_left(a, n), a.rotate_left(n));
1346 assert_eq!(<$t as BinaryRepr>::rotate_right(a, n), a.rotate_right(n));
1347 }
1348 }
1349 }
1350 )*
1351 }
1352 }
1353 mod binary_repr {
1354 test_binary_repr!(u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize);
1355 }
1356
1357 mod saturating {
1358 macro_rules! test_saturating {
1359 ($($unsigned:ident $signed:ident)*) => {
1360 $(
1361 mod $unsigned {
1362 use super::super::*;
1363 type S = Saturating<$unsigned>;
1364
1365 test_saturating!(@common $unsigned);
1366 test_saturating!(@unsigned $unsigned);
1367 }
1368 mod $signed {
1369 use super::super::*;
1370 type S = Saturating<$signed>;
1371
1372 test_saturating!(@common $signed);
1373 test_saturating!(@signed $signed);
1374 }
1375 )*
1376 };
1377 (@common $t:ident) => {
1378 macro_rules! assign {
1379 ($op:tt, $left:expr, $right:expr) => {{
1380 let mut a = $left;
1381 a $op $right;
1382 a
1383 }};
1384 }
1385
1386 #[test]
1387 fn test_saturating() {
1388 let mut rng = Xorshift::default();
1389 let mut values = integer_boundary_values!($t);
1390 if $t::BITS == 8 { values = ($t::MIN..=$t::MAX).collect(); }
1391 let pairs: Vec<_> = values.iter().flat_map(|&a| values.iter().map(move |&b| (a, b))).chain(rng.random_iter((.., ..)).take(Q)).collect();
1392 for (a, b) in pairs {
1393 let n = rng.random(0..=2 * $t::BITS);
1394 assert_eq!(a.to_saturating(), S::from(a));
1395 assert_eq!($t::from_saturating(a.to_saturating()), a);
1396 assert_eq!(S::maximum(), S::from($t::MAX));
1397 assert_eq!(S::minimum(), S::from($t::MIN));
1398 assert_eq!(S::zero(), S::from(0));
1399 assert_eq!(S::one(), S::from(1));
1400 assert_eq!(S::from(a).to_string(), a.to_string());
1401 assert_eq!(S::from_str(&a.to_string()).unwrap(), S::from(a));
1402 assert_eq!(format!("{:?}", S::from(a)), format!("{a:?}"));
1403 assert_eq!(S::scan(&mut Scanner::new(&a.to_string())).unwrap(), S::from(a));
1404 assert_eq!(S::from(a) + S::from(b), S::from(a.saturating_add(b)));
1405 assert_eq!(assign!(+=, S::from(a), S::from(b)), S::from(a.saturating_add(b)));
1406 assert_eq!(S::from(a) + b, S::from(a.saturating_add(b)));
1407 assert_eq!(assign!(+=, S::from(a), b), S::from(a.saturating_add(b)));
1408 assert_eq!(S::from(a) - S::from(b), S::from(a.saturating_sub(b)));
1409 assert_eq!(assign!(-=, S::from(a), S::from(b)), S::from(a.saturating_sub(b)));
1410 assert_eq!(S::from(a) - b, S::from(a.saturating_sub(b)));
1411 assert_eq!(assign!(-=, S::from(a), b), S::from(a.saturating_sub(b)));
1412 assert_eq!(S::from(a) * S::from(b), S::from(a.saturating_mul(b)));
1413 assert_eq!(assign!(*=, S::from(a), S::from(b)), S::from(a.saturating_mul(b)));
1414 assert_eq!(S::from(a) * b, S::from(a.saturating_mul(b)));
1415 assert_eq!(assign!(*=, S::from(a), b), S::from(a.saturating_mul(b)));
1416 assert_eq!(S::from(a) & S::from(b), S::from(a & b));
1417 assert_eq!(assign!(&=, S::from(a), S::from(b)), S::from(a & b));
1418 assert_eq!(S::from(a) & b, S::from(a & b));
1419 assert_eq!(assign!(&=, S::from(a), b), S::from(a & b));
1420 assert_eq!(S::from(a) | S::from(b), S::from(a | b));
1421 assert_eq!(assign!(|=, S::from(a), S::from(b)), S::from(a | b));
1422 assert_eq!(S::from(a) | b, S::from(a | b));
1423 assert_eq!(assign!(|=, S::from(a), b), S::from(a | b));
1424 assert_eq!(S::from(a) ^ S::from(b), S::from(a ^ b));
1425 assert_eq!(assign!(^=, S::from(a), S::from(b)), S::from(a ^ b));
1426 assert_eq!(S::from(a) ^ b, S::from(a ^ b));
1427 assert_eq!(assign!(^=, S::from(a), b), S::from(a ^ b));
1428 if a.checked_div(b).is_some() {
1429 assert_eq!(S::from(a) / S::from(b), S::from(a / b));
1430 assert_eq!(assign!(/=, S::from(a), S::from(b)), S::from(a / b));
1431 assert_eq!(S::from(a) / b, S::from(a / b));
1432 assert_eq!(assign!(/=, S::from(a), b), S::from(a / b));
1433 assert_eq!(S::from(a) % S::from(b), S::from(a % b));
1434 assert_eq!(assign!(%=, S::from(a), S::from(b)), S::from(a % b));
1435 assert_eq!(S::from(a) % b, S::from(a % b));
1436 assert_eq!(assign!(%=, S::from(a), b), S::from(a % b));
1437 assert_eq!(S::from(a).div_euclid(S::from(b)), S::from(a.div_euclid(b)));
1438 assert_eq!(S::from(a).rem_euclid(S::from(b)), S::from(a.rem_euclid(b)));
1439 }
1440 assert_eq!(S::from(a) << n, S::from(a.checked_shl(n).unwrap_or(0)));
1441 assert_eq!(assign!(<<=, S::from(a), n), S::from(a.checked_shl(n).unwrap_or(0)));
1442 assert_eq!(S::from(a) >> n, S::from(a.checked_shr(n).unwrap_or(0)));
1443 assert_eq!(assign!(>>=, S::from(a), n), S::from(a.checked_shr(n).unwrap_or(0)));
1444 assert_eq!(!S::from(a), S::from(!a));
1445 let sum: S = [S::from(a), S::from(b)].into_iter().sum();
1446 let product: S = [S::from(a), S::from(b)].into_iter().product();
1447 assert_eq!(sum, S::from(a.saturating_add(b)));
1448 assert_eq!(product, S::from(a.saturating_mul(b)));
1449 assert_eq!(S::from(a).pow(n), S::from(a.saturating_pow(n)));
1450 assert_eq!(S::from_str_radix(&a.to_string(), 10).unwrap(), S::from(a));
1451 assert_eq!(S::from(a).count_ones(), a.count_ones());
1452 assert_eq!(S::from(a).count_zeros(), a.count_zeros());
1453 assert_eq!(S::from(a).leading_ones(), a.leading_ones());
1454 assert_eq!(S::from(a).leading_zeros(), a.leading_zeros());
1455 assert_eq!(S::from(a).trailing_ones(), a.trailing_ones());
1456 assert_eq!(S::from(a).trailing_zeros(), a.trailing_zeros());
1457 assert_eq!(S::from(a).reverse_bits(), S::from(a.reverse_bits()));
1458 assert_eq!(S::from(a).swap_bytes(), S::from(a.swap_bytes()));
1459 assert_eq!(S::from(a).rotate_left(n), S::from(a.rotate_left(n)));
1460 assert_eq!(S::from(a).rotate_right(n), S::from(a.rotate_right(n)));
1461 let a = rng.random(1..=$t::MAX);
1462 let b = rng.random(2..=$t::MAX);
1463 assert_eq!(S::from(a).ilog(S::from(b)), a.ilog(b));
1464 assert_eq!(S::from(a).ilog2(), a.ilog2());
1465 assert_eq!(S::from(a).ilog10(), a.ilog10());
1466 }
1467 }
1468 };
1469 (@unsigned $t:ident) => {
1470 #[test]
1471 fn test_saturating_unsigned() {
1472 let mut rng = Xorshift::default();
1473 for _ in 0..Q {
1474 let a: $t = rng.random(0..=$t::MAX / 2);
1475 let b: $t = rng.random(0..=$t::MAX / 2);
1476 let m: $t = rng.random(1..=$t::MAX);
1477 assert_eq!(S::from(a).signed().0 as $t, a);
1478 assert_eq!(S::from(a).abs_diff(S::from(b)), S::from(a.abs_diff(b)));
1479 assert_eq!(S::from(a).next_power_of_two(), S::from(a.next_power_of_two()));
1480 assert_eq!(S::from(a).gcd(S::from(b)), S::from(a.gcd(b)));
1481 let a = a % m;
1482 let b = b % m;
1483 assert_eq!(S::from(a).mod_add(S::from(b), S::from(m)), S::from(a.mod_add(b, m)));
1484 assert_eq!(S::from(a).mod_sub(S::from(b), S::from(m)), S::from(a.mod_sub(b, m)));
1485 assert_eq!(S::from(a).mod_mul(S::from(b), S::from(m)), S::from(a.mod_mul(b, m)));
1486 }
1487 }
1488 };
1489 (@signed $t:ident) => {
1490 #[test]
1491 fn test_saturating_signed() {
1492 let mut rng = Xorshift::default();
1493 let mut values = integer_boundary_values!($t);
1494 if $t::BITS == 8 { values = ($t::MIN..=$t::MAX).collect(); }
1495 let pairs: Vec<_> = values.iter().flat_map(|&a| values.iter().map(move |&b| (a, b))).chain(rng.random_iter((.., ..)).take(Q)).collect();
1496 for (a, b) in pairs {
1497 assert_eq!(S::from(a).abs(), S::from(a.saturating_abs()));
1498 assert_eq!(S::from(a).abs_diff(S::from(b)).0, a.abs_diff(b));
1499 assert_eq!(S::from(a).is_negative(), a < 0);
1500 assert_eq!(S::from(a).is_positive(), a > 0);
1501 assert_eq!(S::from(a).signum(), S::from(a.signum()));
1502 assert_eq!(-S::from(a), S::from(a.saturating_neg()));
1503 let a = rng.random(0..=$t::MAX);
1504 assert_eq!(S::from(a).unsigned().0 as $t, a);
1505 }
1506 }
1507 };
1508 }
1509 test_saturating!(u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize);
1510 }
1511
1512 mod wrapping {
1513 macro_rules! test_wrapping {
1514 ($($unsigned:ident $signed:ident)*) => {
1515 $(
1516 mod $unsigned {
1517 use super::super::*;
1518 type W = Wrapping<$unsigned>;
1519
1520 test_wrapping!(@common $unsigned);
1521 test_wrapping!(@unsigned $unsigned);
1522 }
1523 mod $signed {
1524 use super::super::*;
1525 type W = Wrapping<$signed>;
1526
1527 test_wrapping!(@common $signed);
1528 test_wrapping!(@signed $signed);
1529 }
1530 )*
1531 };
1532 (@common $t:ident) => {
1533 macro_rules! assign {
1534 ($op:tt, $left:expr, $right:expr) => {{
1535 let mut a = $left;
1536 a $op $right;
1537 a
1538 }};
1539 }
1540
1541 #[test]
1542 fn test_wrapping() {
1543 let mut rng = Xorshift::default();
1544 let mut values = integer_boundary_values!($t);
1545 if $t::BITS == 8 { values = ($t::MIN..=$t::MAX).collect(); }
1546 let pairs: Vec<_> = values.iter().flat_map(|&a| values.iter().map(move |&b| (a, b))).chain(rng.random_iter((.., ..)).take(Q)).collect();
1547 for (a, b) in pairs {
1548 let n = rng.random(0..=2 * $t::BITS);
1549 assert_eq!(a.to_wrapping(), W::from(a));
1550 assert_eq!($t::from_wrapping(a.to_wrapping()), a);
1551 assert_eq!(W::maximum(), W::from($t::MAX));
1552 assert_eq!(W::minimum(), W::from($t::MIN));
1553 assert_eq!(W::zero(), W::from(0));
1554 assert_eq!(W::one(), W::from(1));
1555 assert_eq!(W::from(a).to_string(), a.to_string());
1556 assert_eq!(W::from_str(&a.to_string()).unwrap(), W::from(a));
1557 assert_eq!(format!("{:?}", W::from(a)), format!("{a:?}"));
1558 assert_eq!(W::scan(&mut Scanner::new(&a.to_string())).unwrap(), W::from(a));
1559 assert_eq!(W::from(a) + W::from(b), W::from(a.wrapping_add(b)));
1560 assert_eq!(assign!(+=, W::from(a), W::from(b)), W::from(a.wrapping_add(b)));
1561 assert_eq!(W::from(a) + b, W::from(a.wrapping_add(b)));
1562 assert_eq!(assign!(+=, W::from(a), b), W::from(a.wrapping_add(b)));
1563 assert_eq!(W::from(a) - W::from(b), W::from(a.wrapping_sub(b)));
1564 assert_eq!(assign!(-=, W::from(a), W::from(b)), W::from(a.wrapping_sub(b)));
1565 assert_eq!(W::from(a) - b, W::from(a.wrapping_sub(b)));
1566 assert_eq!(assign!(-=, W::from(a), b), W::from(a.wrapping_sub(b)));
1567 assert_eq!(W::from(a) * W::from(b), W::from(a.wrapping_mul(b)));
1568 assert_eq!(assign!(*=, W::from(a), W::from(b)), W::from(a.wrapping_mul(b)));
1569 assert_eq!(W::from(a) * b, W::from(a.wrapping_mul(b)));
1570 assert_eq!(assign!(*=, W::from(a), b), W::from(a.wrapping_mul(b)));
1571 assert_eq!(W::from(a) & W::from(b), W::from(a & b));
1572 assert_eq!(assign!(&=, W::from(a), W::from(b)), W::from(a & b));
1573 assert_eq!(W::from(a) & b, W::from(a & b));
1574 assert_eq!(assign!(&=, W::from(a), b), W::from(a & b));
1575 assert_eq!(W::from(a) | W::from(b), W::from(a | b));
1576 assert_eq!(assign!(|=, W::from(a), W::from(b)), W::from(a | b));
1577 assert_eq!(W::from(a) | b, W::from(a | b));
1578 assert_eq!(assign!(|=, W::from(a), b), W::from(a | b));
1579 assert_eq!(W::from(a) ^ W::from(b), W::from(a ^ b));
1580 assert_eq!(assign!(^=, W::from(a), W::from(b)), W::from(a ^ b));
1581 assert_eq!(W::from(a) ^ b, W::from(a ^ b));
1582 assert_eq!(assign!(^=, W::from(a), b), W::from(a ^ b));
1583 if b != 0 {
1584 assert_eq!(W::from(a) / W::from(b), W::from(a.wrapping_div(b)));
1585 assert_eq!(assign!(/=, W::from(a), W::from(b)), W::from(a.wrapping_div(b)));
1586 assert_eq!(W::from(a) / b, W::from(a.wrapping_div(b)));
1587 assert_eq!(assign!(/=, W::from(a), b), W::from(a.wrapping_div(b)));
1588 assert_eq!(W::from(a) % W::from(b), W::from(a.wrapping_rem(b)));
1589 assert_eq!(assign!(%=, W::from(a), W::from(b)), W::from(a.wrapping_rem(b)));
1590 assert_eq!(W::from(a) % b, W::from(a.wrapping_rem(b)));
1591 assert_eq!(assign!(%=, W::from(a), b), W::from(a.wrapping_rem(b)));
1592 assert_eq!(W::from(a).div_euclid(W::from(b)), W::from(a.wrapping_div_euclid(b)));
1593 assert_eq!(W::from(a).rem_euclid(W::from(b)), W::from(a.wrapping_rem_euclid(b)));
1594 }
1595 assert_eq!(W::from(a) << n, W::from(a.wrapping_shl(n)));
1596 assert_eq!(assign!(<<=, W::from(a), n), W::from(a.wrapping_shl(n)));
1597 assert_eq!(W::from(a) >> n, W::from(a.wrapping_shr(n)));
1598 assert_eq!(assign!(>>=, W::from(a), n), W::from(a.wrapping_shr(n)));
1599 assert_eq!(!W::from(a), W::from(!a));
1600 let sum: W = [W::from(a), W::from(b)].into_iter().sum();
1601 let product: W = [W::from(a), W::from(b)].into_iter().product();
1602 assert_eq!(sum, W::from(a.wrapping_add(b)));
1603 assert_eq!(product, W::from(a.wrapping_mul(b)));
1604 assert_eq!(W::from(a).pow(n), W::from(a.wrapping_pow(n)));
1605 assert_eq!(W::from_str_radix(&a.to_string(), 10).unwrap(), W::from(a));
1606 assert_eq!(W::from(a).count_ones(), a.count_ones());
1607 assert_eq!(W::from(a).count_zeros(), a.count_zeros());
1608 assert_eq!(W::from(a).leading_ones(), a.leading_ones());
1609 assert_eq!(W::from(a).leading_zeros(), a.leading_zeros());
1610 assert_eq!(W::from(a).trailing_ones(), a.trailing_ones());
1611 assert_eq!(W::from(a).trailing_zeros(), a.trailing_zeros());
1612 assert_eq!(W::from(a).reverse_bits(), W::from(a.reverse_bits()));
1613 assert_eq!(W::from(a).swap_bytes(), W::from(a.swap_bytes()));
1614 assert_eq!(W::from(a).rotate_left(n), W::from(a.rotate_left(n)));
1615 assert_eq!(W::from(a).rotate_right(n), W::from(a.rotate_right(n)));
1616 let a = rng.random(1..=$t::MAX);
1617 let b = rng.random(2..=$t::MAX);
1618 assert_eq!(W::from(a).ilog(W::from(b)), a.ilog(b));
1619 assert_eq!(W::from(a).ilog2(), a.ilog2());
1620 assert_eq!(W::from(a).ilog10(), a.ilog10());
1621 }
1622 }
1623 };
1624 (@unsigned $t:ident) => {
1625 #[test]
1626 fn test_wrapping_unsigned() {
1627 let mut rng = Xorshift::default();
1628 for _ in 0..Q {
1629 let a: $t = rng.random(0..=$t::MAX / 2);
1630 let b: $t = rng.random(0..=$t::MAX / 2);
1631 let m: $t = rng.random(1..=$t::MAX);
1632 assert_eq!(W::from(a).signed().0 as $t, a);
1633 assert_eq!(W::from(a).abs_diff(W::from(b)), W::from(a.abs_diff(b)));
1634 assert_eq!(W::from(a).next_power_of_two(), W::from(a.next_power_of_two()));
1635 assert_eq!(W::from(a).gcd(W::from(b)), W::from(a.gcd(b)));
1636 let a = a % m;
1637 let b = b % m;
1638 assert_eq!(W::from(a).mod_add(W::from(b), W::from(m)), W::from(a.mod_add(b, m)));
1639 assert_eq!(W::from(a).mod_sub(W::from(b), W::from(m)), W::from(a.mod_sub(b, m)));
1640 assert_eq!(W::from(a).mod_mul(W::from(b), W::from(m)), W::from(a.mod_mul(b, m)));
1641 }
1642 }
1643 };
1644 (@signed $t:ident) => {
1645 #[test]
1646 fn test_wrapping_signed() {
1647 let mut rng = Xorshift::default();
1648 let mut values = integer_boundary_values!($t);
1649 if $t::BITS == 8 { values = ($t::MIN..=$t::MAX).collect(); }
1650 let pairs: Vec<_> = values.iter().flat_map(|&a| values.iter().map(move |&b| (a, b))).chain(rng.random_iter((.., ..)).take(Q)).collect();
1651 for (a, b) in pairs {
1652 assert_eq!(W::from(a).abs(), W::from(a.wrapping_abs()));
1653 assert_eq!(W::from(a).abs_diff(W::from(b)).0, a.abs_diff(b));
1654 assert_eq!(W::from(a).is_negative(), a < 0);
1655 assert_eq!(W::from(a).is_positive(), a > 0);
1656 assert_eq!(W::from(a).signum(), W::from(a.signum()));
1657 assert_eq!(-W::from(a), W::from(a.wrapping_neg()));
1658 let a = rng.random(0..=$t::MAX);
1659 assert_eq!(W::from(a).unsigned().0 as $t, a);
1660 }
1661 }
1662 };
1663 }
1664 test_wrapping!(u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize);
1665 }
1666}