Debian Codegraph @

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

raw
1 //! Benchmark sqrt and cbrt
2
3 #![feature(test)]
4
5 extern crate test;
6
7 use num_integer::Integer;
8 use num_traits::checked_pow;
9 use num_traits::{AsPrimitive, PrimInt, WrappingAdd, WrappingMul};
10 use test::{black_box, Bencher};
11
12 trait BenchInteger: Integer + PrimInt + WrappingAdd + WrappingMul + 'static {}
13
14 impl<T> BenchInteger for T where T: Integer + PrimInt + WrappingAdd + WrappingMul + 'static {}
15
16 fn bench<T, F>(b: &mut Bencher, v: &[T], f: F, n: u32)
17 where
18 T: BenchInteger,
19 F: Fn(&T) -> T,
20 {
21 // Pre-validate the results...
22 for i in v {
23 let rt = f(i);
24 if *i >= T::zero() {
25 let rt1 = rt + T::one();
26 assert!(rt.pow(n) <= *i);
27 if let Some(x) = checked_pow(rt1, n as usize) {
28 assert!(*i < x);
29 }
30 } else {
31 let rt1 = rt - T::one();
32 assert!(rt < T::zero());
33 assert!(*i <= rt.pow(n));
34 if let Some(x) = checked_pow(rt1, n as usize) {
35 assert!(x < *i);
36 }
37 };
38 }
39
40 // Now just run as fast as we can!
41 b.iter(|| {
42 for i in v {
43 black_box(f(i));
44 }
45 });
46 }
47
48 // Simple PRNG so we don't have to worry about rand compatibility
49 fn lcg<T>(x: T) -> T
50 where
51 u32: AsPrimitive<T>,
52 T: BenchInteger,
53 {
54 // LCG parameters from Numerical Recipes
55 // (but we're applying it to arbitrary sizes)
56 const LCG_A: u32 = 1664525;
57 const LCG_C: u32 = 1013904223;
58 x.wrapping_mul(&LCG_A.as_()).wrapping_add(&LCG_C.as_())
59 }
60
61 fn bench_rand<T, F>(b: &mut Bencher, f: F, n: u32)
62 where
63 u32: AsPrimitive<T>,
64 T: BenchInteger,
65 F: Fn(&T) -> T,
66 {
67 let mut x: T = 3u32.as_();
68 let v: Vec<T> = (0..1000)
69 .map(|_| {
70 x = lcg(x);
71 x
72 })
73 .collect();
74 bench(b, &v, f, n);
75 }
76
77 fn bench_rand_pos<T, F>(b: &mut Bencher, f: F, n: u32)
78 where
79 u32: AsPrimitive<T>,
80 T: BenchInteger,
81 F: Fn(&T) -> T,
82 {
83 let mut x: T = 3u32.as_();
84 let v: Vec<T> = (0..1000)
85 .map(|_| {
86 x = lcg(x);
87 while x < T::zero() {
88 x = lcg(x);
89 }
90 x
91 })
92 .collect();
93 bench(b, &v, f, n);
94 }
95
96 fn bench_small<T, F>(b: &mut Bencher, f: F, n: u32)
97 where
98 u32: AsPrimitive<T>,
99 T: BenchInteger,
100 F: Fn(&T) -> T,
101 {
102 let v: Vec<T> = (0..1000).map(|i| i.as_()).collect();
103 bench(b, &v, f, n);
104 }
105
106 fn bench_small_pos<T, F>(b: &mut Bencher, f: F, n: u32)
107 where
108 u32: AsPrimitive<T>,
109 T: BenchInteger,
110 F: Fn(&T) -> T,
111 {
112 let v: Vec<T> = (0..1000)
113 .map(|i| i.as_().mod_floor(&T::max_value()))
114 .collect();
115 bench(b, &v, f, n);
116 }
117
118 macro_rules! bench_roots {
119 ($($T:ident),*) => {$(
120 mod $T {
121 use test::Bencher;
122 use num_integer::Roots;
123
124 #[bench]
125 fn sqrt_rand(b: &mut Bencher) {
126 crate::bench_rand_pos(b, $T::sqrt, 2);
127 }
128
129 #[bench]
130 fn sqrt_small(b: &mut Bencher) {
131 crate::bench_small_pos(b, $T::sqrt, 2);
132 }
133
134 #[bench]
135 fn cbrt_rand(b: &mut Bencher) {
136 crate::bench_rand(b, $T::cbrt, 3);
137 }
138
139 #[bench]
140 fn cbrt_small(b: &mut Bencher) {
141 crate::bench_small(b, $T::cbrt, 3);
142 }
143
144 #[bench]
145 fn fourth_root_rand(b: &mut Bencher) {
146 crate::bench_rand_pos(b, |x: &$T| x.nth_root(4), 4);
147 }
148
149 #[bench]
150 fn fourth_root_small(b: &mut Bencher) {
151 crate::bench_small_pos(b, |x: &$T| x.nth_root(4), 4);
152 }
153
154 #[bench]
155 fn fifth_root_rand(b: &mut Bencher) {
156 crate::bench_rand(b, |x: &$T| x.nth_root(5), 5);
157 }
158
159 #[bench]
160 fn fifth_root_small(b: &mut Bencher) {
161 crate::bench_small(b, |x: &$T| x.nth_root(5), 5);
162 }
163 }
164 )*}
165 }
166
167 bench_roots!(i8, i16, i32, i64, i128);
168 bench_roots!(u8, u16, u32, u64, u128);