Yiming Jing | cf21fc4 | 2021-07-16 13:23:26 -0700 | [diff] [blame] | 1 | #![feature(test)] |
| 2 | #![cfg(feature = "rand")] |
| 3 | |
| 4 | extern crate test; |
| 5 | |
| 6 | use num_bigint::{BigUint, RandBigInt}; |
| 7 | use test::Bencher; |
| 8 | |
| 9 | mod rng; |
| 10 | use rng::get_rng; |
| 11 | |
| 12 | // The `big64` cases demonstrate the speed of cases where the value |
| 13 | // can be converted to a `u64` primitive for faster calculation. |
| 14 | // |
| 15 | // The `big1k` cases demonstrate those that can convert to `f64` for |
| 16 | // a better initial guess of the actual value. |
| 17 | // |
| 18 | // The `big2k` and `big4k` cases are too big for `f64`, and use a simpler guess. |
| 19 | |
| 20 | fn check(x: &BigUint, n: u32) { |
| 21 | let root = x.nth_root(n); |
| 22 | if n == 2 { |
| 23 | assert_eq!(root, x.sqrt()) |
| 24 | } else if n == 3 { |
| 25 | assert_eq!(root, x.cbrt()) |
| 26 | } |
| 27 | |
| 28 | let lo = root.pow(n); |
| 29 | assert!(lo <= *x); |
| 30 | assert_eq!(lo.nth_root(n), root); |
| 31 | assert_eq!((&lo - 1u32).nth_root(n), &root - 1u32); |
| 32 | |
| 33 | let hi = (&root + 1u32).pow(n); |
| 34 | assert!(hi > *x); |
| 35 | assert_eq!(hi.nth_root(n), &root + 1u32); |
| 36 | assert_eq!((&hi - 1u32).nth_root(n), root); |
| 37 | } |
| 38 | |
| 39 | fn bench_sqrt(b: &mut Bencher, bits: u64) { |
| 40 | let x = get_rng().gen_biguint(bits); |
| 41 | eprintln!("bench_sqrt({})", x); |
| 42 | |
| 43 | check(&x, 2); |
| 44 | b.iter(|| x.sqrt()); |
| 45 | } |
| 46 | |
| 47 | #[bench] |
| 48 | fn big64_sqrt(b: &mut Bencher) { |
| 49 | bench_sqrt(b, 64); |
| 50 | } |
| 51 | |
| 52 | #[bench] |
| 53 | fn big1k_sqrt(b: &mut Bencher) { |
| 54 | bench_sqrt(b, 1024); |
| 55 | } |
| 56 | |
| 57 | #[bench] |
| 58 | fn big2k_sqrt(b: &mut Bencher) { |
| 59 | bench_sqrt(b, 2048); |
| 60 | } |
| 61 | |
| 62 | #[bench] |
| 63 | fn big4k_sqrt(b: &mut Bencher) { |
| 64 | bench_sqrt(b, 4096); |
| 65 | } |
| 66 | |
| 67 | fn bench_cbrt(b: &mut Bencher, bits: u64) { |
| 68 | let x = get_rng().gen_biguint(bits); |
| 69 | eprintln!("bench_cbrt({})", x); |
| 70 | |
| 71 | check(&x, 3); |
| 72 | b.iter(|| x.cbrt()); |
| 73 | } |
| 74 | |
| 75 | #[bench] |
| 76 | fn big64_cbrt(b: &mut Bencher) { |
| 77 | bench_cbrt(b, 64); |
| 78 | } |
| 79 | |
| 80 | #[bench] |
| 81 | fn big1k_cbrt(b: &mut Bencher) { |
| 82 | bench_cbrt(b, 1024); |
| 83 | } |
| 84 | |
| 85 | #[bench] |
| 86 | fn big2k_cbrt(b: &mut Bencher) { |
| 87 | bench_cbrt(b, 2048); |
| 88 | } |
| 89 | |
| 90 | #[bench] |
| 91 | fn big4k_cbrt(b: &mut Bencher) { |
| 92 | bench_cbrt(b, 4096); |
| 93 | } |
| 94 | |
| 95 | fn bench_nth_root(b: &mut Bencher, bits: u64, n: u32) { |
| 96 | let x = get_rng().gen_biguint(bits); |
| 97 | eprintln!("bench_{}th_root({})", n, x); |
| 98 | |
| 99 | check(&x, n); |
| 100 | b.iter(|| x.nth_root(n)); |
| 101 | } |
| 102 | |
| 103 | #[bench] |
| 104 | fn big64_nth_10(b: &mut Bencher) { |
| 105 | bench_nth_root(b, 64, 10); |
| 106 | } |
| 107 | |
| 108 | #[bench] |
| 109 | fn big1k_nth_10(b: &mut Bencher) { |
| 110 | bench_nth_root(b, 1024, 10); |
| 111 | } |
| 112 | |
| 113 | #[bench] |
| 114 | fn big1k_nth_100(b: &mut Bencher) { |
| 115 | bench_nth_root(b, 1024, 100); |
| 116 | } |
| 117 | |
| 118 | #[bench] |
| 119 | fn big1k_nth_1000(b: &mut Bencher) { |
| 120 | bench_nth_root(b, 1024, 1000); |
| 121 | } |
| 122 | |
| 123 | #[bench] |
| 124 | fn big1k_nth_10000(b: &mut Bencher) { |
| 125 | bench_nth_root(b, 1024, 10000); |
| 126 | } |
| 127 | |
| 128 | #[bench] |
| 129 | fn big2k_nth_10(b: &mut Bencher) { |
| 130 | bench_nth_root(b, 2048, 10); |
| 131 | } |
| 132 | |
| 133 | #[bench] |
| 134 | fn big2k_nth_100(b: &mut Bencher) { |
| 135 | bench_nth_root(b, 2048, 100); |
| 136 | } |
| 137 | |
| 138 | #[bench] |
| 139 | fn big2k_nth_1000(b: &mut Bencher) { |
| 140 | bench_nth_root(b, 2048, 1000); |
| 141 | } |
| 142 | |
| 143 | #[bench] |
| 144 | fn big2k_nth_10000(b: &mut Bencher) { |
| 145 | bench_nth_root(b, 2048, 10000); |
| 146 | } |
| 147 | |
| 148 | #[bench] |
| 149 | fn big4k_nth_10(b: &mut Bencher) { |
| 150 | bench_nth_root(b, 4096, 10); |
| 151 | } |
| 152 | |
| 153 | #[bench] |
| 154 | fn big4k_nth_100(b: &mut Bencher) { |
| 155 | bench_nth_root(b, 4096, 100); |
| 156 | } |
| 157 | |
| 158 | #[bench] |
| 159 | fn big4k_nth_1000(b: &mut Bencher) { |
| 160 | bench_nth_root(b, 4096, 1000); |
| 161 | } |
| 162 | |
| 163 | #[bench] |
| 164 | fn big4k_nth_10000(b: &mut Bencher) { |
| 165 | bench_nth_root(b, 4096, 10000); |
| 166 | } |