Debian Codegraph @

.cargo/vendor/num-integer/tests/roots.rs

raw
1 use num_integer::Roots;
2 use num_traits::checked_pow;
3 use num_traits::{AsPrimitive, PrimInt, Signed};
4 use std::f64::MANTISSA_DIGITS;
5 use std::fmt::Debug;
6 use std::mem;
7
8 trait TestInteger: Roots + PrimInt + Debug + AsPrimitive<f64> + 'static {}
9
10 impl<T> TestInteger for T where T: Roots + PrimInt + Debug + AsPrimitive<f64> + 'static {}
11
12 /// Check that each root is correct
13 ///
14 /// If `x` is positive, check `rⁿ ≤ x < (r+1)ⁿ`.
15 /// If `x` is negative, check `(r-1)ⁿ < x ≤ rⁿ`.
16 fn check<T>(v: &[T], n: u32)
17 where
18 T: TestInteger,
19 {
20 for i in v {
21 let rt = i.nth_root(n);
22 // println!("nth_root({:?}, {}) = {:?}", i, n, rt);
23 if n == 2 {
24 assert_eq!(rt, i.sqrt());
25 } else if n == 3 {
26 assert_eq!(rt, i.cbrt());
27 }
28 if *i >= T::zero() {
29 let rt1 = rt + T::one();
30 assert!(rt.pow(n) <= *i);
31 if let Some(x) = checked_pow(rt1, n as usize) {
32 assert!(*i < x);
33 }
34 } else {
35 let rt1 = rt - T::one();
36 assert!(rt < T::zero());
37 assert!(*i <= rt.pow(n));
38 if let Some(x) = checked_pow(rt1, n as usize) {
39 assert!(x < *i);
40 }
41 };
42 }
43 }
44
45 /// Get the maximum value that will round down as `f64` (if any),
46 /// and its successor that will round up.
47 ///
48 /// Important because the `std` implementations cast to `f64` to
49 /// get a close approximation of the roots.
50 fn mantissa_max<T>() -> Option<(T, T)>
51 where
52 T: TestInteger,
53 {
54 let bits = if T::min_value().is_zero() {
55 8 * mem::size_of::<T>()
56 } else {
57 8 * mem::size_of::<T>() - 1
58 };
59 if bits > MANTISSA_DIGITS as usize {
60 let rounding_bit = T::one() << (bits - MANTISSA_DIGITS as usize - 1);
61 let x = T::max_value() - rounding_bit;
62
63 let x1 = x + T::one();
64 let x2 = x1 + T::one();
65 assert!(x.as_() < x1.as_());
66 assert_eq!(x1.as_(), x2.as_());
67
68 Some((x, x1))
69 } else {
70 None
71 }
72 }
73
74 fn extend<T>(v: &mut Vec<T>, start: T, end: T)
75 where
76 T: TestInteger,
77 {
78 let mut i = start;
79 while i < end {
80 v.push(i);
81 i = i + T::one();
82 }
83 v.push(i);
84 }
85
86 fn extend_shl<T>(v: &mut Vec<T>, start: T, end: T, mask: T)
87 where
88 T: TestInteger,
89 {
90 let mut i = start;
91 while i != end {
92 v.push(i);
93 i = (i << 1) & mask;
94 }
95 }
96
97 fn extend_shr<T>(v: &mut Vec<T>, start: T, end: T)
98 where
99 T: TestInteger,
100 {
101 let mut i = start;
102 while i != end {
103 v.push(i);
104 i = i >> 1;
105 }
106 }
107
108 fn pos<T>() -> Vec<T>
109 where
110 T: TestInteger,
111 i8: AsPrimitive<T>,
112 {
113 let mut v: Vec<T> = vec![];
114 if mem::size_of::<T>() == 1 {
115 extend(&mut v, T::zero(), T::max_value());
116 } else {
117 extend(&mut v, T::zero(), i8::max_value().as_());
118 extend(
119 &mut v,
120 T::max_value() - i8::max_value().as_(),
121 T::max_value(),
122 );
123 if let Some((i, j)) = mantissa_max::<T>() {
124 v.push(i);
125 v.push(j);
126 }
127 extend_shl(&mut v, T::max_value(), T::zero(), !T::min_value());
128 extend_shr(&mut v, T::max_value(), T::zero());
129 }
130 v
131 }
132
133 fn neg<T>() -> Vec<T>
134 where
135 T: TestInteger + Signed,
136 i8: AsPrimitive<T>,
137 {
138 let mut v: Vec<T> = vec![];
139 if mem::size_of::<T>() <= 1 {
140 extend(&mut v, T::min_value(), T::zero());
141 } else {
142 extend(&mut v, i8::min_value().as_(), T::zero());
143 extend(
144 &mut v,
145 T::min_value(),
146 T::min_value() - i8::min_value().as_(),
147 );
148 if let Some((i, j)) = mantissa_max::<T>() {
149 v.push(-i);
150 v.push(-j);
151 }
152 extend_shl(&mut v, -T::one(), T::min_value(), !T::zero());
153 extend_shr(&mut v, T::min_value(), -T::one());
154 }
155 v
156 }
157
158 macro_rules! test_roots {
159 ($I:ident, $U:ident) => {
160 mod $I {
161 use crate::check;
162 use crate::neg;
163 use crate::pos;
164 use num_integer::Roots;
165 use std::mem;
166
167 #[test]
168 #[should_panic]
169 fn zeroth_root() {
170 (123 as $I).nth_root(0);
171 }
172
173 #[test]
174 fn sqrt() {
175 check(&pos::<$I>(), 2);
176 }
177
178 #[test]
179 #[should_panic]
180 fn sqrt_neg() {
181 (-123 as $I).sqrt();
182 }
183
184 #[test]
185 fn cbrt() {
186 check(&pos::<$I>(), 3);
187 }
188
189 #[test]
190 fn cbrt_neg() {
191 check(&neg::<$I>(), 3);
192 }
193
194 #[test]
195 fn nth_root() {
196 let bits = 8 * mem::size_of::<$I>() as u32 - 1;
197 let pos = pos::<$I>();
198 for n in 4..bits {
199 check(&pos, n);
200 }
201 }
202
203 #[test]
204 fn nth_root_neg() {
205 let bits = 8 * mem::size_of::<$I>() as u32 - 1;
206 let neg = neg::<$I>();
207 for n in 2..bits / 2 {
208 check(&neg, 2 * n + 1);
209 }
210 }
211
212 #[test]
213 fn bit_size() {
214 let bits = 8 * mem::size_of::<$I>() as u32 - 1;
215 assert_eq!($I::max_value().nth_root(bits - 1), 2);
216 assert_eq!($I::max_value().nth_root(bits), 1);
217 assert_eq!($I::min_value().nth_root(bits), -2);
218 assert_eq!(($I::min_value() + 1).nth_root(bits), -1);
219 }
220 }
221
222 mod $U {
223 use crate::check;
224 use crate::pos;
225 use num_integer::Roots;
226 use std::mem;
227
228 #[test]
229 #[should_panic]
230 fn zeroth_root() {
231 (123 as $U).nth_root(0);
232 }
233
234 #[test]
235 fn sqrt() {
236 check(&pos::<$U>(), 2);
237 }
238
239 #[test]
240 fn cbrt() {
241 check(&pos::<$U>(), 3);
242 }
243
244 #[test]
245 fn nth_root() {
246 let bits = 8 * mem::size_of::<$I>() as u32 - 1;
247 let pos = pos::<$I>();
248 for n in 4..bits {
249 check(&pos, n);
250 }
251 }
252
253 #[test]
254 fn bit_size() {
255 let bits = 8 * mem::size_of::<$U>() as u32;
256 assert_eq!($U::max_value().nth_root(bits - 1), 2);
257 assert_eq!($U::max_value().nth_root(bits), 1);
258 }
259 }
260 };
261 }
262
263 test_roots!(i8, u8);
264 test_roots!(i16, u16);
265 test_roots!(i32, u32);
266 test_roots!(i64, u64);
267 test_roots!(i128, u128);
268 test_roots!(isize, usize);