1 #![feature(test)]
2 #![cfg(feature = "rand")]
3
4 extern crate test;
5
6 use num_bigint::{BigUint, RandBigInt};
7 use num_integer::Integer;
8 use num_traits::Zero;
9 use test::Bencher;
10
11 mod rng;
12 use rng::get_rng;
13
bench(b: &mut Bencher, bits: u64, gcd: fn(&BigUint, &BigUint) -> BigUint)14 fn bench(b: &mut Bencher, bits: u64, gcd: fn(&BigUint, &BigUint) -> BigUint) {
15 let mut rng = get_rng();
16 let x = rng.gen_biguint(bits);
17 let y = rng.gen_biguint(bits);
18
19 assert_eq!(euclid(&x, &y), x.gcd(&y));
20
21 b.iter(|| gcd(&x, &y));
22 }
23
euclid(x: &BigUint, y: &BigUint) -> BigUint24 fn euclid(x: &BigUint, y: &BigUint) -> BigUint {
25 // Use Euclid's algorithm
26 let mut m = x.clone();
27 let mut n = y.clone();
28 while !m.is_zero() {
29 let temp = m;
30 m = n % &temp;
31 n = temp;
32 }
33 n
34 }
35
36 #[bench]
gcd_euclid_0064(b: &mut Bencher)37 fn gcd_euclid_0064(b: &mut Bencher) {
38 bench(b, 64, euclid);
39 }
40
41 #[bench]
gcd_euclid_0256(b: &mut Bencher)42 fn gcd_euclid_0256(b: &mut Bencher) {
43 bench(b, 256, euclid);
44 }
45
46 #[bench]
gcd_euclid_1024(b: &mut Bencher)47 fn gcd_euclid_1024(b: &mut Bencher) {
48 bench(b, 1024, euclid);
49 }
50
51 #[bench]
gcd_euclid_4096(b: &mut Bencher)52 fn gcd_euclid_4096(b: &mut Bencher) {
53 bench(b, 4096, euclid);
54 }
55
56 // Integer for BigUint now uses Stein for gcd
57
58 #[bench]
gcd_stein_0064(b: &mut Bencher)59 fn gcd_stein_0064(b: &mut Bencher) {
60 bench(b, 64, BigUint::gcd);
61 }
62
63 #[bench]
gcd_stein_0256(b: &mut Bencher)64 fn gcd_stein_0256(b: &mut Bencher) {
65 bench(b, 256, BigUint::gcd);
66 }
67
68 #[bench]
gcd_stein_1024(b: &mut Bencher)69 fn gcd_stein_1024(b: &mut Bencher) {
70 bench(b, 1024, BigUint::gcd);
71 }
72
73 #[bench]
gcd_stein_4096(b: &mut Bencher)74 fn gcd_stein_4096(b: &mut Bencher) {
75 bench(b, 4096, BigUint::gcd);
76 }
77