vendor/num-integer/benches/gcd.rs

   1 //! Benchmark comparing the current GCD implemtation against an older one.
   2
   3 #![feature(test)]
   4
   5 extern crate num_integer;
   6 extern crate num_traits;
   7 extern crate test;
   8
   9 use num_integer::Integer;
  10 use num_traits::{AsPrimitive, Bounded, Signed};
  11 use test::{black_box, Bencher};
  12
  13 trait GcdOld: Integer {
  14     fn gcd_old(&self, other: &Self) -> Self;
  15 }
  16
  17 macro_rules! impl_gcd_old_for_isize {
  18     ($T:ty) => {
  19         impl GcdOld for $T {
  20             /// Calculates the Greatest Common Divisor (GCD) of the number and
  21             /// `other`. The result is always positive.
  22             #[inline]
  23             fn gcd_old(&self, other: &Self) -> Self {
  24                 // Use Stein's algorithm
  25                 let mut m = *self;
  26                 let mut n = *other;
  27                 if m == 0 || n == 0 {
  28                     return (m | n).abs();
  29                 }
  30
  31                 // find common factors of 2
  32                 let shift = (m | n).trailing_zeros();
  33
  34                 // The algorithm needs positive numbers, but the minimum value
  35                 // can't be represented as a positive one.
  36                 // It's also a power of two, so the gcd can be
  37                 // calculated by bitshifting in that case
  38
  39                 // Assuming two's complement, the number created by the shift
  40                 // is positive for all numbers except gcd = abs(min value)
  41                 // The call to .abs() causes a panic in debug mode
  42                 if m == Self::min_value() || n == Self::min_value() {
  43                     return (1 << shift).abs();
  44                 }
  45
  46                 // guaranteed to be positive now, rest like unsigned algorithm
  47                 m = m.abs();
  48                 n = n.abs();
  49
  50                 // divide n and m by 2 until odd
  51                 // m inside loop
  52                 n >>= n.trailing_zeros();
  53
  54                 while m != 0 {
  55                     m >>= m.trailing_zeros();
  56                     if n > m {
  57                         std::mem::swap(&mut n, &mut m)
  58                     }
  59                     m -= n;
  60                 }
  61
  62                 n << shift
  63             }
  64         }
  65     };
  66 }
  67
  68 impl_gcd_old_for_isize!(i8);
  69 impl_gcd_old_for_isize!(i16);
  70 impl_gcd_old_for_isize!(i32);
  71 impl_gcd_old_for_isize!(i64);
  72 impl_gcd_old_for_isize!(isize);
  73 impl_gcd_old_for_isize!(i128);
  74
  75 macro_rules! impl_gcd_old_for_usize {
  76     ($T:ty) => {
  77         impl GcdOld for $T {
  78             /// Calculates the Greatest Common Divisor (GCD) of the number and
  79             /// `other`. The result is always positive.
  80             #[inline]
  81             fn gcd_old(&self, other: &Self) -> Self {
  82                 // Use Stein's algorithm
  83                 let mut m = *self;
  84                 let mut n = *other;
  85                 if m == 0 || n == 0 {
  86                     return m | n;
  87                 }
  88
  89                 // find common factors of 2
  90                 let shift = (m | n).trailing_zeros();
  91
  92                 // divide n and m by 2 until odd
  93                 // m inside loop
  94                 n >>= n.trailing_zeros();
  95
  96                 while m != 0 {
  97                     m >>= m.trailing_zeros();
  98                     if n > m {
  99                         std::mem::swap(&mut n, &mut m)
 100                     }
 101                     m -= n;
 102                 }
 103
 104                 n << shift
 105             }
 106         }
 107     };
 108 }
 109
 110 impl_gcd_old_for_usize!(u8);
 111 impl_gcd_old_for_usize!(u16);
 112 impl_gcd_old_for_usize!(u32);
 113 impl_gcd_old_for_usize!(u64);
 114 impl_gcd_old_for_usize!(usize);
 115 impl_gcd_old_for_usize!(u128);
 116
 117 /// Return an iterator that yields all Fibonacci numbers fitting into a u128.
 118 fn fibonacci() -> impl Iterator<Item = u128> {
 119     (0..185).scan((0, 1), |&mut (ref mut a, ref mut b), _| {
 120         let tmp = *a;
 121         *a = *b;
 122         *b += tmp;
 123         Some(*b)
 124     })
 125 }
 126
 127 fn run_bench<T: Integer + Bounded + Copy + 'static>(b: &mut Bencher, gcd: fn(&T, &T) -> T)
 128 where
 129     T: AsPrimitive<u128>,
 130     u128: AsPrimitive<T>,
 131 {
 132     let max_value: u128 = T::max_value().as_();
 133     let pairs: Vec<(T, T)> = fibonacci()
 134         .collect::<Vec<_>>()
 135         .windows(2)
 136         .filter(|&pair| pair[0] <= max_value && pair[1] <= max_value)
 137         .map(|pair| (pair[0].as_(), pair[1].as_()))
 138         .collect();
 139     b.iter(|| {
 140         for &(ref m, ref n) in &pairs {
 141             black_box(gcd(m, n));
 142         }
 143     });
 144 }
 145
 146 macro_rules! bench_gcd {
 147     ($T:ident) => {
 148         mod $T {
 149             use crate::{run_bench, GcdOld};
 150             use num_integer::Integer;
 151             use test::Bencher;
 152
 153             #[bench]
 154             fn bench_gcd(b: &mut Bencher) {
 155                 run_bench(b, $T::gcd);
 156             }
 157
 158             #[bench]
 159             fn bench_gcd_old(b: &mut Bencher) {
 160                 run_bench(b, $T::gcd_old);
 161             }
 162         }
 163     };
 164 }
 165
 166 bench_gcd!(u8);
 167 bench_gcd!(u16);
 168 bench_gcd!(u32);
 169 bench_gcd!(u64);
 170 bench_gcd!(u128);
 171
 172 bench_gcd!(i8);
 173 bench_gcd!(i16);
 174 bench_gcd!(i32);
 175 bench_gcd!(i64);
 176 bench_gcd!(i128);