Skip to content

Commit 5183e21

Browse files
fangchenliroktadeja
authored
GH-46901: [C++][Compute] Add remainder and modulo kernels (#48914)
### Rationale for this change Arrow is currently missing remainder and modulo kernels. ### What changes are included in this PR? Add the kernels `remainder`, `remainder_checked`, `modulo`, and `modulo_checked`, following the terminology in the [divmod proposal](https://lists.apache.org/thread/h3t6nz1ys2k2hnbrjvwyoxkf70cps8sh): * `remainder` uses truncated (C/C++) semantics — the result has the sign of the dividend, e.g. `remainder(-7, 3) == -1`. * `modulo` uses floored (Python/R) semantics — the result has the sign of the divisor, e.g. `modulo(-7, 3) == 2`. Both are supported for integer, floating-point and decimal inputs, and are exposed as `compute::Remainder` / `compute::Modulo` in `api_scalar.h`. Decimal arguments are promoted to a common scale like `add`, but the result type is resolved by a dedicated resolver rather than reusing `ResolveDecimalAdditionOrSubtractionOutput`: a remainder is always smaller in magnitude than the divisor, so no extra digit is needed for a carry, and the result is `precision = max(p1, p2)`, `scale = s1`. This keeps maximum-precision inputs (`decimal128(38, 0)`, `decimal256(76, 0)`) from overflowing the decimal precision range. Left as follow-ups: combined divmod #27909, floor division #39386, and duration support. ### Are these changes tested? Yes. New tests cover truncated vs. floored semantics across signed/unsigned integer, floating-point and decimal types, division by zero, `INT_MIN % -1` overflow, and decimal result-type resolution (same type in/out, mixed precisions and scales, Decimal128/Decimal256 promotion, decimal/integer promotion, and maximum-precision decimals). ### Are there any user-facing changes? Yes — four new compute functions (`remainder`, `remainder_checked`, `modulo`, `modulo_checked`), the corresponding `compute::Remainder` / `compute::Modulo` C++ APIs, and a new `BasicDecimal256 operator%`. These are additions only; no existing API is changed or removed. * GitHub Issue: #46901 * xref: #46902, * xref: #28497 Lead-authored-by: Fangchen Li <[email protected]> Co-authored-by: Rok Mihevc <[email protected]> Co-authored-by: tadeja <[email protected]> Signed-off-by: Rok Mihevc <[email protected]>
1 parent f0d043c commit 5183e21

11 files changed

Lines changed: 648 additions & 48 deletions

File tree

‎cpp/src/arrow/compute/api_scalar.cc‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -799,8 +799,10 @@ Result<Datum> RoundToMultiple(const Datum& arg, RoundToMultipleOptions options,
799799
SCALAR_ARITHMETIC_BINARY(Add, "add", "add_checked")
800800
SCALAR_ARITHMETIC_BINARY(Divide, "divide", "divide_checked")
801801
SCALAR_ARITHMETIC_BINARY(Logb, "logb", "logb_checked")
802+
SCALAR_ARITHMETIC_BINARY(Modulo, "modulo", "modulo_checked")
802803
SCALAR_ARITHMETIC_BINARY(Multiply, "multiply", "multiply_checked")
803804
SCALAR_ARITHMETIC_BINARY(Power, "power", "power_checked")
805+
SCALAR_ARITHMETIC_BINARY(Remainder, "remainder", "remainder_checked")
804806
SCALAR_ARITHMETIC_BINARY(ShiftLeft, "shift_left", "shift_left_checked")
805807
SCALAR_ARITHMETIC_BINARY(ShiftRight, "shift_right", "shift_right_checked")
806808
SCALAR_ARITHMETIC_BINARY(Subtract, "subtract", "subtract_checked")

‎cpp/src/arrow/compute/api_scalar.h‎

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -671,6 +671,42 @@ Result<Datum> Divide(const Datum& left, const Datum& right,
671671
ArithmeticOptions options = ArithmeticOptions(),
672672
ExecContext* ctx = NULLPTR);
673673

674+
/// \brief Compute the remainder (truncated division) of two values.
675+
/// Array values must be the same length. If either argument is null the result
676+
/// will be null. For integer and decimal types, if there is a zero divisor, an
677+
/// error will be raised. For floating-point types, a zero divisor yields NaN
678+
/// unless overflow checking is enabled, in which case an error is raised.
679+
///
680+
/// The result has the same sign as the dividend (C/C++ semantics).
681+
///
682+
/// \param[in] left the dividend
683+
/// \param[in] right the divisor
684+
/// \param[in] options arithmetic options (enable/disable overflow checking), optional
685+
/// \param[in] ctx the function execution context, optional
686+
/// \return the elementwise remainder
687+
ARROW_EXPORT
688+
Result<Datum> Remainder(const Datum& left, const Datum& right,
689+
ArithmeticOptions options = ArithmeticOptions(),
690+
ExecContext* ctx = NULLPTR);
691+
692+
/// \brief Compute the modulo (floored division) of two values.
693+
/// Array values must be the same length. If either argument is null the result
694+
/// will be null. For integer and decimal types, if there is a zero divisor, an
695+
/// error will be raised. For floating-point types, a zero divisor yields NaN
696+
/// unless overflow checking is enabled, in which case an error is raised.
697+
///
698+
/// The result has the same sign as the divisor (Python semantics).
699+
///
700+
/// \param[in] left the dividend
701+
/// \param[in] right the divisor
702+
/// \param[in] options arithmetic options (enable/disable overflow checking), optional
703+
/// \param[in] ctx the function execution context, optional
704+
/// \return the elementwise modulo
705+
ARROW_EXPORT
706+
Result<Datum> Modulo(const Datum& left, const Datum& right,
707+
ArithmeticOptions options = ArithmeticOptions(),
708+
ExecContext* ctx = NULLPTR);
709+
674710
/// \brief Negate values.
675711
///
676712
/// If argument is null the result will be null.

‎cpp/src/arrow/compute/kernels/base_arithmetic_internal.h‎

Lines changed: 75 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -34,6 +34,7 @@ namespace arrow {
3434

3535
using internal::AddWithOverflow;
3636
using internal::DivideWithOverflow;
37+
using internal::ModuloWithOverflow;
3738
using internal::MultiplyWithOverflow;
3839
using internal::NegateWithOverflow;
3940
using internal::SubtractWithOverflow;
@@ -468,6 +469,80 @@ struct FloatingDivideChecked {
468469
// TODO: Add decimal
469470
};
470471

472+
enum class RemainderMode { kTruncated, kFloored };
473+
474+
// Truncated: sign follows the dividend (C/C++ '%').
475+
// Floored: sign follows the divisor (Python '%').
476+
template <RemainderMode Mode, typename T>
477+
T FinishRemainder(T rem, T divisor) {
478+
if constexpr (Mode == RemainderMode::kTruncated) {
479+
return rem;
480+
} else {
481+
if constexpr (std::is_floating_point_v<T>) {
482+
if (rem == 0) {
483+
// Zero takes the sign of the divisor
484+
return std::copysign(rem, divisor);
485+
}
486+
}
487+
if constexpr (!std::is_unsigned_v<T>) {
488+
const T zero{};
489+
if ((rem > zero && divisor < zero) || (rem < zero && divisor > zero)) {
490+
rem += divisor;
491+
}
492+
}
493+
return rem;
494+
}
495+
}
496+
497+
template <RemainderMode Mode, bool Checked>
498+
struct RemainderImpl {
499+
template <typename T, typename Arg0, typename Arg1>
500+
static enable_if_floating_value<T> Call(KernelContext*, Arg0 left, Arg1 right,
501+
Status* st) {
502+
static_assert(std::is_same_v<T, Arg0> && std::is_same_v<T, Arg1>);
503+
if constexpr (Checked) {
504+
if (ARROW_PREDICT_FALSE(right == 0)) {
505+
*st = Status::Invalid("divide by zero");
506+
return T{};
507+
}
508+
}
509+
return FinishRemainder<Mode, T>(std::fmod(left, right), right);
510+
}
511+
512+
template <typename T, typename Arg0, typename Arg1>
513+
static enable_if_integer_value<T> Call(KernelContext*, Arg0 left, Arg1 right,
514+
Status* st) {
515+
static_assert(std::is_same_v<T, Arg0> && std::is_same_v<T, Arg1>);
516+
T result{};
517+
if (ARROW_PREDICT_FALSE(ModuloWithOverflow(left, right, &result))) {
518+
if (right == 0) {
519+
*st = Status::Invalid("divide by zero");
520+
} else if constexpr (Checked) {
521+
*st = Status::Invalid("overflow");
522+
}
523+
// INT_MIN % -1 is 0 when unchecked
524+
return T{};
525+
}
526+
return FinishRemainder<Mode, T>(result, right);
527+
}
528+
529+
template <typename T, typename Arg0, typename Arg1>
530+
static enable_if_decimal_value<T> Call(KernelContext*, Arg0 left, Arg1 right,
531+
Status* st) {
532+
static_assert(std::is_same_v<T, Arg0> && std::is_same_v<T, Arg1>);
533+
if (ARROW_PREDICT_FALSE(right == T{})) {
534+
*st = Status::Invalid("divide by zero");
535+
return T{};
536+
}
537+
return FinishRemainder<Mode, T>(left % right, right);
538+
}
539+
};
540+
541+
using Remainder = RemainderImpl<RemainderMode::kTruncated, /*Checked=*/false>;
542+
using RemainderChecked = RemainderImpl<RemainderMode::kTruncated, /*Checked=*/true>;
543+
using Modulo = RemainderImpl<RemainderMode::kFloored, /*Checked=*/false>;
544+
using ModuloChecked = RemainderImpl<RemainderMode::kFloored, /*Checked=*/true>;
545+
471546
struct Negate {
472547
template <typename T, typename Arg>
473548
static constexpr enable_if_floating_value<T> Call(KernelContext*, Arg arg, Status*) {

‎cpp/src/arrow/compute/kernels/scalar_arithmetic.cc‎

Lines changed: 75 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -613,6 +613,19 @@ Result<TypeHolder> ResolveDecimalAdditionOrSubtractionOutput(
613613
});
614614
}
615615

616+
Result<TypeHolder> ResolveDecimalRemainderOutput(KernelContext*,
617+
const std::vector<TypeHolder>& types) {
618+
return ResolveDecimalBinaryOperationOutput(
619+
types,
620+
[](int32_t p1, int32_t s1, int32_t p2,
621+
int32_t s2) -> Result<std::pair<int32_t, int32_t>> {
622+
DCHECK_EQ(s1, s2);
623+
// Unlike addition, no extra digit is needed: the magnitude of a
624+
// remainder is always less than that of the divisor.
625+
return std::make_pair(std::max(p1, p2), s1);
626+
});
627+
}
628+
616629
Result<TypeHolder> ResolveDecimalMultiplicationOutput(
617630
KernelContext*, const std::vector<TypeHolder>& types) {
618631
return ResolveDecimalBinaryOperationOutput(
@@ -674,6 +687,9 @@ void AddDecimalBinaryKernels(const std::string& name, ScalarFunction* func) {
674687
if (op == "add" || op == "subtract") {
675688
out_type = OutputType(ResolveDecimalAdditionOrSubtractionOutput);
676689
constraint = DecimalsHaveSameScale();
690+
} else if (op == "remainder" || op == "modulo") {
691+
out_type = OutputType(ResolveDecimalRemainderOutput);
692+
constraint = DecimalsHaveSameScale();
677693
} else if (op == "multiply") {
678694
out_type = OutputType(ResolveDecimalMultiplicationOutput);
679695
} else if (op == "divide") {
@@ -784,7 +800,7 @@ struct ArithmeticFunction : ScalarFunction {
784800
// "add_checked" -> "add"
785801
const auto func_name = name();
786802
const std::string op = func_name.substr(0, func_name.find("_"));
787-
if (op == "add" || op == "subtract") {
803+
if (op == "add" || op == "subtract" || op == "remainder" || op == "modulo") {
788804
return CastBinaryDecimalArgs(DecimalPromotion::kAdd, types);
789805
} else if (op == "multiply") {
790806
return CastBinaryDecimalArgs(DecimalPromotion::kMultiply, types);
@@ -1173,6 +1189,42 @@ const FunctionDoc div_checked_doc{
11731189
"integer overflow is encountered."),
11741190
{"dividend", "divisor"}};
11751191

1192+
const FunctionDoc remainder_doc{
1193+
"Compute the remainder of the arguments element-wise",
1194+
("The result has the same sign as the dividend (truncated division).\n"
1195+
"This is equivalent to the C/C++ '%' operator.\n"
1196+
"Integer and decimal division by zero returns an error, while\n"
1197+
"floating-point division by zero returns NaN.\n"
1198+
"Use function \"remainder_checked\" if you want to get an error\n"
1199+
"in all the aforementioned cases."),
1200+
{"dividend", "divisor"}};
1201+
1202+
const FunctionDoc remainder_checked_doc{
1203+
"Compute the remainder of the arguments element-wise",
1204+
("The result has the same sign as the dividend (truncated division).\n"
1205+
"This is equivalent to the C/C++ '%' operator.\n"
1206+
"An error is returned when trying to divide by zero, or when\n"
1207+
"integer overflow is encountered."),
1208+
{"dividend", "divisor"}};
1209+
1210+
const FunctionDoc modulo_doc{
1211+
"Compute the modulo of the arguments element-wise",
1212+
("The result has the same sign as the divisor (floored division).\n"
1213+
"This is equivalent to Python's '%' operator.\n"
1214+
"Integer and decimal division by zero returns an error, while\n"
1215+
"floating-point division by zero returns NaN.\n"
1216+
"Use function \"modulo_checked\" if you want to get an error\n"
1217+
"in all the aforementioned cases."),
1218+
{"dividend", "divisor"}};
1219+
1220+
const FunctionDoc modulo_checked_doc{
1221+
"Compute the modulo of the arguments element-wise",
1222+
("The result has the same sign as the divisor (floored division).\n"
1223+
"This is equivalent to Python's '%' operator.\n"
1224+
"An error is returned when trying to divide by zero, or when\n"
1225+
"integer overflow is encountered."),
1226+
{"dividend", "divisor"}};
1227+
11761228
const FunctionDoc negate_doc{"Negate the argument element-wise",
11771229
("Results will wrap around on integer overflow.\n"
11781230
"Use function \"negate_checked\" if you want overflow\n"
@@ -1724,6 +1776,28 @@ void RegisterScalarArithmetic(FunctionRegistry* registry) {
17241776

17251777
DCHECK_OK(registry->AddFunction(std::move(divide_checked)));
17261778

1779+
// ----------------------------------------------------------------------
1780+
auto remainder = MakeArithmeticFunctionNotNull<Remainder>("remainder", remainder_doc);
1781+
AddDecimalBinaryKernels<Remainder>("remainder", remainder.get());
1782+
DCHECK_OK(registry->AddFunction(std::move(remainder)));
1783+
1784+
// ----------------------------------------------------------------------
1785+
auto remainder_checked = MakeArithmeticFunctionNotNull<RemainderChecked>(
1786+
"remainder_checked", remainder_checked_doc);
1787+
AddDecimalBinaryKernels<RemainderChecked>("remainder_checked", remainder_checked.get());
1788+
DCHECK_OK(registry->AddFunction(std::move(remainder_checked)));
1789+
1790+
// ----------------------------------------------------------------------
1791+
auto modulo = MakeArithmeticFunctionNotNull<Modulo>("modulo", modulo_doc);
1792+
AddDecimalBinaryKernels<Modulo>("modulo", modulo.get());
1793+
DCHECK_OK(registry->AddFunction(std::move(modulo)));
1794+
1795+
// ----------------------------------------------------------------------
1796+
auto modulo_checked =
1797+
MakeArithmeticFunctionNotNull<ModuloChecked>("modulo_checked", modulo_checked_doc);
1798+
AddDecimalBinaryKernels<ModuloChecked>("modulo_checked", modulo_checked.get());
1799+
DCHECK_OK(registry->AddFunction(std::move(modulo_checked)));
1800+
17271801
// ----------------------------------------------------------------------
17281802
auto negate = MakeUnaryArithmeticFunction<Negate>("negate", negate_doc);
17291803
AddDecimalUnaryKernels<Negate>(negate.get());

0 commit comments

Comments
 (0)