249 lines
10 KiB
Rust
249 lines
10 KiB
Rust
|
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);
|