rluvaton commented on code in PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#discussion_r4306960527
##########
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,
+ );
+ let n = (u128::from(hi) << 64) | u128::from(lo);
+ let d = u128::from(divisor);
+ assert_eq!(
+ div_rem_word_reciprocal(hi, lo, divisor, reciprocal_word(divisor)),
+ ((n / d) as u64, (n % d) as u64)
+ );
+
+ let mut rng = rng();
+ let mut divisors = vec![1 << 63, (1 << 63) + 1, u64::MAX - 1,
u64::MAX];
+ divisors.extend((0..100).map(|_| rng.random::<u64>() | (1 << 63)));
+ for divisor in divisors {
+ let reciprocal = reciprocal_word(divisor);
+ let mut his = vec![0, 1, divisor / 2, divisor - 1];
+ his.extend((0..20).map(|_| rng.random_range(0..divisor)));
+ for hi in his {
+ let mut los = vec![0, 1, divisor - 1, divisor, u64::MAX];
+ los.extend((0..20).map(|_| rng.random::<u64>()));
+ for lo in los {
+ let n = (u128::from(hi) << 64) | u128::from(lo);
+ let d = u128::from(divisor);
+ let expected = ((n / d) as u64, (n % d) as u64);
+ assert_eq!(
+ div_rem_word_reciprocal(hi, lo, divisor, reciprocal),
+ expected,
+ "{n} / {divisor}"
+ );
+ }
+ }
+ }
+ }
+
+ #[test]
+ fn test_div_rem_small_reciprocal() {
+ let mut rng = rng();
+ let numerators = [
+ [0; 4],
+ [1, 0, 0, 0],
+ [0, 0, 0, 1],
+ [u64::MAX; 4],
+ [0, 0, 0, u64::MAX],
+ [u64::MAX, 0, 0, 0],
+ rng.random(),
+ ];
+ // Every normalization shift, with divisors at and next to each power
of two
+ for shift in 0..64 {
+ let p = 1u64 << shift;
+ let mut divisors = vec![p, p.wrapping_mul(2).wrapping_sub(1)];
+ divisors.extend(p.checked_add(1));
+ divisors.extend(p.checked_sub(1).filter(|d| *d != 0));
+ for divisor in divisors {
+ for numerator in numerators {
+ check_div_rem_small(numerator, divisor);
+ check_div_rem_small([numerator[0], numerator[1]], divisor);
+ check_div_rem_small([numerator[0]], divisor);
+ }
+ }
+ }
+ // Powers of ten, as used when rescaling decimals
+ for k in 0..=19 {
+ let p = 10u64.pow(k);
+ for divisor in [p - 1, p, p + 1].into_iter().filter(|d| *d != 0) {
+ for numerator in numerators {
+ check_div_rem_small(numerator, divisor);
+ }
+ }
+ }
+ for _ in 0..1000 {
+ let divisor = rng.random::<u64>() >> rng.random_range(0..64);
Review Comment:
can you make it seeded rng to be deterministic
--
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]
