Debian Codegraph @

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

raw
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 }