| macro_rules! tests { |
| ($isqrt_consistency_check_fn_macro:ident : $($T:ident)+) => { |
| $( |
| mod $T { |
| $isqrt_consistency_check_fn_macro!($T); |
| |
| // Check that the following produce the correct values from |
| // `isqrt`: |
| // |
| // * the first and last 128 nonnegative values |
| // * powers of two, minus one |
| // * powers of two |
| // |
| // For signed types, check that `checked_isqrt` and `isqrt` |
| // either produce the same numeric value or respectively |
| // produce `None` and a panic. Make sure to do a consistency |
| // check for `<$T>::MIN` as well, as no nonnegative values |
| // negate to it. |
| // |
| // For unsigned types check that `isqrt` produces the same |
| // numeric value for `$T` and `NonZero<$T>`. |
| #[test] |
| fn isqrt() { |
| isqrt_consistency_check(<$T>::MIN); |
| |
| for n in (0..=127) |
| .chain(<$T>::MAX - 127..=<$T>::MAX) |
| .chain((0..<$T>::MAX.count_ones()).map(|exponent| (1 << exponent) - 1)) |
| .chain((0..<$T>::MAX.count_ones()).map(|exponent| 1 << exponent)) |
| { |
| isqrt_consistency_check(n); |
| |
| let isqrt_n = n.isqrt(); |
| assert!( |
| isqrt_n |
| .checked_mul(isqrt_n) |
| .map(|isqrt_n_squared| isqrt_n_squared <= n) |
| .unwrap_or(false), |
| "`{n}.isqrt()` should be lower than {isqrt_n}." |
| ); |
| assert!( |
| (isqrt_n + 1) |
| .checked_mul(isqrt_n + 1) |
| .map(|isqrt_n_plus_1_squared| n < isqrt_n_plus_1_squared) |
| .unwrap_or(true), |
| "`{n}.isqrt()` should be higher than {isqrt_n})." |
| ); |
| } |
| } |
| |
| // Check the square roots of: |
| // |
| // * the first 1,024 perfect squares |
| // * halfway between each of the first 1,024 perfect squares |
| // and the next perfect square |
| // * the next perfect square after the each of the first 1,024 |
| // perfect squares, minus one |
| // * the last 1,024 perfect squares |
| // * the last 1,024 perfect squares, minus one |
| // * halfway between each of the last 1,024 perfect squares |
| // and the previous perfect square |
| #[test] |
| // Skip this test on Miri, as it takes too long to run. |
| #[cfg(not(miri))] |
| fn isqrt_extended() { |
| // The correct value is worked out by using the fact that |
| // the nth nonzero perfect square is the sum of the first n |
| // odd numbers: |
| // |
| // 1 = 1 |
| // 4 = 1 + 3 |
| // 9 = 1 + 3 + 5 |
| // 16 = 1 + 3 + 5 + 7 |
| // |
| // Note also that the last odd number added in is two times |
| // the square root of the previous perfect square, plus |
| // one: |
| // |
| // 1 = 2*0 + 1 |
| // 3 = 2*1 + 1 |
| // 5 = 2*2 + 1 |
| // 7 = 2*3 + 1 |
| // |
| // That means we can add the square root of this perfect |
| // square once to get about halfway to the next perfect |
| // square, then we can add the square root of this perfect |
| // square again to get to the next perfect square, minus |
| // one, then we can add one to get to the next perfect |
| // square. |
| // |
| // This allows us to, for each of the first 1,024 perfect |
| // squares, test that the square roots of the following are |
| // all correct and equal to each other: |
| // |
| // * the current perfect square |
| // * about halfway to the next perfect square |
| // * the next perfect square, minus one |
| let mut n: $T = 0; |
| for sqrt_n in 0..1_024.min((1_u128 << (<$T>::MAX.count_ones()/2)) - 1) as $T { |
| isqrt_consistency_check(n); |
| assert_eq!( |
| n.isqrt(), |
| sqrt_n, |
| "`{sqrt_n}.pow(2).isqrt()` should be {sqrt_n}." |
| ); |
| |
| n += sqrt_n; |
| isqrt_consistency_check(n); |
| assert_eq!( |
| n.isqrt(), |
| sqrt_n, |
| "{n} is about halfway between `{sqrt_n}.pow(2)` and `{}.pow(2)`, so `{n}.isqrt()` should be {sqrt_n}.", |
| sqrt_n + 1 |
| ); |
| |
| n += sqrt_n; |
| isqrt_consistency_check(n); |
| assert_eq!( |
| n.isqrt(), |
| sqrt_n, |
| "`({}.pow(2) - 1).isqrt()` should be {sqrt_n}.", |
| sqrt_n + 1 |
| ); |
| |
| n += 1; |
| } |
| |
| // Similarly, for each of the last 1,024 perfect squares, |
| // check: |
| // |
| // * the current perfect square |
| // * the current perfect square, minus one |
| // * about halfway to the previous perfect square |
| // |
| // `MAX`'s `isqrt` return value is verified in the `isqrt` |
| // test function above. |
| let maximum_sqrt = <$T>::MAX.isqrt(); |
| let mut n = maximum_sqrt * maximum_sqrt; |
| |
| for sqrt_n in (maximum_sqrt - 1_024.min((1_u128 << (<$T>::MAX.count_ones()/2)) - 1) as $T..maximum_sqrt).rev() { |
| isqrt_consistency_check(n); |
| assert_eq!( |
| n.isqrt(), |
| sqrt_n + 1, |
| "`{0}.pow(2).isqrt()` should be {0}.", |
| sqrt_n + 1 |
| ); |
| |
| n -= 1; |
| isqrt_consistency_check(n); |
| assert_eq!( |
| n.isqrt(), |
| sqrt_n, |
| "`({}.pow(2) - 1).isqrt()` should be {sqrt_n}.", |
| sqrt_n + 1 |
| ); |
| |
| n -= sqrt_n; |
| isqrt_consistency_check(n); |
| assert_eq!( |
| n.isqrt(), |
| sqrt_n, |
| "{n} is about halfway between `{sqrt_n}.pow(2)` and `{}.pow(2)`, so `{n}.isqrt()` should be {sqrt_n}.", |
| sqrt_n + 1 |
| ); |
| |
| n -= sqrt_n; |
| } |
| } |
| } |
| )* |
| }; |
| } |
| |
| macro_rules! signed_check { |
| ($T:ident) => { |
| /// This takes an input and, if it's nonnegative or |
| #[doc = concat!("`", stringify!($T), "::MIN`,")] |
| /// checks that `isqrt` and `checked_isqrt` produce equivalent results |
| /// for that input and for the negative of that input. |
| /// |
| /// # Note |
| /// |
| /// This cannot check that negative inputs to `isqrt` cause panics if |
| /// panics abort instead of unwind. |
| fn isqrt_consistency_check(n: $T) { |
| // `<$T>::MIN` will be negative, so ignore it in this nonnegative |
| // section. |
| if n >= 0 { |
| assert_eq!( |
| Some(n.isqrt()), |
| n.checked_isqrt(), |
| "`{n}.checked_isqrt()` should match `Some({n}.isqrt())`.", |
| ); |
| } |
| |
| // `wrapping_neg` so that `<$T>::MIN` will negate to itself rather |
| // than panicking. |
| let negative_n = n.wrapping_neg(); |
| |
| // Zero negated will still be nonnegative, so ignore it in this |
| // negative section. |
| if negative_n < 0 { |
| assert_eq!( |
| negative_n.checked_isqrt(), |
| None, |
| "`({negative_n}).checked_isqrt()` should be `None`, as {negative_n} is negative.", |
| ); |
| |
| // `catch_unwind` only works when panics unwind rather than abort. |
| #[cfg(panic = "unwind")] |
| { |
| std::panic::catch_unwind(core::panic::AssertUnwindSafe(|| (-n).isqrt())).expect_err( |
| &format!("`({negative_n}).isqrt()` should have panicked, as {negative_n} is negative.") |
| ); |
| } |
| } |
| } |
| }; |
| } |
| |
| macro_rules! unsigned_check { |
| ($T:ident) => { |
| /// This takes an input and, if it's nonzero, checks that `isqrt` |
| /// produces the same numeric value for both |
| #[doc = concat!("`", stringify!($T), "` and ")] |
| #[doc = concat!("`NonZero<", stringify!($T), ">`.")] |
| fn isqrt_consistency_check(n: $T) { |
| // Zero cannot be turned into a `NonZero` value, so ignore it in |
| // this nonzero section. |
| if n > 0 { |
| assert_eq!( |
| n.isqrt(), |
| core::num::NonZero::<$T>::new(n) |
| .expect( |
| "Was not able to create a new `NonZero` value from a nonzero number." |
| ) |
| .isqrt() |
| .get(), |
| "`{n}.isqrt` should match `NonZero`'s `{n}.isqrt().get()`.", |
| ); |
| } |
| } |
| }; |
| } |
| |
| tests!(signed_check: i8 i16 i32 i64 i128); |
| tests!(unsigned_check: u8 u16 u32 u64 u128); |
