1 #![feature(test)]
2 #![cfg(feature = "rand")]
3
4 extern crate num_bigint;
5 extern crate num_integer;
6 extern crate num_traits;
7 extern crate rand;
8 extern crate test;
9
10 use num_bigint::{BigInt, BigUint, RandBigInt};
11 use num_traits::{FromPrimitive, Num, One, Pow, Zero};
12 use rand::{SeedableRng, StdRng};
13 use std::mem::replace;
14 use test::Bencher;
15
get_rng() -> StdRng16 fn get_rng() -> StdRng {
17 let mut seed = [0; 32];
18 for i in 1..32 {
19 seed[usize::from(i)] = i;
20 }
21 SeedableRng::from_seed(seed)
22 }
23
multiply_bench(b: &mut Bencher, xbits: usize, ybits: usize)24 fn multiply_bench(b: &mut Bencher, xbits: usize, ybits: usize) {
25 let mut rng = get_rng();
26 let x = rng.gen_bigint(xbits);
27 let y = rng.gen_bigint(ybits);
28
29 b.iter(|| &x * &y);
30 }
31
divide_bench(b: &mut Bencher, xbits: usize, ybits: usize)32 fn divide_bench(b: &mut Bencher, xbits: usize, ybits: usize) {
33 let mut rng = get_rng();
34 let x = rng.gen_bigint(xbits);
35 let y = rng.gen_bigint(ybits);
36
37 b.iter(|| &x / &y);
38 }
39
remainder_bench(b: &mut Bencher, xbits: usize, ybits: usize)40 fn remainder_bench(b: &mut Bencher, xbits: usize, ybits: usize) {
41 let mut rng = get_rng();
42 let x = rng.gen_bigint(xbits);
43 let y = rng.gen_bigint(ybits);
44
45 b.iter(|| &x % &y);
46 }
47
factorial(n: usize) -> BigUint48 fn factorial(n: usize) -> BigUint {
49 let mut f: BigUint = One::one();
50 for i in 1..(n + 1) {
51 let bu: BigUint = FromPrimitive::from_usize(i).unwrap();
52 f = f * bu;
53 }
54 f
55 }
56
57 /// Compute Fibonacci numbers
fib(n: usize) -> BigUint58 fn fib(n: usize) -> BigUint {
59 let mut f0: BigUint = Zero::zero();
60 let mut f1: BigUint = One::one();
61 for _ in 0..n {
62 let f2 = f0 + &f1;
63 f0 = replace(&mut f1, f2);
64 }
65 f0
66 }
67
68 /// Compute Fibonacci numbers with two ops per iteration
69 /// (add and subtract, like issue #200)
fib2(n: usize) -> BigUint70 fn fib2(n: usize) -> BigUint {
71 let mut f0: BigUint = Zero::zero();
72 let mut f1: BigUint = One::one();
73 for _ in 0..n {
74 f1 = f1 + &f0;
75 f0 = &f1 - f0;
76 }
77 f0
78 }
79
80 #[bench]
multiply_0(b: &mut Bencher)81 fn multiply_0(b: &mut Bencher) {
82 multiply_bench(b, 1 << 8, 1 << 8);
83 }
84
85 #[bench]
multiply_1(b: &mut Bencher)86 fn multiply_1(b: &mut Bencher) {
87 multiply_bench(b, 1 << 8, 1 << 16);
88 }
89
90 #[bench]
multiply_2(b: &mut Bencher)91 fn multiply_2(b: &mut Bencher) {
92 multiply_bench(b, 1 << 16, 1 << 16);
93 }
94
95 #[bench]
multiply_3(b: &mut Bencher)96 fn multiply_3(b: &mut Bencher) {
97 multiply_bench(b, 1 << 16, 1 << 17);
98 }
99
100 #[bench]
divide_0(b: &mut Bencher)101 fn divide_0(b: &mut Bencher) {
102 divide_bench(b, 1 << 8, 1 << 6);
103 }
104
105 #[bench]
divide_1(b: &mut Bencher)106 fn divide_1(b: &mut Bencher) {
107 divide_bench(b, 1 << 12, 1 << 8);
108 }
109
110 #[bench]
divide_2(b: &mut Bencher)111 fn divide_2(b: &mut Bencher) {
112 divide_bench(b, 1 << 16, 1 << 12);
113 }
114
115 #[bench]
remainder_0(b: &mut Bencher)116 fn remainder_0(b: &mut Bencher) {
117 remainder_bench(b, 1 << 8, 1 << 6);
118 }
119
120 #[bench]
remainder_1(b: &mut Bencher)121 fn remainder_1(b: &mut Bencher) {
122 remainder_bench(b, 1 << 12, 1 << 8);
123 }
124
125 #[bench]
remainder_2(b: &mut Bencher)126 fn remainder_2(b: &mut Bencher) {
127 remainder_bench(b, 1 << 16, 1 << 12);
128 }
129
130 #[bench]
factorial_100(b: &mut Bencher)131 fn factorial_100(b: &mut Bencher) {
132 b.iter(|| factorial(100));
133 }
134
135 #[bench]
fib_100(b: &mut Bencher)136 fn fib_100(b: &mut Bencher) {
137 b.iter(|| fib(100));
138 }
139
140 #[bench]
fib_1000(b: &mut Bencher)141 fn fib_1000(b: &mut Bencher) {
142 b.iter(|| fib(1000));
143 }
144
145 #[bench]
fib_10000(b: &mut Bencher)146 fn fib_10000(b: &mut Bencher) {
147 b.iter(|| fib(10000));
148 }
149
150 #[bench]
fib2_100(b: &mut Bencher)151 fn fib2_100(b: &mut Bencher) {
152 b.iter(|| fib2(100));
153 }
154
155 #[bench]
fib2_1000(b: &mut Bencher)156 fn fib2_1000(b: &mut Bencher) {
157 b.iter(|| fib2(1000));
158 }
159
160 #[bench]
fib2_10000(b: &mut Bencher)161 fn fib2_10000(b: &mut Bencher) {
162 b.iter(|| fib2(10000));
163 }
164
165 #[bench]
fac_to_string(b: &mut Bencher)166 fn fac_to_string(b: &mut Bencher) {
167 let fac = factorial(100);
168 b.iter(|| fac.to_string());
169 }
170
171 #[bench]
fib_to_string(b: &mut Bencher)172 fn fib_to_string(b: &mut Bencher) {
173 let fib = fib(100);
174 b.iter(|| fib.to_string());
175 }
176
to_str_radix_bench(b: &mut Bencher, radix: u32)177 fn to_str_radix_bench(b: &mut Bencher, radix: u32) {
178 let mut rng = get_rng();
179 let x = rng.gen_bigint(1009);
180 b.iter(|| x.to_str_radix(radix));
181 }
182
183 #[bench]
to_str_radix_02(b: &mut Bencher)184 fn to_str_radix_02(b: &mut Bencher) {
185 to_str_radix_bench(b, 2);
186 }
187
188 #[bench]
to_str_radix_08(b: &mut Bencher)189 fn to_str_radix_08(b: &mut Bencher) {
190 to_str_radix_bench(b, 8);
191 }
192
193 #[bench]
to_str_radix_10(b: &mut Bencher)194 fn to_str_radix_10(b: &mut Bencher) {
195 to_str_radix_bench(b, 10);
196 }
197
198 #[bench]
to_str_radix_16(b: &mut Bencher)199 fn to_str_radix_16(b: &mut Bencher) {
200 to_str_radix_bench(b, 16);
201 }
202
203 #[bench]
to_str_radix_36(b: &mut Bencher)204 fn to_str_radix_36(b: &mut Bencher) {
205 to_str_radix_bench(b, 36);
206 }
207
from_str_radix_bench(b: &mut Bencher, radix: u32)208 fn from_str_radix_bench(b: &mut Bencher, radix: u32) {
209 let mut rng = get_rng();
210 let x = rng.gen_bigint(1009);
211 let s = x.to_str_radix(radix);
212 assert_eq!(x, BigInt::from_str_radix(&s, radix).unwrap());
213 b.iter(|| BigInt::from_str_radix(&s, radix));
214 }
215
216 #[bench]
from_str_radix_02(b: &mut Bencher)217 fn from_str_radix_02(b: &mut Bencher) {
218 from_str_radix_bench(b, 2);
219 }
220
221 #[bench]
from_str_radix_08(b: &mut Bencher)222 fn from_str_radix_08(b: &mut Bencher) {
223 from_str_radix_bench(b, 8);
224 }
225
226 #[bench]
from_str_radix_10(b: &mut Bencher)227 fn from_str_radix_10(b: &mut Bencher) {
228 from_str_radix_bench(b, 10);
229 }
230
231 #[bench]
from_str_radix_16(b: &mut Bencher)232 fn from_str_radix_16(b: &mut Bencher) {
233 from_str_radix_bench(b, 16);
234 }
235
236 #[bench]
from_str_radix_36(b: &mut Bencher)237 fn from_str_radix_36(b: &mut Bencher) {
238 from_str_radix_bench(b, 36);
239 }
240
rand_bench(b: &mut Bencher, bits: usize)241 fn rand_bench(b: &mut Bencher, bits: usize) {
242 let mut rng = get_rng();
243
244 b.iter(|| rng.gen_bigint(bits));
245 }
246
247 #[bench]
rand_64(b: &mut Bencher)248 fn rand_64(b: &mut Bencher) {
249 rand_bench(b, 1 << 6);
250 }
251
252 #[bench]
rand_256(b: &mut Bencher)253 fn rand_256(b: &mut Bencher) {
254 rand_bench(b, 1 << 8);
255 }
256
257 #[bench]
rand_1009(b: &mut Bencher)258 fn rand_1009(b: &mut Bencher) {
259 rand_bench(b, 1009);
260 }
261
262 #[bench]
rand_2048(b: &mut Bencher)263 fn rand_2048(b: &mut Bencher) {
264 rand_bench(b, 1 << 11);
265 }
266
267 #[bench]
rand_4096(b: &mut Bencher)268 fn rand_4096(b: &mut Bencher) {
269 rand_bench(b, 1 << 12);
270 }
271
272 #[bench]
rand_8192(b: &mut Bencher)273 fn rand_8192(b: &mut Bencher) {
274 rand_bench(b, 1 << 13);
275 }
276
277 #[bench]
rand_65536(b: &mut Bencher)278 fn rand_65536(b: &mut Bencher) {
279 rand_bench(b, 1 << 16);
280 }
281
282 #[bench]
rand_131072(b: &mut Bencher)283 fn rand_131072(b: &mut Bencher) {
284 rand_bench(b, 1 << 17);
285 }
286
287 #[bench]
shl(b: &mut Bencher)288 fn shl(b: &mut Bencher) {
289 let n = BigUint::one() << 1000;
290 b.iter(|| {
291 let mut m = n.clone();
292 for i in 0..50 {
293 m = m << i;
294 }
295 })
296 }
297
298 #[bench]
shr(b: &mut Bencher)299 fn shr(b: &mut Bencher) {
300 let n = BigUint::one() << 2000;
301 b.iter(|| {
302 let mut m = n.clone();
303 for i in 0..50 {
304 m = m >> i;
305 }
306 })
307 }
308
309 #[bench]
hash(b: &mut Bencher)310 fn hash(b: &mut Bencher) {
311 use std::collections::HashSet;
312 let mut rng = get_rng();
313 let v: Vec<BigInt> = (1000..2000).map(|bits| rng.gen_bigint(bits)).collect();
314 b.iter(|| {
315 let h: HashSet<&BigInt> = v.iter().collect();
316 assert_eq!(h.len(), v.len());
317 });
318 }
319
320 #[bench]
pow_bench(b: &mut Bencher)321 fn pow_bench(b: &mut Bencher) {
322 b.iter(|| {
323 let upper = 100_usize;
324 for i in 2..upper + 1 {
325 for j in 2..upper + 1 {
326 let i_big = BigUint::from_usize(i).unwrap();
327 i_big.pow(j);
328 }
329 }
330 });
331 }
332
333 /// This modulus is the prime from the 2048-bit MODP DH group:
334 /// https://tools.ietf.org/html/rfc3526#section-3
335 const RFC3526_2048BIT_MODP_GROUP: &'static str =
336 "\
337 FFFFFFFF_FFFFFFFF_C90FDAA2_2168C234_C4C6628B_80DC1CD1\
338 29024E08_8A67CC74_020BBEA6_3B139B22_514A0879_8E3404DD\
339 EF9519B3_CD3A431B_302B0A6D_F25F1437_4FE1356D_6D51C245\
340 E485B576_625E7EC6_F44C42E9_A637ED6B_0BFF5CB6_F406B7ED\
341 EE386BFB_5A899FA5_AE9F2411_7C4B1FE6_49286651_ECE45B3D\
342 C2007CB8_A163BF05_98DA4836_1C55D39A_69163FA8_FD24CF5F\
343 83655D23_DCA3AD96_1C62F356_208552BB_9ED52907_7096966D\
344 670C354E_4ABC9804_F1746C08_CA18217C_32905E46_2E36CE3B\
345 E39E772C_180E8603_9B2783A2_EC07A28F_B5C55DF0_6F4C52C9\
346 DE2BCBF6_95581718_3995497C_EA956AE5_15D22618_98FA0510\
347 15728E5A_8AACAA68_FFFFFFFF_FFFFFFFF";
348
349 #[bench]
modpow(b: &mut Bencher)350 fn modpow(b: &mut Bencher) {
351 let mut rng = get_rng();
352 let base = rng.gen_biguint(2048);
353 let e = rng.gen_biguint(2048);
354 let m = BigUint::from_str_radix(RFC3526_2048BIT_MODP_GROUP, 16).unwrap();
355
356 b.iter(|| base.modpow(&e, &m));
357 }
358
359 #[bench]
modpow_even(b: &mut Bencher)360 fn modpow_even(b: &mut Bencher) {
361 let mut rng = get_rng();
362 let base = rng.gen_biguint(2048);
363 let e = rng.gen_biguint(2048);
364 // Make the modulus even, so monty (base-2^32) doesn't apply.
365 let m = BigUint::from_str_radix(RFC3526_2048BIT_MODP_GROUP, 16).unwrap() - 1u32;
366
367 b.iter(|| base.modpow(&e, &m));
368 }
369