mbutrovich commented on code in PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#discussion_r4314717593
##########
arrow-buffer/src/bigint/div.rs:
##########
@@ -72,6 +95,104 @@ fn div_rem_small<const N: usize>(numerator: &[u64; N],
divisor: u64) -> ([u64; N
(numerator, rem_padded)
}
+/// Like [`div_rem_small_word`], but divides each digit by multiplying with a
+/// reciprocal of the divisor, computed once
+#[cfg(any(
+ test,
+ all(target_pointer_width = "64", any(not(target_arch = "x86_64"), miri))
+))]
+fn div_rem_small_reciprocal<const N: usize>(
+ numerator: &[u64; N],
+ divisor: u64,
+) -> ([u64; N], [u64; N]) {
+ // Shifting both operands so the divisor's top bit is set leaves the
quotient unchanged
+ let shift = divisor.leading_zeros();
+ let divisor = divisor << shift;
+ let reciprocal = reciprocal_word(divisor);
+ let numerator = full_shl(numerator, shift);
+
+ // The top digit is below 2^shift, and so below the divisor
+ let mut rem = numerator[N];
+ let mut quotient = [0; N];
+ for i in (0..N).rev() {
+ let (q, r) = div_rem_word_reciprocal(rem, numerator[i], divisor,
reciprocal);
+ quotient[i] = q;
+ rem = r;
+ }
+
+ let mut rem_padded = [0; N];
+ rem_padded[0] = rem >> shift;
+ (quotient, rem_padded)
+}
+
+/// Returns `floor((2^128 - 1) / divisor) - 2^64` for a divisor with its top
bit set
+///
+/// This is algorithm 2 of [Möller and Granlund
(2011)](https://gmplib.org/~tege/division-paper.pdf),
Review Comment:
> Maybe add the paper name in the comment in case the link ever die
Added "Improved division by invariant integers" to both links.
https://github.com/apache/arrow-rs/pull/11580#discussion_r4306946278
--
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]
