Debian Codegraph @

.cargo/vendor/num-integer/benches/gcd.rs

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