Is it possible for integer division in C++ to express a compact mathematical condition, as for Euclidean division

Question

I am studying integer division in C++. At the same time, I read the wikipedia article 'Euclidean division'. In this article there is such a lemma:

a = b · q + r     // formula
0 ≤ r < |b|       // condition

In these formulas a — dividend, b — divisor (b ≠ 0), q — quotient and r — remainder.

As far as I understand, the condition 0 ≤ r < |b| is necessary to ensure the unambiguity of the division results.

I compared the results of some examples of integer division for Euclidean division and for integer division in C++. They work in different ways:

 a  | b  | Euclidean division|       in C++      | matching
    |    |  a / b  |  a % b  |  a / b  |  a % b  | results
----------------------------------------------------------------
 13 |  5 |    2    |    3    |    2    |    3    |    yes
-13 |  5 |   -3    |    2    |   -2    |   -3    |    no
 13 | -5 |   -2    |    3    |   -2    |    3    |    yes
-13 | -5 |    3    |    2    |    2    |   -3    |    no

Notation in the table: a / b equivalent to quotient q, a % b equivalent to remainder r.

I understand how integer division works in C++:

1. q (quotient) is obtained by cutting off (truncate) the fractional part from the result of the usual division a / b;
2. the sign of the quotient q is obtained as in the usual division;
3. the sign of the remainder r is obtained by deducing from the formula (mnemonic: the sign is the same as that of the dividend a; this has been added since C++11, before the remainder sign was implementation-defined).

My question. Is it possible for integer division in C++ to express the above verbal description with a compact mathematical condition, as for Euclidean division? What might it look like?

a = b · q + r     // formula
???               // condition

Answer 1

The most similar way to express similar to the Euclidean division i believe would be

$$ a = b \cdot q + r \\ 0 \le \mathrm{sgn}(a) r < |b| $$

Proof:

We can let the original Euclidean divide do all the proving by considering the two cases:

1. When $a>0$ then the original Euclidean division form is retained $$ a = b \cdot q + r \\ 0 \le r < |b| $$

2. Otherwise $a<0$ then rewrite the system as $$ a' = b \cdot q' + r' \\ 0 \le r' < |b| $$ where $$ a'=-a\\ q'=-q\\ r'=-r $$

This not only proves the uniqueness of the solution, but also shows how the values could be computed from the Euclidean division. For $a > 0$ results are identical.

Example: Given $a = -13$, $b = 5$, then $a'=13$. Euclidean division gives the solution $q'=2$ and $r'=3$. Thus $q=-2$ and $r=-3$.

Example 2: Given $a = -13$, $b = -5$, then $a'=13$. Euclidian division gives the solution $q'=-2$ and $r'=3$. Thus $q=2$ and $r=-3$.

---

Edit: Having re-read the question more carefully, I now realize I initially misunderstood what was requested (sorry). I will just leave the code as is in case anyone who wants to compute the Euclidean division might stumble on it.

#include <tuple>
#include <cmath>
#include <iostream>


template<typename T>
std::tuple<T, T> euclidean_divide(T dividend, T divisor) {
    if (dividend >= 0) {
        return {dividend / divisor, dividend % divisor};
    } else {
        dividend = std::abs(dividend);
        if (divisor > 0) {
            return {-((dividend + divisor) / divisor), divisor - (dividend % divisor)};
        } else {
            divisor = std::abs(divisor);
            return {(dividend + divisor) / divisor, divisor - (dividend % divisor)};
        }
    }
}

int main() {
    auto [q0, r0] = euclidean_divide(13, 5);
    std::cout << q0 << ',' << r0 << std::endl;
    auto [q1, r1] = euclidean_divide(-13, 5);
    std::cout << q1 << ',' << r1 << std::endl;
    auto [q2, r2] = euclidean_divide(13, -5);
    std::cout << q2 << ',' << r2 << std::endl;
    auto [q3, r3] = euclidean_divide(-13, -5);
    std::cout << q3 << ',' << r3 << std::endl;
}