This is an automated email from the ASF dual-hosted git repository.
Jefffrey pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/arrow-rs.git
The following commit(s) were added to refs/heads/main by this push:
new a381897ff0 arith: fallback to dividing decimals digitwise when regular
scale into div overflows (#10911)
a381897ff0 is described below
commit a381897ff0104bf126adb94ae81e413e40f207db
Author: Bharadwaj Pendyala <[email protected]>
AuthorDate: Wed Sep 2 01:02:24 2026 -0500
arith: fallback to dividing decimals digitwise when regular scale into div
overflows (#10911)
# Which issue does this PR close?
- Closes #7216.
# Rationale for this change
`Op::Div` scales the left operand before dividing: `result_scale = s1 +
4`, then `mul_pow = result_scale - s1 + s2`. For large operand scales,
`mul_pow` includes all of `s2`, so `l * 10^mul_pow` overflows even when
the quotient fits.
On `main` at 4962d38, the issue example is `Decimal256(38, 37) /
Decimal256(38, 37)` with `l = 60096743305738933273387748827369321010`,
`r = 60096763826458053191384497987259478584`, and `mul_pow = 41`. `l *
10^41 = 6.0e78`, above `i256::MAX = 5.8e76`, while the quotient is
`9.9999965853869970143724273117679321341339e40` at scale 41. Today this
reports `Arithmetic overflow: Overflow happened on:
60096743305738933273387748827369321010 *
100000000000000000000000000000000000000000`, despite 35 digits of result
headroom.
# What changes are included in this PR?
`scaled_div` computes `l * 10^mul_pow / r` digit by digit after
`mul_checked` overflows; the fast path is unchanged. It carries the
remainder forward without calculating `remainder * 10`, adding it ten
times and subtracting the divisor when needed. This also handles
divisors above `T::Native::MAX / 10`, where that multiply would
overflow. The calculation uses magnitudes and restores the sign,
preserving truncation toward zero for all four sign combinations.
# Are these changes tested?
Four tests in `arrow-arith/src/numeric.rs` cover the issue operands,
each negated in turn, and a zero divisor; a `Decimal256(76, 37)` divisor
of `6e75` above `i256::MAX / 10`; the same wide-intermediate case for
`Decimal128`; and `scaled_div` against `i128` `l * 10^mul_pow / r`
across both signs, a zero numerator, and operands near `i128::MAX / 10`.
I also checked 1000 random `Decimal256(76, 70)` pairs against Python
integer division: 661 now return exact values with no sign or truncation
disagreements. The remaining 339 have quotients that do not fit `i256`;
that harness is not in the diff. `cargo test -p arrow-arith` gives 239
passed / 0 failed, `cargo test -p arrow` is clean, and `cargo fmt --all
--check` and `cargo clippy -p arrow-arith --all-targets -- -D warnings`
are quiet.
# Are there any user-facing changes?
No API change. A zero divisor whose numerator would have overflowed now
reports `Divide by zero error` instead of the multiplication overflow,
because the zero check no longer sits behind scaling. Unrepresentable
divisions still error, but the message names the multiplication the
digit loop failed on rather than `l * 10^mul_pow`.
`T::Native::MIN` remains unsupported as either operand because taking
its magnitude overflows. No array with a valid precision can hold it:
`MIN` has more digits than `MAX_PRECISION` allows for every decimal
type.
---------
Co-authored-by: RIchard Baah <[email protected]>
---
arrow-arith/src/numeric.rs | 167 ++++++++++++++++++++++++++++++++++++++++++++-
1 file changed, 166 insertions(+), 1 deletion(-)
diff --git a/arrow-arith/src/numeric.rs b/arrow-arith/src/numeric.rs
index be6ae21ff5..f3a87a74d3 100644
--- a/arrow-arith/src/numeric.rs
+++ b/arrow-arith/src/numeric.rs
@@ -967,6 +967,58 @@ fn date_op<T: DateOp>(
}
}
+/// Divides `l * 10^mul_pow` by `r` a digit at a time, without forming the
scaled numerator.
+/// Used when scaling `l` would overflow `T::Native`, which it does well
before the quotient
+/// does.
+///
+/// Runs on magnitudes and restores the sign last, so it truncates toward zero.
+fn scaled_div<T: DecimalType>(
+ l: T::Native,
+ r: T::Native,
+ mul_pow: i8,
+) -> Result<T::Native, ArrowError> {
+ let zero = T::Native::ZERO;
+ let negative = l.is_lt(zero) != r.is_lt(zero);
+ let dividend = abs_checked::<T>(l)?;
+ let divisor = abs_checked::<T>(r)?;
+
+ let mut quotient = dividend.div_checked(divisor)?;
+ let mut remainder = dividend.mod_checked(divisor)?;
+ for _ in 0..mul_pow {
+ // `remainder * 10` overflows for divisors near `T::Native::MAX`, so
add the remainder
+ // ten times and take the divisor off whenever the running sum reaches
it.
+ let mut carried = zero;
+ let mut digit = zero;
+ for _ in 0..10 {
+ let headroom = divisor.sub_wrapping(remainder);
+ if carried.is_lt(headroom) {
+ carried = carried.add_wrapping(remainder);
+ } else {
+ carried = carried.sub_wrapping(headroom);
+ digit = digit.add_wrapping(T::Native::ONE);
+ }
+ }
+ quotient = quotient
+ .mul_checked(T::Native::usize_as(10))?
+ .add_checked(digit)?;
+ remainder = carried;
+ }
+
+ if negative {
+ quotient.neg_checked()
+ } else {
+ Ok(quotient)
+ }
+}
+
+fn abs_checked<T: DecimalType>(value: T::Native) -> Result<T::Native,
ArrowError> {
+ if value.is_lt(T::Native::ZERO) {
+ value.neg_checked()
+ } else {
+ Ok(value)
+ }
+}
+
/// Perform arithmetic operation on decimal arrays
fn decimal_op<T: DecimalType>(
op: Op,
@@ -1076,7 +1128,10 @@ fn decimal_op<T: DecimalType>(
l_s,
r,
r_s,
- l.mul_checked(l_mul)?.div_checked(r.mul_checked(r_mul)?)
+ match l.mul_checked(l_mul) {
+ Ok(scaled) => scaled.div_checked(r.mul_checked(r_mul)?),
+ Err(_) => scaled_div::<T>(l, r, mul_pow),
+ }
)
.with_precision_and_scale(result_precision, result_scale)?
}
@@ -1479,6 +1534,116 @@ mod tests {
assert_eq!(err, "Divide by zero error");
}
+ #[test]
+ fn test_decimal256_div_wide_intermediate() {
+ // Dividing two scale-37 values needs l * 10^41, which is 79 digits
and does not
+ // fit in an i256, even though the 41-digit quotient does.
+ let a = Decimal256Array::from(vec![i256::from_i128(
+ 60096743305738933273387748827369321010i128,
+ )])
+ .with_precision_and_scale(38, 37)
+ .unwrap();
+ let b = Decimal256Array::from(vec![i256::from_i128(
+ 60096763826458053191384497987259478584i128,
+ )])
+ .with_precision_and_scale(38, 37)
+ .unwrap();
+
+ let result = div(&a, &b).unwrap();
+ assert_eq!(result.data_type(), &DataType::Decimal256(76, 41));
+ assert_eq!(
+ result.as_primitive::<Decimal256Type>().value(0),
+
i256::from_string("99999965853869970143724273117679321341339").unwrap()
+ );
+
+ // Truncation stays toward zero on either side of the fallback.
+ let neg_a = neg(&a).unwrap();
+ let result = div(neg_a.as_primitive::<Decimal256Type>(), &b).unwrap();
+ assert_eq!(
+ result.as_primitive::<Decimal256Type>().value(0),
+
i256::from_string("-99999965853869970143724273117679321341339").unwrap()
+ );
+
+ let neg_b = neg(&b).unwrap();
+ let result = div(&a, neg_b.as_primitive::<Decimal256Type>()).unwrap();
+ assert_eq!(
+ result.as_primitive::<Decimal256Type>().value(0),
+
i256::from_string("-99999965853869970143724273117679321341339").unwrap()
+ );
+
+ let zero = Decimal256Array::from(vec![i256::ZERO])
+ .with_precision_and_scale(38, 37)
+ .unwrap();
+ let err = div(&a, &zero).unwrap_err().to_string();
+ assert_eq!(err, "Divide by zero error");
+ }
+
+ #[test]
+ fn test_decimal256_div_divisor_near_max() {
+ // A divisor past i256::MAX / 10 leaves no room to scale the running
remainder either.
+ let a = Decimal256Array::from(vec![
+ i256::from_string(
+
"5900000000000000000000000000000000000000000000000000000000000000000000000000",
+ )
+ .unwrap(),
+ ])
+ .with_precision_and_scale(76, 37)
+ .unwrap();
+ let b = Decimal256Array::from(vec![
+ i256::from_string(
+
"6000000000000000000000000000000000000000000000000000000000000000000000000000",
+ )
+ .unwrap(),
+ ])
+ .with_precision_and_scale(76, 37)
+ .unwrap();
+
+ let result = div(&a, &b).unwrap();
+ assert_eq!(
+ result.as_primitive::<Decimal256Type>().value(0),
+
i256::from_string("98333333333333333333333333333333333333333").unwrap()
+ );
+ }
+
+ #[test]
+ fn test_decimal128_div_wide_intermediate() {
+ // Same overflow one type down: 3.0 / 6.0 at scale 37 needs l * 10^38,
76 digits in i128.
+ let a =
Decimal128Array::from(vec![30000000000000000000000000000000000000i128])
+ .with_precision_and_scale(38, 37)
+ .unwrap();
+ let b =
Decimal128Array::from(vec![60000000000000000000000000000000000000i128])
+ .with_precision_and_scale(38, 37)
+ .unwrap();
+
+ let result = div(&a, &b).unwrap();
+ assert_eq!(result.data_type(), &DataType::Decimal128(38, 38));
+ assert_eq!(
+ result.as_primitive::<Decimal128Type>().value(0),
+ 50000000000000000000000000000000000000i128
+ );
+ }
+
+ #[test]
+ fn test_scaled_div_agrees_with_direct_division() {
+ for (l, r, mul_pow) in [
+ (7i128, 3i128, 4i8),
+ (-7, 3, 4),
+ (7, -3, 4),
+ (-7, -3, 4),
+ (1, 999_999_999, 9),
+ (i128::MAX / 10, 7, 1),
+ (i128::MAX / 10, -i128::MAX / 11, 1),
+ (0, 5, 6),
+ ] {
+ let scaled = l * 10i128.pow(mul_pow as u32);
+ assert_eq!(
+ scaled_div::<Decimal128Type>(l, r, mul_pow).unwrap(),
+ scaled / r,
+ "{l} * 10^{mul_pow} / {r}"
+ );
+ }
+ }
+
#[test]
fn test_decimal256_same_scale_add_sub() {
let lhs = Decimal256Array::from(vec