diff options
author | Valentin Popov <valentin@popov.link> | 2024-07-19 15:37:58 +0300 |
---|---|---|
committer | Valentin Popov <valentin@popov.link> | 2024-07-19 15:37:58 +0300 |
commit | a990de90fe41456a23e58bd087d2f107d321f3a1 (patch) | |
tree | 15afc392522a9e85dc3332235e311b7d39352ea9 /vendor/num-integer/benches/gcd.rs | |
parent | 3d48cd3f81164bbfc1a755dc1d4a9a02f98c8ddd (diff) | |
download | fparkan-a990de90fe41456a23e58bd087d2f107d321f3a1.tar.xz fparkan-a990de90fe41456a23e58bd087d2f107d321f3a1.zip |
Deleted vendor folder
Diffstat (limited to 'vendor/num-integer/benches/gcd.rs')
-rw-r--r-- | vendor/num-integer/benches/gcd.rs | 176 |
1 files changed, 0 insertions, 176 deletions
diff --git a/vendor/num-integer/benches/gcd.rs b/vendor/num-integer/benches/gcd.rs deleted file mode 100644 index 082d5ee..0000000 --- a/vendor/num-integer/benches/gcd.rs +++ /dev/null @@ -1,176 +0,0 @@ -//! Benchmark comparing the current GCD implemtation against an older one. - -#![feature(test)] - -extern crate num_integer; -extern crate num_traits; -extern crate test; - -use num_integer::Integer; -use num_traits::{AsPrimitive, Bounded, Signed}; -use test::{black_box, Bencher}; - -trait GcdOld: Integer { - fn gcd_old(&self, other: &Self) -> Self; -} - -macro_rules! impl_gcd_old_for_isize { - ($T:ty) => { - impl GcdOld for $T { - /// Calculates the Greatest Common Divisor (GCD) of the number and - /// `other`. The result is always positive. - #[inline] - fn gcd_old(&self, other: &Self) -> Self { - // Use Stein's algorithm - let mut m = *self; - let mut n = *other; - if m == 0 || n == 0 { - return (m | n).abs(); - } - - // find common factors of 2 - let shift = (m | n).trailing_zeros(); - - // The algorithm needs positive numbers, but the minimum value - // can't be represented as a positive one. - // It's also a power of two, so the gcd can be - // calculated by bitshifting in that case - - // Assuming two's complement, the number created by the shift - // is positive for all numbers except gcd = abs(min value) - // The call to .abs() causes a panic in debug mode - if m == Self::min_value() || n == Self::min_value() { - return (1 << shift).abs(); - } - - // guaranteed to be positive now, rest like unsigned algorithm - m = m.abs(); - n = n.abs(); - - // divide n and m by 2 until odd - // m inside loop - n >>= n.trailing_zeros(); - - while m != 0 { - m >>= m.trailing_zeros(); - if n > m { - std::mem::swap(&mut n, &mut m) - } - m -= n; - } - - n << shift - } - } - }; -} - -impl_gcd_old_for_isize!(i8); -impl_gcd_old_for_isize!(i16); -impl_gcd_old_for_isize!(i32); -impl_gcd_old_for_isize!(i64); -impl_gcd_old_for_isize!(isize); -impl_gcd_old_for_isize!(i128); - -macro_rules! impl_gcd_old_for_usize { - ($T:ty) => { - impl GcdOld for $T { - /// Calculates the Greatest Common Divisor (GCD) of the number and - /// `other`. The result is always positive. - #[inline] - fn gcd_old(&self, other: &Self) -> Self { - // Use Stein's algorithm - let mut m = *self; - let mut n = *other; - if m == 0 || n == 0 { - return m | n; - } - - // find common factors of 2 - let shift = (m | n).trailing_zeros(); - - // divide n and m by 2 until odd - // m inside loop - n >>= n.trailing_zeros(); - - while m != 0 { - m >>= m.trailing_zeros(); - if n > m { - std::mem::swap(&mut n, &mut m) - } - m -= n; - } - - n << shift - } - } - }; -} - -impl_gcd_old_for_usize!(u8); -impl_gcd_old_for_usize!(u16); -impl_gcd_old_for_usize!(u32); -impl_gcd_old_for_usize!(u64); -impl_gcd_old_for_usize!(usize); -impl_gcd_old_for_usize!(u128); - -/// Return an iterator that yields all Fibonacci numbers fitting into a u128. -fn fibonacci() -> impl Iterator<Item = u128> { - (0..185).scan((0, 1), |&mut (ref mut a, ref mut b), _| { - let tmp = *a; - *a = *b; - *b += tmp; - Some(*b) - }) -} - -fn run_bench<T: Integer + Bounded + Copy + 'static>(b: &mut Bencher, gcd: fn(&T, &T) -> T) -where - T: AsPrimitive<u128>, - u128: AsPrimitive<T>, -{ - let max_value: u128 = T::max_value().as_(); - let pairs: Vec<(T, T)> = fibonacci() - .collect::<Vec<_>>() - .windows(2) - .filter(|&pair| pair[0] <= max_value && pair[1] <= max_value) - .map(|pair| (pair[0].as_(), pair[1].as_())) - .collect(); - b.iter(|| { - for &(ref m, ref n) in &pairs { - black_box(gcd(m, n)); - } - }); -} - -macro_rules! bench_gcd { - ($T:ident) => { - mod $T { - use crate::{run_bench, GcdOld}; - use num_integer::Integer; - use test::Bencher; - - #[bench] - fn bench_gcd(b: &mut Bencher) { - run_bench(b, $T::gcd); - } - - #[bench] - fn bench_gcd_old(b: &mut Bencher) { - run_bench(b, $T::gcd_old); - } - } - }; -} - -bench_gcd!(u8); -bench_gcd!(u16); -bench_gcd!(u32); -bench_gcd!(u64); -bench_gcd!(u128); - -bench_gcd!(i8); -bench_gcd!(i16); -bench_gcd!(i32); -bench_gcd!(i64); -bench_gcd!(i128); |