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