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::{BigUint, RandBigInt};
11 use num_integer::Integer;
12 use num_traits::Zero;
13 use rand::{SeedableRng, StdRng};
14 use test::Bencher;
15 
16 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 
24 fn bench(b: &mut Bencher, bits: usize, gcd: fn(&BigUint, &BigUint) -> BigUint) {
25     let mut rng = get_rng();
26     let x = rng.gen_biguint(bits);
27     let y = rng.gen_biguint(bits);
28 
29     assert_eq!(euclid(&x, &y), x.gcd(&y));
30 
31     b.iter(|| gcd(&x, &y));
32 }
33 
34 fn euclid(x: &BigUint, y: &BigUint) -> BigUint {
35     // Use Euclid's algorithm
36     let mut m = x.clone();
37     let mut n = y.clone();
38     while !m.is_zero() {
39         let temp = m;
40         m = n % &temp;
41         n = temp;
42     }
43     return n;
44 }
45 
46 #[bench]
47 fn gcd_euclid_0064(b: &mut Bencher) {
48     bench(b, 64, euclid);
49 }
isSafeToSpeculatePHIUsers(PHINode & PN,DominatorTree & DT,SmallPtrSetImpl<Instruction * > & PotentialSpecSet,SmallPtrSetImpl<Instruction * > & UnsafeSet)50 
51 #[bench]
52 fn gcd_euclid_0256(b: &mut Bencher) {
53     bench(b, 256, euclid);
54 }
55 
56 #[bench]
57 fn gcd_euclid_1024(b: &mut Bencher) {
58     bench(b, 1024, euclid);
59 }
60 
61 #[bench]
62 fn gcd_euclid_4096(b: &mut Bencher) {
63     bench(b, 4096, euclid);
64 }
65 
66 // Integer for BigUint now uses Stein for gcd
67 
68 #[bench]
69 fn gcd_stein_0064(b: &mut Bencher) {
70     bench(b, 64, BigUint::gcd);
71 }
72 
73 #[bench]
74 fn gcd_stein_0256(b: &mut Bencher) {
75     bench(b, 256, BigUint::gcd);
76 }
77 
78 #[bench]
79 fn gcd_stein_1024(b: &mut Bencher) {
80     bench(b, 1024, BigUint::gcd);
81 }
82 
83 #[bench]
84 fn gcd_stein_4096(b: &mut Bencher) {
85     bench(b, 4096, BigUint::gcd);
86 }
87