| 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); |