| 1 |
mod biguint { |
| 2 |
use num_bigint::BigUint; |
| 3 |
use num_traits::{One, Zero}; |
| 4 |
|
| 5 |
fn check<T: Into<BigUint>>(x: T, n: u32) { |
| 6 |
let x: BigUint = x.into(); |
| 7 |
let root = x.nth_root(n); |
| 8 |
println!("check {}.nth_root({}) = {}", x, n, root); |
| 9 |
|
| 10 |
if n == 2 { |
| 11 |
assert_eq!(root, x.sqrt()) |
| 12 |
} else if n == 3 { |
| 13 |
assert_eq!(root, x.cbrt()) |
| 14 |
} |
| 15 |
|
| 16 |
let lo = root.pow(n); |
| 17 |
assert!(lo <= x); |
| 18 |
assert_eq!(lo.nth_root(n), root); |
| 19 |
if !lo.is_zero() { |
| 20 |
assert_eq!((&lo - 1u32).nth_root(n), &root - 1u32); |
| 21 |
} |
| 22 |
|
| 23 |
let hi = (&root + 1u32).pow(n); |
| 24 |
assert!(hi > x); |
| 25 |
assert_eq!(hi.nth_root(n), &root + 1u32); |
| 26 |
assert_eq!((&hi - 1u32).nth_root(n), root); |
| 27 |
} |
| 28 |
|
| 29 |
#[test] |
| 30 |
fn test_sqrt() { |
| 31 |
check(99u32, 2); |
| 32 |
check(100u32, 2); |
| 33 |
check(120u32, 2); |
| 34 |
} |
| 35 |
|
| 36 |
#[test] |
| 37 |
fn test_cbrt() { |
| 38 |
check(8u32, 3); |
| 39 |
check(26u32, 3); |
| 40 |
} |
| 41 |
|
| 42 |
#[test] |
| 43 |
fn test_nth_root() { |
| 44 |
check(0u32, 1); |
| 45 |
check(10u32, 1); |
| 46 |
check(100u32, 4); |
| 47 |
} |
| 48 |
|
| 49 |
#[test] |
| 50 |
#[should_panic] |
| 51 |
fn test_nth_root_n_is_zero() { |
| 52 |
check(4u32, 0); |
| 53 |
} |
| 54 |
|
| 55 |
#[test] |
| 56 |
fn test_nth_root_big() { |
| 57 |
let x = BigUint::from(123_456_789_u32); |
| 58 |
let expected = BigUint::from(6u32); |
| 59 |
|
| 60 |
assert_eq!(x.nth_root(10), expected); |
| 61 |
check(x, 10); |
| 62 |
} |
| 63 |
|
| 64 |
#[test] |
| 65 |
fn test_nth_root_googol() { |
| 66 |
let googol = BigUint::from(10u32).pow(100u32); |
| 67 |
|
| 68 |
// perfect divisors of 100 |
| 69 |
for &n in &[2, 4, 5, 10, 20, 25, 50, 100] { |
| 70 |
let expected = BigUint::from(10u32).pow(100u32 / n); |
| 71 |
assert_eq!(googol.nth_root(n), expected); |
| 72 |
check(googol.clone(), n); |
| 73 |
} |
| 74 |
} |
| 75 |
|
| 76 |
#[test] |
| 77 |
fn test_nth_root_twos() { |
| 78 |
const EXP: u32 = 12; |
| 79 |
const LOG2: usize = 1 << EXP; |
| 80 |
let x = BigUint::one() << LOG2; |
| 81 |
|
| 82 |
// the perfect divisors are just powers of two |
| 83 |
for exp in 1..=EXP { |
| 84 |
let n = 2u32.pow(exp); |
| 85 |
let expected = BigUint::one() << (LOG2 / n as usize); |
| 86 |
assert_eq!(x.nth_root(n), expected); |
| 87 |
check(x.clone(), n); |
| 88 |
} |
| 89 |
|
| 90 |
// degenerate cases should return quickly |
| 91 |
assert!(x.nth_root(x.bits() as u32).is_one()); |
| 92 |
assert!(x.nth_root(i32::MAX as u32).is_one()); |
| 93 |
assert!(x.nth_root(u32::MAX).is_one()); |
| 94 |
} |
| 95 |
|
| 96 |
#[test] |
| 97 |
fn test_roots_rand1() { |
| 98 |
// A random input that found regressions |
| 99 |
let s = "575981506858479247661989091587544744717244516135539456183849\ |
| 100 |
986593934723426343633698413178771587697273822147578889823552\ |
| 101 |
182702908597782734558103025298880194023243541613924361007059\ |
| 102 |
353344183590348785832467726433749431093350684849462759540710\ |
| 103 |
026019022227591412417064179299354183441181373862905039254106\ |
| 104 |
4781867"; |
| 105 |
let x: BigUint = s.parse().unwrap(); |
| 106 |
|
| 107 |
check(x.clone(), 2); |
| 108 |
check(x.clone(), 3); |
| 109 |
check(x.clone(), 10); |
| 110 |
check(x, 100); |
| 111 |
} |
| 112 |
} |
| 113 |
|
| 114 |
mod bigint { |
| 115 |
use num_bigint::BigInt; |
| 116 |
use num_traits::Signed; |
| 117 |
|
| 118 |
fn check(x: i64, n: u32) { |
| 119 |
let big_x = BigInt::from(x); |
| 120 |
let res = big_x.nth_root(n); |
| 121 |
|
| 122 |
if n == 2 { |
| 123 |
assert_eq!(&res, &big_x.sqrt()) |
| 124 |
} else if n == 3 { |
| 125 |
assert_eq!(&res, &big_x.cbrt()) |
| 126 |
} |
| 127 |
|
| 128 |
if big_x.is_negative() { |
| 129 |
assert!(res.pow(n) >= big_x); |
| 130 |
assert!((res - 1u32).pow(n) < big_x); |
| 131 |
} else { |
| 132 |
assert!(res.pow(n) <= big_x); |
| 133 |
assert!((res + 1u32).pow(n) > big_x); |
| 134 |
} |
| 135 |
} |
| 136 |
|
| 137 |
#[test] |
| 138 |
fn test_nth_root() { |
| 139 |
check(-100, 3); |
| 140 |
} |
| 141 |
|
| 142 |
#[test] |
| 143 |
#[should_panic] |
| 144 |
fn test_nth_root_x_neg_n_even() { |
| 145 |
check(-100, 4); |
| 146 |
} |
| 147 |
|
| 148 |
#[test] |
| 149 |
#[should_panic] |
| 150 |
fn test_sqrt_x_neg() { |
| 151 |
check(-4, 2); |
| 152 |
} |
| 153 |
|
| 154 |
#[test] |
| 155 |
fn test_cbrt() { |
| 156 |
check(8, 3); |
| 157 |
check(-8, 3); |
| 158 |
} |
| 159 |
} |