Debian Codegraph @

.cargo/vendor/strength_reduce/src/long_division.rs

raw
1 extern crate core;
2
3 const U32_MAX: u64 = core::u32::MAX as u64;
4 const U64_MAX: u128 = core::u64::MAX as u128;
5
6 use ::StrengthReducedU64;
7 use ::long_multiplication;
8
9 // divides a 128-bit number by a 64-bit divisor, returning the quotient as a 64-bit number
10 // assumes that the divisor and numerator have both already been bit-shifted so that divisor.leading_zeros() == 0
11 #[inline]
12 fn divide_128_by_64_preshifted(numerator_hi: u64, numerator_lo: u64, divisor: u64) -> u64 {
13 let numerator_mid = (numerator_lo >> 32) as u128;
14 let numerator_lo = numerator_lo as u32 as u128;
15 let divisor_full_128 = divisor as u128;
16 let divisor_hi = divisor >> 32;
17
18 // To get the upper 32 bits of the quotient, we want to divide 'full_upper_numerator' by 'divisor'
19 // but the problem is, full_upper_numerator is a 96-bit number, meaning we would need to use u128 to do the division all at once, and the whole point of this is that we don't want to do 128 bit divison because it's slow
20 // so instead, we'll shift both the numerator and divisor right by 32, giving us a 64 bit / 32 bit division. This won't give us the exact quotient -- but it will be close.
21 let full_upper_numerator = ((numerator_hi as u128) << 32) | numerator_mid;
22 let mut quotient_hi = core::cmp::min(numerator_hi / divisor_hi, U32_MAX);
23 let mut product_hi = quotient_hi as u128 * divisor_full_128;
24
25 // quotient_hi contains our guess at what the quotient is! the problem is that we got this by ignoring the lower 32 bits of the divisor. when we account for that, the quotient might be slightly lower
26 // we will know our quotient is too high if quotient * divisor > numerator. if it is, decrement until it's in range
27 while product_hi > full_upper_numerator {
28 quotient_hi -= 1;
29 product_hi -= divisor_full_128;
30 }
31 let remainder_hi = full_upper_numerator - product_hi;
32
33
34 // repeat the process using the lower half of the numerator
35 let full_lower_numerator = (remainder_hi << 32) | numerator_lo;
36 let mut quotient_lo = core::cmp::min((remainder_hi as u64) / divisor_hi, U32_MAX);
37 let mut product_lo = quotient_lo as u128 * divisor_full_128;
38
39 // again, quotient_lo is just a guess at this point, it might be slightly too large
40 while product_lo > full_lower_numerator {
41 quotient_lo -= 1;
42 product_lo -= divisor_full_128;
43 }
44
45 // We now have our separate quotients, now we just have to add them together
46 (quotient_hi << 32) | quotient_lo
47 }
48
49 // divides a 128-bit number by a 64-bit divisor, returning the quotient as a 64-bit number
50 // assumes that the divisor and numerator have both already been bit-shifted to maximize the number of bits in divisor_hi
51 // divisor_hi should be the upper 32 bits, and divisor_lo should be the lower 32 bits
52 #[inline]
53 fn divide_128_by_64_preshifted_reduced(numerator_hi: u64, numerator_lo: u64, divisor_hi: StrengthReducedU64, divisor_full: u64) -> u64 {
54 let numerator_mid = (numerator_lo >> 32) as u128;
55 let numerator_lo = numerator_lo as u32 as u128;
56 let divisor_full_128 = divisor_full as u128;
57
58 // To get the upper 32 bits of the quotient, we want to divide 'full_upper_numerator' by 'divisor'
59 // but the problem is, full_upper_numerator is a 96-bit number, meaning we would need to use u128 to do the division all at once, and the whole point of this is that we don't want to do 128 bit divison because it's slow
60 // so instead, we'll shift both the numerator and divisor right by 32, giving us a 64 bit / 32 bit division. This won't give us the exact quotient -- but it will be close.
61 let full_upper_numerator = ((numerator_hi as u128) << 32) | numerator_mid;
62 let mut quotient_hi = core::cmp::min(numerator_hi / divisor_hi, U32_MAX);
63 let mut product_hi = quotient_hi as u128 * divisor_full_128;
64
65 // quotient_hi contains our guess at what the quotient is! the problem is that we got this by ignoring the lower 32 bits of the divisor. when we account for that, the quotient might be slightly lower
66 // we will know our quotient is too high if quotient * divisor > numerator. if it is, decrement until it's in range
67 while product_hi > full_upper_numerator {
68 quotient_hi -= 1;
69 product_hi -= divisor_full_128;
70 }
71 let full_upper_remainder = full_upper_numerator - product_hi;
72
73
74 // repeat the process using the lower half of the numerator
75 let full_lower_numerator = (full_upper_remainder << 32) | numerator_lo;
76 let mut quotient_lo = core::cmp::min((full_upper_remainder as u64) / divisor_hi, U32_MAX);
77 let mut product_lo = quotient_lo as u128 * divisor_full_128;
78
79 // again, quotient_lo is just a guess at this point, it might be slightly too large
80 while product_lo > full_lower_numerator {
81 quotient_lo -= 1;
82 product_lo -= divisor_full_128;
83 }
84
85 // We now have our separate quotients, now we just have to add them together
86 (quotient_hi << 32) | quotient_lo
87 }
88
89 // divides a 128-bit number by a 128-bit divisor
90 pub fn divide_128(numerator: u128, divisor: u128) -> u128 {
91 if divisor <= U64_MAX {
92 let divisor64 = divisor as u64;
93 let upper_numerator = (numerator >> 64) as u64;
94 if divisor64 > upper_numerator {
95 divide_128_by_64_helper(numerator, divisor64) as u128
96 }
97 else {
98 let upper_quotient = upper_numerator / divisor64;
99 let upper_remainder = upper_numerator - upper_quotient * divisor64;
100
101 let intermediate_numerator = ((upper_remainder as u128) << 64) | (numerator as u64 as u128);
102 let lower_quotient = divide_128_by_64_helper(intermediate_numerator, divisor64);
103
104 ((upper_quotient as u128) << 64) | (lower_quotient as u128)
105 }
106 }
107 else {
108 let shift_size = divisor.leading_zeros();
109 let shifted_divisor = divisor << shift_size;
110
111 let shifted_numerator = numerator >> 1;
112
113 let upper_quotient = divide_128_by_64_helper(shifted_numerator, (shifted_divisor >> 64) as u64);
114 let mut quotient = upper_quotient >> (63 - shift_size);
115 if quotient > 0 {
116 quotient -= 1;
117 }
118
119 let remainder = numerator - quotient as u128 * divisor;
120 if remainder >= divisor {
121 quotient += 1;
122 }
123 quotient as u128
124 }
125 }
126
127 // divides a 128-bit number by a 64-bit divisor, returning the quotient as a 64-bit number. Panics if the quotient doesn't fit in a 64-bit number
128 fn divide_128_by_64_helper(numerator: u128, divisor: u64) -> u64 {
129 // Assert that the upper half of the numerator is less than the denominator. This will guarantee that the quotient fits inside the numerator.
130 // Sadly this will give us some false negatives! TODO: Find a quick test we can do that doesn't have false negatives
131 // false negative example: numerator = u64::MAX * u64::MAX / u64::MAX
132 assert!(divisor > (numerator >> 64) as u64, "The numerator is too large for the denominator; the quotient might not fit inside a u64.");
133
134 if divisor <= U32_MAX {
135 return divide_128_by_32_helper(numerator, divisor as u32);
136 }
137
138 let shift_size = divisor.leading_zeros();
139 let shifted_divisor = divisor << shift_size;
140 let shifted_numerator = numerator << shift_size;
141 let divisor_hi = shifted_divisor >> 32;
142 let divisor_lo = shifted_divisor as u32 as u64;
143
144 // split the numerator into 3 chunks: the top 64-bits, the next 32-bits, and the lowest 32-bits
145 let numerator_hi : u64 = (shifted_numerator >> 64) as u64;
146 let numerator_mid : u64 = (shifted_numerator >> 32) as u32 as u64;
147 let numerator_lo : u64 = shifted_numerator as u32 as u64;
148
149 // we're essentially going to do a long division algorithm with 2 divisions, one on numerator_hi << 32 | numerator_mid, and the second on the remainder of the first | numerator_lo
150 // but numerator_hi << 32 | numerator_mid is a 96-bit number, and we only have 64 bits to work with. so instead we split the divisor into 2 chunks, and divde by the upper chunk, and then check against the lower chunk in a while loop
151
152 // step 1: divide the top chunk of the numerator by the divisor
153 // IDEALLY, we would divide (numerator_hi << 32) | numerator_mid by shifted_divisor, but that would require a 128-bit numerator, which is the whole thing we're trying to avoid
154 // so instead we're going to split the second division into two sub-phases. in 1a, we divide numerator_hi by divisor_hi, and then in 1b we decrement the quotient to account for the fact that it'll be smaller when you take divisor_lo into account
155
156 // keep in mind that for all of step 2, the full numerator we're using will be
157 // complete_first_numerator = (numerator_midbits << 32) | numerator_mid
158
159 // step 1a: divide the upper part of the middle numerator by the upper part of the divisor
160 let mut quotient_hi = core::cmp::min(numerator_hi / divisor_hi, U32_MAX);
161 let mut partial_remainder_hi = numerator_hi - quotient_hi * divisor_hi;
162
163 // step 1b: we know sort of what the quotient is, but it's slightly too large because it doesn't account for divisor_lo, nor numerator_mid, so decrement the quotient until it fits
164 // note that if we do some algebra on the condition in this while loop,
165 // ie "quotient_hi * divisor_lo > (partial_remainder_hi << 32) | numerator_mid"
166 // we end up getting "quotient_hi * shifted_divisor < (numerator_midbits << 32) | numerator_mid". remember that the right side of the inequality sign is complete_first_numerator from above.
167 // which deminstrates that we're decrementing the quotient until the quotient multipled by the complete divisor is less than the complete numerator
168 while partial_remainder_hi <= U32_MAX && quotient_hi * divisor_lo > (partial_remainder_hi << 32) | numerator_mid {
169 quotient_hi -= 1;
170 partial_remainder_hi += divisor_hi;
171 }
172
173 // step 2: Divide the bottom part of the numerator. We're going to have the same problem as step 1, where we want the numerator to be a 96-bit number, so again we're going to split it into 2 substeps
174 // the full numeratoe for step 3 will be:
175 // complete_second_numerator = (first_division_remainder << 32) | numerator_lo
176
177 // step 2a: divide the upper part of the lower numerator by the upper part of the divisor
178 // To get the numerator, complate the calculation of the full remainder by subtracing the quotient times the lower bits of the divisor
179 // TODO: a warpping subtract is necessary here. why does this work, and why is it necessary?
180 let full_remainder_hi = ((partial_remainder_hi << 32) | numerator_mid).wrapping_sub(quotient_hi * divisor_lo);
181
182 let mut quotient_lo = core::cmp::min(full_remainder_hi / divisor_hi, U32_MAX);
183 let mut partial_remainder_lo = full_remainder_hi - quotient_lo * divisor_hi;
184
185 // step 2b: just like step 1b, decrement the final quotient until it's correctr when accounting for the full divisor
186 while partial_remainder_lo <= U32_MAX && quotient_lo * divisor_lo > (partial_remainder_lo << 32) | numerator_lo {
187 quotient_lo -= 1;
188 partial_remainder_lo += divisor_hi;
189 }
190
191 // We now have our separate quotients, now we just have to add them together
192 (quotient_hi << 32) | quotient_lo
193 }
194
195
196 // Same as divide_128_by_64_into_64, but optimized for scenarios where the divisor fits in a u32. Still panics if the quotient doesn't fit in a u64
197 fn divide_128_by_32_helper(numerator: u128, divisor: u32) -> u64 {
198 // Assert that the upper half of the numerator is less than the denominator. This will guarantee that the quotient fits inside the numerator.
199 // Sadly this will give us some false negatives! TODO: Find a quick test we can do that doesn't have false negatives
200 // false negative example: numerator = u64::MAX * u64::MAX / u64::MAX
201 assert!(divisor as u64 > (numerator >> 64) as u64, "The numerator is too large for the denominator; the quotient might not fit inside a u64.");
202
203 let shift_size = divisor.leading_zeros();
204 let shifted_divisor = (divisor << shift_size) as u64;
205 let shifted_numerator = numerator << (shift_size + 32);
206
207 // split the numerator into 3 chunks: the top 64-bits, the next 32-bits, and the lowest 32-bits
208 let numerator_hi : u64 = (shifted_numerator >> 64) as u64;
209 let numerator_mid : u64 = (shifted_numerator >> 32) as u32 as u64;
210
211 // we're essentially going to do a long division algorithm with 2 divisions, one on numerator_hi << 32 | numerator_mid, and the second on the remainder of the first | numerator_lo
212 // but numerator_hi << 32 | numerator_mid is a 96-bit number, and we only have 64 bits to work with. so instead we split the divisor into 2 chunks, and divde by the upper chunk, and then check against the lower chunk in a while loop
213
214 // step 1: divide the top chunk of the numerator by the divisor
215 // IDEALLY, we would divide (numerator_hi << 32) | numerator_mid by shifted_divisor, but that would require a 128-bit numerator, which is the whole thing we're trying to avoid
216 // so instead we're going to split the second division into two sub-phases. in 1a, we divide numerator_hi by divisor_hi, and then in 1b we decrement the quotient to account for the fact that it'll be smaller when you take divisor_lo into account
217
218 // keep in mind that for all of step 1, the full numerator we're using will be
219 // complete_first_numerator = (numerator_hi << 32) | numerator_mid
220
221 // step 1a: divide the upper part of the middle numerator by the upper part of the divisor
222 let quotient_hi = numerator_hi / shifted_divisor;
223 let remainder_hi = numerator_hi - quotient_hi * shifted_divisor;
224
225 // step 2: Divide the bottom part of the numerator. We're going to have the same problem as step 1, where we want the numerator to be a 96-bit number, so again we're going to split it into 2 substeps
226 // the full numeratoe for step 3 will be:
227 // complete_second_numerator = (first_division_remainder << 32) | numerator_lo
228
229 // step 2a: divide the upper part of the lower numerator by the upper part of the divisor
230 // To get the numerator, complate the calculation of the full remainder by subtracing the quotient times the lower bits of the divisor
231 // TODO: a warpping subtract is necessary here. why does this work, and why is it necessary?
232 let final_numerator = (remainder_hi) << 32 | numerator_mid;
233 let quotient_lo = final_numerator / shifted_divisor;
234
235 // We now have our separate quotients, now we just have to add them together
236 (quotient_hi << 32) | quotient_lo
237 }
238
239 #[inline(never)]
240 fn long_division(numerator_slice: &[u64], reduced_divisor: &StrengthReducedU64, quotient: &mut [u64]) {
241 let mut remainder = 0;
242 for (numerator_element, quotient_element) in numerator_slice.iter().zip(quotient.iter_mut()).rev() {
243 if remainder > 0 {
244 // Do one division that includes the running remainder and the upper half of this numerator element,
245 // then a second division for the first division's remainder combinedwith the lower half
246 let upper_numerator = (remainder << 32) | (*numerator_element >> 32);
247 let (upper_quotient, upper_remainder) = StrengthReducedU64::div_rem(upper_numerator, *reduced_divisor);
248
249 let lower_numerator = (upper_remainder << 32) | (*numerator_element as u32 as u64);
250 let (lower_quotient, lower_remainder) = StrengthReducedU64::div_rem(lower_numerator, *reduced_divisor);
251
252 *quotient_element = (upper_quotient << 32) | lower_quotient;
253 remainder = lower_remainder;
254 } else {
255 // The remainder is zero, which means we can take a shortcut and only do a single division!
256 let (digit_quotient, digit_remainder) = StrengthReducedU64::div_rem(*numerator_element, *reduced_divisor);
257
258 *quotient_element = digit_quotient;
259 remainder = digit_remainder;
260 }
261 }
262 }
263
264 #[inline]
265 fn normalize_slice(input: &mut [u64]) -> &mut [u64] {
266 let input_len = input.len();
267 let trailing_zero_chunks = input.iter().rev().take_while(|e| **e == 0).count();
268 &mut input[..input_len - trailing_zero_chunks]
269 }
270
271 #[inline]
272 fn is_slice_greater(a: &[u64], b: &[u64]) -> bool {
273 if a.len() > b.len() {
274 return true;
275 }
276 if b.len() > a.len() {
277 return false;
278 }
279
280 for (&ai, &bi) in a.iter().zip(b.iter()).rev() {
281 if ai < bi {
282 return false;
283 }
284 if ai > bi {
285 return true;
286 }
287 }
288 false
289 }
290 // subtract b from a, and store the result in a
291 #[inline]
292 fn sub_assign(a: &mut [u64], b: &[u64]) {
293 let mut borrow: i128 = 0;
294
295 // subtract b from a, keeping track of borrows as we go
296 let (a_lo, a_hi) = a.split_at_mut(b.len());
297
298 for (a, b) in a_lo.iter_mut().zip(b) {
299 borrow += *a as i128;
300 borrow -= *b as i128;
301 *a = borrow as u64;
302 borrow >>= 64;
303 }
304
305 // We're done subtracting, we just need to finish carrying
306 let mut a_element = a_hi.iter_mut();
307 while borrow != 0 {
308 let a_element = a_element.next().expect("borrow underflow during sub_assign");
309 borrow += *a_element as i128;
310
311 *a_element = borrow as u64;
312 borrow >>= 64;
313 }
314 }
315
316 pub(crate) fn divide_128_max_by_64(divisor: u64) -> u128 {
317 let quotient_hi = core::u64::MAX / divisor;
318 let remainder_hi = core::u64::MAX - quotient_hi * divisor;
319
320 let leading_zeros = divisor.leading_zeros();
321 let quotient_lo = if leading_zeros >= 32 {
322 let numerator_mid = (remainder_hi << 32) | core::u32::MAX as u64;
323 let quotient_mid = numerator_mid / divisor;
324 let remainder_mid = numerator_mid - quotient_mid * divisor;
325
326 let numerator_lo = (remainder_mid << 32) | core::u32::MAX as u64;
327 let quotient_lo = numerator_lo / divisor;
328
329 (quotient_mid << 32) | quotient_lo
330 }
331 else {
332 let numerator_hi = if leading_zeros > 0 { (remainder_hi << leading_zeros) | (core::u64::MAX >> (64 - leading_zeros)) } else { remainder_hi };
333 let numerator_lo = core::u64::MAX << leading_zeros;
334
335 divide_128_by_64_preshifted(numerator_hi, numerator_lo, divisor << leading_zeros)
336 };
337 ((quotient_hi as u128) << 64) | (quotient_lo as u128)
338 }
339
340 fn divide_256_max_by_32(divisor: u32) -> (u128, u128) {
341 let reduced_divisor = StrengthReducedU64::new(divisor as u64);
342 let mut numerator_chunks = [core::u64::MAX; 4];
343 let mut quotient_chunks = [0; 4];
344 long_division(&mut numerator_chunks, &reduced_divisor, &mut quotient_chunks);
345
346 // quotient_chunks now contains the quotient! all we have to do is recombine it into u128s
347 let quotient_lo = (quotient_chunks[0] as u128) | ((quotient_chunks[1] as u128) << 64);
348 let quotient_hi = (quotient_chunks[2] as u128) | ((quotient_chunks[3] as u128) << 64);
349
350 (quotient_hi, quotient_lo)
351 }
352
353 pub(crate) fn divide_256_max_by_128(divisor: u128) -> (u128, u128) {
354 let leading_zeros = divisor.leading_zeros();
355
356 // if the divisor fits inside a u32, we can use a much faster algorithm
357 if leading_zeros >= 96 {
358 return divide_256_max_by_32(divisor as u32);
359 }
360
361 let empty_divisor_chunks = (leading_zeros / 64) as usize;
362 let shift_amount = leading_zeros % 64;
363
364 // Shift the divisor and chunk it up into U32s
365 let divisor_shifted = divisor << shift_amount;
366 let divisor_chunks = [
367 divisor_shifted as u64,
368 (divisor_shifted >> 64) as u64,
369 ];
370 let divisor_slice = &divisor_chunks[..(divisor_chunks.len() - empty_divisor_chunks)];
371
372 // We're gonna be doing a ton of u64/u64 divisions, so we're gonna eat our own dog food and set up a strength-reduced division instance
373 // the only actual **divisions* we'll be doing will be with the largest 32 bits of the full divisor, not the full divisor
374 let reduced_divisor_hi = StrengthReducedU64::new(*divisor_slice.last().unwrap() >> 32);
375 let divisor_hi = *divisor_slice.last().unwrap();
376
377 // Build our numerator, represented by u32 chunks. at first it will be full of u32::MAX, but we will iteratively take chunks out of it as we divide
378 let mut numerator_chunks = [core::u64::MAX; 5];
379 let mut numerator_max_idx = if shift_amount > 0 {
380 numerator_chunks[4] >>= 64 - shift_amount;
381 numerator_chunks[0] <<= shift_amount;
382 5
383 }
384 else {
385 4
386 };
387
388 // allocate the biggest-possible quotient, even if it might be smaller -- we just won't fill out the biggest parts
389 let num_quotient_chunks = 3 + empty_divisor_chunks;
390 let mut quotient_chunks = [0; 4];
391 for quotient_idx in (0..num_quotient_chunks).rev() {
392 /*
393 * When calculating our next guess q0, we don't need to consider the digits below j
394 * + b.data.len() - 1: we're guessing digit j of the quotient (i.e. q0 << j) from
395 * digit bn of the divisor (i.e. bn << (b.data.len() - 1) - so the product of those
396 * two numbers will be zero in all digits up to (j + b.data.len() - 1).
397 */
398
399 let numerator_slice = &mut numerator_chunks[..numerator_max_idx];
400 let numerator_start_idx = quotient_idx + divisor_slice.len() - 1;
401 if numerator_start_idx >= numerator_slice.len() {
402 continue;
403 }
404
405
406 // scope for borrow checker
407 {
408 // divide the uppermost bits of the remaining numerator to get "sub_quotient" which will be our guess for this quotient element
409 let numerator_hi = if numerator_slice.len() - numerator_start_idx > 1 { numerator_slice[numerator_start_idx + 1] } else { 0 };
410 let numerator_lo = numerator_slice[numerator_start_idx];
411 let mut sub_quotient = divide_128_by_64_preshifted_reduced(numerator_hi, numerator_lo, reduced_divisor_hi, divisor_hi);
412
413 let mut tmp_product = [0; 3];
414 long_multiplication::long_multiply(&divisor_slice, sub_quotient, &mut tmp_product);
415 let sub_product = normalize_slice(&mut tmp_product);
416
417 // our sub_quotient is just a guess at the quotient -- it only accounts for the topmost bits of the divisor. when we take the bottom bits of the divisor into account, the actual quotient will be smaller
418 // we will know if our guess is too large if (quotient_guess * full_divisor) (aka sub_product) is greater than this iteration's numerator slice. ifthat's the case, decrement it until it's less than or equal.
419 while is_slice_greater(sub_product, &numerator_slice[quotient_idx..]) {
420 sub_assign(sub_product, &divisor_slice);
421 sub_quotient -= 1;
422 }
423
424 // sub_quotient is now the correct sub-quotient for this iteration. add it to the full quotient, and subtract the product from the full numerator, so that what remains in the numerator is the remainder of this division
425 quotient_chunks[quotient_idx] = sub_quotient;
426 sub_assign(&mut numerator_slice[quotient_idx..], sub_product);
427 }
428
429
430 // slice off any zeroes at the end of the numerator. we're not calling normalize_slice here because of borrow checker obnoxiousness
431 numerator_max_idx -= numerator_slice.iter().rev().take_while(|e| **e == 0).count();
432 }
433
434
435 // quotient_chunks now contains the quotient! all we have to do is recombine it into u128s
436 let quotient_lo = (quotient_chunks[0] as u128)
437 | ((quotient_chunks[1] as u128) << 64);
438 let quotient_hi = (quotient_chunks[2] as u128)
439 | ((quotient_chunks[3] as u128) << 64);
440
441 (quotient_hi, quotient_lo)
442 }
443
444
445
446 #[cfg(test)]
447 mod unit_tests {
448 use num_bigint::BigUint;
449
450 #[test]
451 fn test_divide_128_by_64() {
452 for divisor in core::u64::MAX..=core::u64::MAX {
453 let divisor_128 = core::u64::MAX as u128;
454
455 let numerator = divisor_128 * divisor_128 + (divisor_128 - 1);
456 //for numerator in core::u128::MAX - 10..core::u128::MAX {
457 let expected_quotient = numerator / divisor as u128;
458 assert!(expected_quotient == core::u64::MAX as u128);
459
460 let actual_quotient = super::divide_128_by_64_helper(numerator as u128, divisor);
461
462
463
464 let expected_upper = (expected_quotient >> 32) as u64;
465 let expected_lower = expected_quotient as u32 as u64;
466 let actual_upper = (actual_quotient >> 32) as u64;
467 let actual_lower = actual_quotient as u32 as u64;
468
469 assert_eq!(expected_upper, actual_upper, "wrong quotient for {}/{}", numerator, divisor);
470 assert_eq!(expected_lower, actual_lower, "wrong quotient for {}/{}", numerator, divisor);
471 //}
472 }
473 }
474
475 fn test_divisor_128(divisor: u128) {
476 let big_numerator = BigUint::from_slice(&[core::u32::MAX; 8]);
477 let big_quotient = big_numerator / divisor;
478
479 //let (actual_hi, actual_lo) = super::divide_256_max_by_128_direct(divisor);
480 let (actual64_hi, actual64_lo) = super::divide_256_max_by_128(divisor);
481
482 //let actual_big = (BigUint::from(actual_hi) << 128) | BigUint::from(actual_lo);
483 let actual64_big = (BigUint::from(actual64_hi) << 128) | BigUint::from(actual64_lo);
484
485 //assert_eq!(big_quotient, actual_big, "Actual quotient didn't match expected quotient for max/{}", divisor);
486 assert_eq!(big_quotient, actual64_big, "Actual64 quotient didn't match expected quotient for max/{}", divisor);
487 }
488
489 #[allow(unused_imports)]
490 use rand::{rngs::StdRng, SeedableRng, distributions::Distribution, distributions::Uniform};
491
492 #[test]
493 fn test_max_256() {
494 let log2_tests_per_bit = 6;
495
496 for divisor in 1..(1 << log2_tests_per_bit) {
497 test_divisor_128(divisor);
498 }
499
500 let mut gen = StdRng::seed_from_u64(5673573);
501 for bits in log2_tests_per_bit..128 {
502 let lower_start = 1 << bits;
503 let lower_stop = lower_start + (1 << (log2_tests_per_bit - 3));
504 let upper_stop = 1u128.checked_shl(bits + 1).map_or(core::u128::MAX, |v| v - 1);
505 let upper_start = upper_stop - (1 << (log2_tests_per_bit - 3)) + 1;
506
507 for divisor in lower_start..lower_stop {
508 test_divisor_128(divisor);
509 }
510 for divisor in upper_start..=upper_stop {
511 test_divisor_128(divisor);
512 }
513
514 let random_count = 1 << log2_tests_per_bit;
515 let dist = Uniform::new(lower_stop + 1, upper_start);
516 for _ in 0..random_count {
517 let divisor = dist.sample(&mut gen);
518 test_divisor_128(divisor);
519 }
520 }
521 }
522 }