| 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 |
} |