mbutrovich commented on code in PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#discussion_r4314728091
##########
arrow-buffer/src/bigint/div.rs:
##########
@@ -300,3 +421,116 @@ impl<T, const N: usize> std::ops::DerefMut for
ArrayPlusOne<T, N> {
unsafe { std::slice::from_raw_parts_mut(x.cast::<T>(), N + 1) }
}
}
+
+#[cfg(test)]
+mod tests {
+ use super::*;
+ use rand::{RngExt, rng};
+
+ fn check_div_rem_small<const N: usize>(numerator: [u64; N], divisor: u64) {
+ let expected = div_rem_small_word(&numerator, divisor);
+ assert_eq!(
+ div_rem_small_reciprocal(&numerator, divisor),
+ expected,
+ "{numerator:?} / {divisor}"
+ );
+ }
+
+ #[test]
+ fn test_reciprocal_word() {
+ let mut divisors = vec![1 << 63, (1 << 63) + 1, u64::MAX - 1,
u64::MAX];
+ // Each boundary between entries of the lookup table
+ for i in 257..512u64 {
+ divisors.extend([(i << 55) - 1, i << 55, (i << 55) + 1]);
+ }
+ let mut rng = rng();
+ divisors.extend((0..100_000).map(|_| rng.random::<u64>() | (1 << 63)));
+ for divisor in divisors {
+ let n = (u128::from(!divisor) << 64) | u128::from(u64::MAX);
+ let expected = (n / u128::from(divisor)) as u64;
+ assert_eq!(reciprocal_word(divisor), expected, "{divisor}");
+ }
+ }
+
+ #[test]
+ fn test_div_rem_word_reciprocal() {
+ // The second correction, which random inputs rarely reach, runs for
this input
+ let (hi, lo, divisor) = (
+ 3787258589690185862,
+ 17800796494353475223,
+ 9357586864501027680,
Review Comment:
> What is special for those numbers?
Nothing, beyond the fact that they reach the second correction. I found them
by searching random inputs, and the comment didn't say so. I replaced them with
an input whose arithmetic can be checked by hand. The reciprocal of `2^63 + 2`
is `2^64 - 8`, so the estimate for `(2^127 + 2^64 - 1) / (2^63 + 2)` is `2^64 -
3`. The quotient is `2^64 - 2`, so the estimate is one too small and the second
correction adds it back. The test also asserts the reciprocal value.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
