aboutsummaryrefslogtreecommitdiff
path: root/vendor/num-integer/benches/gcd.rs
diff options
context:
space:
mode:
authorValentin Popov <valentin@popov.link>2024-07-19 15:37:58 +0300
committerValentin Popov <valentin@popov.link>2024-07-19 15:37:58 +0300
commita990de90fe41456a23e58bd087d2f107d321f3a1 (patch)
tree15afc392522a9e85dc3332235e311b7d39352ea9 /vendor/num-integer/benches/gcd.rs
parent3d48cd3f81164bbfc1a755dc1d4a9a02f98c8ddd (diff)
downloadfparkan-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.rs176
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);