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