This is an automated email from the ASF dual-hosted git repository.
jonah pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/datafusion.git
The following commit(s) were added to refs/heads/main by this push:
new 1daf007462 fix: gcd returns negative results (#11099)
1daf007462 is described below
commit 1daf007462e338c56499231298a5e571884125d4
Author: Jonah Gao <[email protected]>
AuthorDate: Wed Jun 26 14:56:49 2024 +0800
fix: gcd returns negative results (#11099)
---
datafusion/functions/src/math/gcd.rs | 38 +++++++++++++++--------------
datafusion/sqllogictest/test_files/math.slt | 14 +++++++++++
2 files changed, 34 insertions(+), 18 deletions(-)
diff --git a/datafusion/functions/src/math/gcd.rs
b/datafusion/functions/src/math/gcd.rs
index 6346f96d2c..ace4937d6d 100644
--- a/datafusion/functions/src/math/gcd.rs
+++ b/datafusion/functions/src/math/gcd.rs
@@ -92,42 +92,44 @@ fn gcd(args: &[ArrayRef]) -> Result<ArrayRef> {
}
}
-/// Computes greatest common divisor using Binary GCD algorithm.
-pub fn compute_gcd(x: i64, y: i64) -> Result<i64> {
- if x == 0 {
- return Ok(y);
+/// Computes gcd of two unsigned integers using Binary GCD algorithm.
+fn unsigned_gcd(mut a: u64, mut b: u64) -> u64 {
+ if a == 0 {
+ return b;
}
- if y == 0 {
- return Ok(x);
+ if b == 0 {
+ return a;
}
- let mut a = x.unsigned_abs();
- let mut b = y.unsigned_abs();
-
let shift = (a | b).trailing_zeros();
a >>= shift;
b >>= shift;
a >>= a.trailing_zeros();
-
loop {
b >>= b.trailing_zeros();
if a > b {
swap(&mut a, &mut b);
}
-
b -= a;
-
if b == 0 {
- // because the input values are i64, casting this back to i64 is
safe
- return (a << shift).try_into().map_err(|_| {
- arrow_datafusion_err!(ArrowError::ComputeError(format!(
- "Signed integer overflow in GCD({x}, {y})"
- )))
- });
+ return a << shift;
}
}
}
+/// Computes greatest common divisor using Binary GCD algorithm.
+pub fn compute_gcd(x: i64, y: i64) -> Result<i64> {
+ let a = x.unsigned_abs();
+ let b = y.unsigned_abs();
+ let r = unsigned_gcd(a, b);
+ // gcd(i64::MIN, i64::MIN) = i64::MIN.unsigned_abs() cannot fit into i64
+ r.try_into().map_err(|_| {
+ arrow_datafusion_err!(ArrowError::ComputeError(format!(
+ "Signed integer overflow in GCD({x}, {y})"
+ )))
+ })
+}
+
#[cfg(test)]
mod test {
use std::sync::Arc;
diff --git a/datafusion/sqllogictest/test_files/math.slt
b/datafusion/sqllogictest/test_files/math.slt
index 3a433c76fc..dfbfa84bf0 100644
--- a/datafusion/sqllogictest/test_files/math.slt
+++ b/datafusion/sqllogictest/test_files/math.slt
@@ -573,5 +573,19 @@ select gcd(20, 1000), lcm(20, 1000);
query error DataFusion error: Arrow error: Compute error: Signed integer
overflow in GCD\(\-9223372036854775808, \-9223372036854775808\)
select gcd(-9223372036854775808, -9223372036854775808);
+# gcd(i64::MIN, 0)
+query error DataFusion error: Arrow error: Compute error: Signed integer
overflow in GCD\(\-9223372036854775808, 0\)
+select gcd(-9223372036854775808, 0);
+
+# gcd(0, i64::MIN)
+query error DataFusion error: Arrow error: Compute error: Signed integer
overflow in GCD\(0, \-9223372036854775808\)
+select gcd(0, -9223372036854775808);
+
+# Test gcd with zero and negative values
+query III
+select gcd(0, 0), gcd(-100, 0), gcd(0, -100);
+----
+0 100 100
+
query error DataFusion error: Arrow error: Compute error: Signed integer
overflow in LCM\(\-9223372036854775808, \-9223372036854775808\)
select lcm(-9223372036854775808, -9223372036854775808);
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
