Yiming Jing | cf21fc4 | 2021-07-16 13:23:26 -0700 | [diff] [blame] | 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 | |
| 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 | |
| 24 | 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] |
| 37 | fn gcd_euclid_0064(b: &mut Bencher) { |
| 38 | bench(b, 64, euclid); |
| 39 | } |
| 40 | |
| 41 | #[bench] |
| 42 | fn gcd_euclid_0256(b: &mut Bencher) { |
| 43 | bench(b, 256, euclid); |
| 44 | } |
| 45 | |
| 46 | #[bench] |
| 47 | fn gcd_euclid_1024(b: &mut Bencher) { |
| 48 | bench(b, 1024, euclid); |
| 49 | } |
| 50 | |
| 51 | #[bench] |
| 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] |
| 59 | fn gcd_stein_0064(b: &mut Bencher) { |
| 60 | bench(b, 64, BigUint::gcd); |
| 61 | } |
| 62 | |
| 63 | #[bench] |
| 64 | fn gcd_stein_0256(b: &mut Bencher) { |
| 65 | bench(b, 256, BigUint::gcd); |
| 66 | } |
| 67 | |
| 68 | #[bench] |
| 69 | fn gcd_stein_1024(b: &mut Bencher) { |
| 70 | bench(b, 1024, BigUint::gcd); |
| 71 | } |
| 72 | |
| 73 | #[bench] |
| 74 | fn gcd_stein_4096(b: &mut Bencher) { |
| 75 | bench(b, 4096, BigUint::gcd); |
| 76 | } |