1 #![feature(test)]
2 #![cfg(feature = "rand")]
3 
4 extern crate test;
5 
6 use num_bigint::{BigUint, RandBigInt};
7 use test::Bencher;
8 
9 mod rng;
10 use rng::get_rng;
11 
12 // The `big64` cases demonstrate the speed of cases where the value
13 // can be converted to a `u64` primitive for faster calculation.
14 //
15 // The `big1k` cases demonstrate those that can convert to `f64` for
16 // a better initial guess of the actual value.
17 //
18 // The `big2k` and `big4k` cases are too big for `f64`, and use a simpler guess.
19 
check(x: &BigUint, n: u32)20 fn check(x: &BigUint, n: u32) {
21     let root = x.nth_root(n);
22     if n == 2 {
23         assert_eq!(root, x.sqrt())
24     } else if n == 3 {
25         assert_eq!(root, x.cbrt())
26     }
27 
28     let lo = root.pow(n);
29     assert!(lo <= *x);
30     assert_eq!(lo.nth_root(n), root);
31     assert_eq!((&lo - 1u32).nth_root(n), &root - 1u32);
32 
33     let hi = (&root + 1u32).pow(n);
34     assert!(hi > *x);
35     assert_eq!(hi.nth_root(n), &root + 1u32);
36     assert_eq!((&hi - 1u32).nth_root(n), root);
37 }
38 
bench_sqrt(b: &mut Bencher, bits: u64)39 fn bench_sqrt(b: &mut Bencher, bits: u64) {
40     let x = get_rng().gen_biguint(bits);
41     eprintln!("bench_sqrt({})", x);
42 
43     check(&x, 2);
44     b.iter(|| x.sqrt());
45 }
46 
47 #[bench]
big64_sqrt(b: &mut Bencher)48 fn big64_sqrt(b: &mut Bencher) {
49     bench_sqrt(b, 64);
50 }
51 
52 #[bench]
big1k_sqrt(b: &mut Bencher)53 fn big1k_sqrt(b: &mut Bencher) {
54     bench_sqrt(b, 1024);
55 }
56 
57 #[bench]
big2k_sqrt(b: &mut Bencher)58 fn big2k_sqrt(b: &mut Bencher) {
59     bench_sqrt(b, 2048);
60 }
61 
62 #[bench]
big4k_sqrt(b: &mut Bencher)63 fn big4k_sqrt(b: &mut Bencher) {
64     bench_sqrt(b, 4096);
65 }
66 
bench_cbrt(b: &mut Bencher, bits: u64)67 fn bench_cbrt(b: &mut Bencher, bits: u64) {
68     let x = get_rng().gen_biguint(bits);
69     eprintln!("bench_cbrt({})", x);
70 
71     check(&x, 3);
72     b.iter(|| x.cbrt());
73 }
74 
75 #[bench]
big64_cbrt(b: &mut Bencher)76 fn big64_cbrt(b: &mut Bencher) {
77     bench_cbrt(b, 64);
78 }
79 
80 #[bench]
big1k_cbrt(b: &mut Bencher)81 fn big1k_cbrt(b: &mut Bencher) {
82     bench_cbrt(b, 1024);
83 }
84 
85 #[bench]
big2k_cbrt(b: &mut Bencher)86 fn big2k_cbrt(b: &mut Bencher) {
87     bench_cbrt(b, 2048);
88 }
89 
90 #[bench]
big4k_cbrt(b: &mut Bencher)91 fn big4k_cbrt(b: &mut Bencher) {
92     bench_cbrt(b, 4096);
93 }
94 
bench_nth_root(b: &mut Bencher, bits: u64, n: u32)95 fn bench_nth_root(b: &mut Bencher, bits: u64, n: u32) {
96     let x = get_rng().gen_biguint(bits);
97     eprintln!("bench_{}th_root({})", n, x);
98 
99     check(&x, n);
100     b.iter(|| x.nth_root(n));
101 }
102 
103 #[bench]
big64_nth_10(b: &mut Bencher)104 fn big64_nth_10(b: &mut Bencher) {
105     bench_nth_root(b, 64, 10);
106 }
107 
108 #[bench]
big1k_nth_10(b: &mut Bencher)109 fn big1k_nth_10(b: &mut Bencher) {
110     bench_nth_root(b, 1024, 10);
111 }
112 
113 #[bench]
big1k_nth_100(b: &mut Bencher)114 fn big1k_nth_100(b: &mut Bencher) {
115     bench_nth_root(b, 1024, 100);
116 }
117 
118 #[bench]
big1k_nth_1000(b: &mut Bencher)119 fn big1k_nth_1000(b: &mut Bencher) {
120     bench_nth_root(b, 1024, 1000);
121 }
122 
123 #[bench]
big1k_nth_10000(b: &mut Bencher)124 fn big1k_nth_10000(b: &mut Bencher) {
125     bench_nth_root(b, 1024, 10000);
126 }
127 
128 #[bench]
big2k_nth_10(b: &mut Bencher)129 fn big2k_nth_10(b: &mut Bencher) {
130     bench_nth_root(b, 2048, 10);
131 }
132 
133 #[bench]
big2k_nth_100(b: &mut Bencher)134 fn big2k_nth_100(b: &mut Bencher) {
135     bench_nth_root(b, 2048, 100);
136 }
137 
138 #[bench]
big2k_nth_1000(b: &mut Bencher)139 fn big2k_nth_1000(b: &mut Bencher) {
140     bench_nth_root(b, 2048, 1000);
141 }
142 
143 #[bench]
big2k_nth_10000(b: &mut Bencher)144 fn big2k_nth_10000(b: &mut Bencher) {
145     bench_nth_root(b, 2048, 10000);
146 }
147 
148 #[bench]
big4k_nth_10(b: &mut Bencher)149 fn big4k_nth_10(b: &mut Bencher) {
150     bench_nth_root(b, 4096, 10);
151 }
152 
153 #[bench]
big4k_nth_100(b: &mut Bencher)154 fn big4k_nth_100(b: &mut Bencher) {
155     bench_nth_root(b, 4096, 100);
156 }
157 
158 #[bench]
big4k_nth_1000(b: &mut Bencher)159 fn big4k_nth_1000(b: &mut Bencher) {
160     bench_nth_root(b, 4096, 1000);
161 }
162 
163 #[bench]
big4k_nth_10000(b: &mut Bencher)164 fn big4k_nth_10000(b: &mut Bencher) {
165     bench_nth_root(b, 4096, 10000);
166 }
167