Debian Codegraph @

.cargo/vendor/num-bigint/benches/bigint.rs

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