1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
|
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);
|
