1 mod biguint { 2 use num_bigint::BigUint; 3 use num_traits::{One, Zero}; 4 check<T: Into<BigUint>>(x: T, n: u32)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] test_sqrt()30 fn test_sqrt() { 31 check(99u32, 2); 32 check(100u32, 2); 33 check(120u32, 2); 34 } 35 36 #[test] test_cbrt()37 fn test_cbrt() { 38 check(8u32, 3); 39 check(26u32, 3); 40 } 41 42 #[test] test_nth_root()43 fn test_nth_root() { 44 check(0u32, 1); 45 check(10u32, 1); 46 check(100u32, 4); 47 } 48 49 #[test] 50 #[should_panic] test_nth_root_n_is_zero()51 fn test_nth_root_n_is_zero() { 52 check(4u32, 0); 53 } 54 55 #[test] test_nth_root_big()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] test_nth_root_googol()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] test_nth_root_twos()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] test_roots_rand1()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 check(x: i64, n: u32)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] test_nth_root()138 fn test_nth_root() { 139 check(-100, 3); 140 } 141 142 #[test] 143 #[should_panic] test_nth_root_x_neg_n_even()144 fn test_nth_root_x_neg_n_even() { 145 check(-100, 4); 146 } 147 148 #[test] 149 #[should_panic] test_sqrt_x_neg()150 fn test_sqrt_x_neg() { 151 check(-4, 2); 152 } 153 154 #[test] test_cbrt()155 fn test_cbrt() { 156 check(8, 3); 157 check(-8, 3); 158 } 159 } 160