Integer division
- Document number:
- P3724R0
- Date:
2025-06-03 - Audience:
- LEWG, SG6
- Project:
- ISO/IEC 14882 Programming Languages — C++, ISO/IEC JTC1/SC22/WG21
- Reply-To:
- Jan Schultke <[email protected]>
- GitHub Issue:
- wg21.link/P3724/github
- Source:
- github.com/Eisenwave/cpp-proposals/blob/master/src/intdiv.cow
operator.
I propose standard library functions for computing quotients and remainders
with other rounding modes.
Contents
Introduction
Existing practice
Language support for integer division
Hardware support for integer division
Motivation
Is this not trivial for the user to do?
Computing remainders is hard, actually
Design
Relation to P0105R1
Naming
Isn't std :: div_ *
inconsistent with the existing std :: div
?
Should it be std :: div_floor
and std :: div_ceil
?
Should it be std :: div_to_pos_inf
?
Why is it std :: mod
?
Interface
Error handling and noexcept
Why no std :: rounding
parameter?
std :: div_result < T >
Do we really need the std :: div_rem_ *
functions?
Supported rounding modes
Rounding to zero
Rounding to even/odd
To-nearest-rounding division and tie breaking
std :: mod
Implementation experience
Try it yourself
Wording
[structure.specifications]
[version.syn]
[bit.pow.two]
[numeric.ops.overview]
[numeric.sat.func]
[numeric.int.div]
[simd.bit]
References
Appendix A — Reference implementation
1. Introduction
C++ currently only offers truncating integer division in the form of the
operator.
However, other rounding modes have various use cases too,
and implementing these as the user can be surprisingly hard,
especially when integer overflow needs to be avoided,
and negative inputs are accepted.
Furthermore, since the
operator rounds towards zero,
the
(remainder) operator may yield negative results
(specifically, when the dividend is negative).
In modular arithmetic and various other use cases,
this is undesirable,
and a negative remainder may be surprising in general.
Therefore, I propose a set of standard library functions which implement a variety of rounding modes when computing quotients and remainders. Such a feature was previously part of [P0105R1] and the Numerics TS [P1889R1], but was eventually abandoned by the author, in part due to design disagreements.
Your browser requires MathML support to view the equation above.
1.1. Existing practice
To better put this proposal into context, it is relevant to know what rounding modes are usually supported by programming languages and hardware.
1.1.1. Language support for integer division
Language | Quotient | Remainder | Rounding |
---|---|---|---|
C and C++ | to zero | ||
D | to zero | ||
Objective-C | to zero | ||
C# | to zero | ||
Java | to zero | ||
Rust | to zero | ||
Go | to zero | ||
Swift | to zero | ||
Scala | to zero | ||
OCaml | to zero | ||
Perl | to zero | ||
GLSL | N/A | to zero | |
JavaScript | to zero (for |
||
Python | to | ||
Lua | to | ||
R | to | ||
Dart | to | ||
Haskell |
|
||
Ada |
|
||
Fortran |
|
||
CSS | N/A |
|
|
Kotlin |
|
||
Julia |
depending on
|
1.1.2. Hardware support for integer division
Architecture | Type | Quotient | Remainder | Rounding |
---|---|---|---|---|
x86 and x86_64 | CPU | to zero | ||
ARM | CPU | N/A | to zero | |
RISC-V | CPU | to zero | ||
PowerPC | CPU | N/A | to zero | |
MIPS | CPU | to zero | ||
AVR (8-bit) | CPU | N/A | N/A | N/A |
WebAssembly | VM | to zero | ||
LLVM IR | VM | to zero | ||
Java Bytecode | VM | to zero |
While every architecture rounds to zero, there there are major differences in how the remainder is obtained:
- On x86_64 and MIPS, the quotient and remainder are computed simultaneously, although MIPS also supports separate computation of the remainder.
- On other architectures, even if there is support for computing the remainder separately, if both the quotient and remainder are needed, it is faster to compute the remainder using the quotient of the division.
- In some cases, the remainder can only be computed using the quotient.
Only if the division rounds towards zero can this also be translated literally into a multiplication and subtraction, without the possibility of overflow. This makes rounding towards zero by far the most useful rounding mode in computing, and it is no coincidence that every architecture implements it.
2. Motivation
Rounding modes other than rounding towards zero are commonly useful. An extremely common alternative is rounding towards , which is the rounding mode of the division operator in some other languages (§1.1.1. Language support for integer division). See below for some motivating examples.
Note that with truncating division, the zero-bucket would contain all elements in [-999, 999], which would make it larger than any other bucket.
While the examples are somewhat abstract, they appear in vast amounts of concrete problems. For example, we need to know how many blocks of memory must be allocated to hold a certain amount of bytes, do interval arithmetic, fixed-point arithmetic with rounding of choice, etc. etc.
2.1. Is this not trivial for the user to do?
At first glance,
it would seem trivial to change rounding modes by making slight adjustments to
.
However, doing so with correct output, high performance,
and without introducing more undefined behavior than
already has,
is surprisingly hard.
There is an ocean of examples where C++ users have gotten this wrong. A few droplets are listed below.
).
For example, one answer with 67 upvotes (at the time of writing) attempts to implement ceiling (rounded towards positive infinity) integer division as follows:
The quotient
would be
, not
for inputs
and
,
which is obviously wrong because it rounds
up to
, skipping zero.
To be fair, the answer is correct for positive integers, and perhaps the author didn't want to support negative inputs anyway. However, the answer contains no disclaimer that clarifies this.
andabs ( a )
have undefined behavior givenabs ( b )
inputINT_MIN
overflows on large inputs indiv_round
anda - b a + b - all functions branch depending on whether the quotient is negative, and at least for a standard library (which has to cover a wide variety of use cases), such a branch could be highly unpredictable
Users sometimes also implement these functions using
or
,
but this can equally yield incorrect results,
and use of floating-point numbers is unnecessary for this task.
2.2. Computing remainders is hard, actually
There exist various use cases (modular arithmetic, integer-to-string conversion, etc.)
where we need both the quotient and remainder at the same time.
The naive approach to computing the remainder
using an integer division function
This approach is only safe when
is
,
i.e. when rounding towards zero.
If we now call
,
where
is
,
then
is
.
The multiplication
has undefined behavior
because it results in
, which cannot be represented as
.
Crucially, it does not mean that
cannot be defined for these inputs.
The correct quotient is
,
and the correct remainder is
.
It just means that for any rounding mode except towards zero,
we cannot use the naive formula to obtain a remainder.
In conclusion,
the proposal should also include a way to obtain a remainder in tandem with the quotient.
Any other design would simply invite bugs where users foolishly assume that
the
method works for all rounding modes.
3. Design
The design aims of this proposal are to provide concise, simple, efficient, robust functions which are useful in practice.
3.1. Relation to P0105R1
The design somewhat leans on [P0105R1] (which first proposed division functions with custom rounding), but heavily deviates from it. In general, [P0105R1] was a proposal with overly broad scope, and some questionable design choices, such as:
- Making some of the rounding modes conditionally supported, even when providing them isn't particularly difficult.
- Adding rounding modes which optimize for latency or code size,
without much motivation or details.
The proposal provided no concrete example of how this implementation freedom could be utilized,
and I suspect that any implementation would default to rounding to zero,
matching the
operator anyway./
3.2. Naming
All functions which compute a quotient begin with
,
and functions which also compute a remainder begin with
.
Furthermore, the functions include the name of the rounding mode
in a format that requires as little prior knowledge as feasible.
3.2.1. Isn't std :: div_ *
inconsistent with the existing std :: div
?
It is worth pointing out that there already exist
functions in the standard library, returning
,
which contains the quotient and remainder.
The proposal does not aim for consistency because the facilities are an unnecessary
and rarely-used C relic for the most part.
On the contrary, when investigating existing practice in §2.1. Is this not trivial for the user to do?,
I found that almost every definition of these differently-rounded division functions
uses
names.
This naming scheme is well-established and intuitive for users.
3.2.2. Should it be std :: div_floor
and std :: div_ceil
?
While the use of names like
and
is common in various domains,
including in
,
I do not believe we should perpetuate this design because:
- The scheme does not nicely extend to division with rounding away from zero; there is no established term for that.
-
A hypothetical
(for rounding to the nearest integer) would be somewhat perplexing because all proposed functions round, just towards different targets.std :: div_round -
The scheme is needlessly hostile towards novices
who are not yet familiar with the fact that
rounds towards negative infinity.
By comparison,
is self-documenting.std :: div_to_neg_inf
Regardless whether the functions end up called
or
, the names should remain somewhat brief so they take up
a reasonable amount of space in C++ expressions.
3.2.3. Should it be std :: div_to_pos_inf
?
While it looks nicer on paper if
and
have symmetrical names,
this does not have any clear technical benefit to the user.
is sufficiently clear,
and adding
would merely make the function name longer.
3.2.4. Why is it std :: mod
?
.
Despite the fact that
,
it is arguably the best name because:
-
It follows the conventions of Haskell, Ada, CSS, and many more languages,
where
mod rounds towards (unlike% ,rem , etc.). See §1.1.1. Language support for integer division. - It matches the notation of the modulo operator in mathematical literature. That is, .
3.3. Interface
The functions generally match the style of similar features in
,
like [numeric.sat] or [numeric.ops.gcd].
The design also follows [P3161R4].
It is constrained to accept only signed or unsigned integer types.
3.3.1. Error handling and noexcept
These functions are not
because they could not have a wide contract;
they naturally have undefined behavior for cases like
or
.
Looking at § Appendix A — Reference implementation,
it would require additional effort to perform error handling such as throwing exceptions,
so it seems best to leave these functions undefined if and only if division is undefined too.
However, an invocation of these functions is not a constant expression for such inputs; i.e. we don't get undefined behavior during constant evaluation. This can even be implemented without a single additional line of code: since we always perform a division in these functions, they naturally get disqualified from being core constant expressions when division is undefiend.
3.3.2. Why no std :: rounding
parameter?
As compared to [P0105R1], I do not propose that the rounding mode is passed as a runtime parameter.
In virtually every case, the rounding mode for an integer division is a fixed choice.
This is evidenced by the ten trillion existing uses of the
operator
which always truncate.
Also, the implementation of the proposed functions does not lend itself to a runtime parameter:
As can be seen, these implementations are substantially different.
could theoretically use the
instead,
it requires more operations to compute this positive/negative sign instead of merely checking
whether the quotient is negative.
This would be an unnecessary performance penalty.
In practice, compilers optimize
strictly worse than
.
If we now provided a runtime
,
the obvious implementation would look like:
The user can trivially make such an
and
themselves,
if they actually need to.
If they don't (which is likely),
all we accomplish is making the user write
instead of
.
3.3.3. std :: div_result < T >
As seen in in §3.3. Interface,
we define an additional class template
:
This generally matches standard library style,
including the active proposal [P3161R4],
and including the "legacy types"
,
.
That is, we should not use reference output parameters,
but return a value.
However, we should also not reuse those legacy types because it is not possible to deduce their "member type" from the class, which would make them clunky in generic code. There also exist no such classes for extended integer types and bit-precise integer types.
exists because the user may want to compare
the quotient and remainder to an existing pair of values in one go,
or store results of
functions in a
, etc.
It would seem arbitrarily limiting to make
incomparable.
3.3.4. Do we really need the std :: div_rem_ *
functions?
Yes, because it is non-trivial to compute the remainder without overflow for rounding modes other than towards zero. See §2.2. Computing remainders is hard, actually.
Furthermore, it is relatively cheap to obtain the remainder as a side product of any division function (see § Appendix A — Reference implementation). On extremely feature-starved hardware with no instructions for division and multiplication, computing the remainder via multiplication may be more expensive than producing it "directly" during division (implemented in software).
3.4. Supported rounding modes
It is apparent that the proposal contains quite a lot of rounding modes
– more than just the traditional
,
,
.
It is therefore valid to ask:
Do we really need all these rounding modes?
All proposed "top-level rounding modes" have practical applications. For consistency, the same set of "tie-breaking rounding modes" is provided. In any case, the implementation of these modes is all fairly similar, and there is neither any significant implementation cost (§ Appendix A — Reference implementation) nor wording cost (§6. Wording) to having a few extra functions. This would be a much different discussion for floating-point numbers.
I suspect that cherry-picking the "useful" rounding modes out of the proposed ones would devolve into endless discussion, and the design would have an inconsistent feel to it if say, division away from zero was provided, but no division to the nearest integer with tie breaks away from zero.
3.4.1. Rounding to zero
The "trivial" functions
and
exist solely for consistency and enhanced expressiveness.
Note that not every has a truncating integer division like C++.
For example, the
to avoid confusion.
3.4.2. Rounding to even/odd
Rounding to even/odd integers is mainly useful because it is unbiased. That is, when dividing a large amount of integers, results would not gravitate towards one end due to rounding mode bias towards zero, infinity, etc. This may be important when operating on fixed-point numbers.
[P0105R1] provides additional motivation and explanation of these rounding modes.
3.4.3. To-nearest-rounding division and tie breaking
Saying "round to nearest" is not clear enough in itself
because ties (where the fractional part of the quotient is exactly
)
could also be resolved in multiple ways.
Any of the "top-level rounding modes" could plausibly be chosen
as a "tie-breaking rounding mode" as well,
which is what this proposal offers.
3.5. std :: mod
In addition to the quotient (
)
and quotient/remainder functions (
),
we also define a single function
which specifically computes the remainder of the division rounding towards .
Unlike the other rounding modes, the remainder of division rounding to is uniquely useful for modular arithmetic because the sign of the remainder is the sign of the divisor. In other words, if we divide by a positive number, the remainder is always positive. This is why it has a dedicated function.
Division rounding to zero, where the sign of the remainder is that of the divisor,
already has
, so no dedicated function is required.
The other rounding modes have more chaotic remainder signs,
and thus it is rarely useful to compute the remainder in isolation,
not in conjunction with the quotient.
4. Implementation experience
A reference implementation can be found on [GitHub]. A simplified version of that, for educational purposes, can be found at § Appendix A — Reference implementation.
Generally speaking,
a portable strategy is to implement all divisions by performing a division
with rounding towards zero (
and
),
and then adjusting the quotient and remainder to emulate a different rounding mode.
On x86_64, Clang compiles this as follows:
Note that even on architectures where the remainder is not computed
simultaneously with the quotient like for
,
only one division is necessary;
the remainder can be obtained from the quotient.
Consequently, the implementation effort for all of these functions is close to zero.
None of them require intrinsics or much architecture-specific knowledge;
if any, rounding towards zero is supported in hardware
(§1.1.2. Hardware support for integer division),
and even if it isn't,
has to exist and the other rounding modes can be implemented in terms of it,
exactly the same.
5. Try it yourself
If you have JavaScript enabled, you can play around with the following code block.
has finite size.
Under the hood, calculations are performed using JavaScript's
6. Wording
All changes are relative to [N5008].
6.1. [structure.specifications]
In [structure.specifications] paragraph 3, add a bullet immediately following bullet 3.4:
- Preconditions: conditions that the function assumes to hold whenever it is called; violation of any preconditions results in undefined behavior.
- Hardened preconditions: […]
- Constant-checked preconditions: equivalent to a Preconditions specification, except that a function call expression that violates the assumed condition is not a core constant expression ([expr.const]).
Change [structure.specifications] paragraph 4 as follows:
Whenever the Effects element specifies that the semantics of some function
are Equivalent to some code sequence, then the various elements are
interpreted as follows.
If
's semantics specifies any Constraints or Mandates elements,
then those requirements are logically imposed prior to the equivalent-to semantics.
Next, the semantics of the code sequence are determined by the
Constraints,
Mandates,
Preconditions,
Hardened preconditions,
Constant-checked preconditions,
Effects,
Synchronization,
Postconditions,
Returns,
Throws,
Complexity,
Remarks, and
Error conditions
specified for the function invocations contained in the code sequence.
The value returned from
is specified by
's Returns element,
or if
has no Returns element,
a non-
return from
is specified by the
statements ([stmt.return]) in the code sequence.
If
's semantics contains a Throws,
Postconditions, or Complexity element,
then that supersedes any occurrences of that element in the code sequence.
6.2. [version.syn]
Change the synopsis in [version.syn] as follows:
6.3. [bit.pow.two]
Change [bit.pow.two] paragraph 5 as follows:
Preconditions: Constant-checked preconditions:
is representable as a value of type
.
Delete [bit.pow.two] paragraph 8:
Remarks: A function call expression that violates the precondition in the Preconditions: element is not a core constant expression ([expr.const]).
6.4. [numeric.ops.overview]
Change the synopsis in [numeric.ops.overview] as follows:
6.5. [numeric.sat.func]
Change [numeric.sat.func] paragraph 9 as follows:
Preconditions: Constant-checked preconditions:
is
.
Delete [numeric.sat.func] paragraph 11:
Remarks: A function call expression that violates the precondition in the Preconditions: element is not a core constant expression ([expr.const]).
6.6. [numeric.int.div]
Append a new subclause to [numeric.ops], following [numeric.sat]:
Integer division [numeric.int.div]
1
Constraints:
is a signed or unsigned integer type ([basic.fundamental]).
2
Constant-checked preconditions:
is well-defined.
3
Returns: , rounded towards zero.
.
— end note]
4
Constraints:
is a signed or unsigned integer type ([basic.fundamental]).
5
Constant-checked preconditions:
is well-defined.
6 Returns: , rounded away from zero.
7
Constraints:
is a signed or unsigned integer type ([basic.fundamental]).
8
Constant-checked preconditions:
is well-defined.
9 Returns: , rounded towards positive infinity.
10
Constraints:
is a signed or unsigned integer type ([basic.fundamental]).
11
Constant-checked preconditions:
is well-defined.
12 Returns: , rounded towards negative infinity.
13
Constraints:
is a signed or unsigned integer type ([basic.fundamental]).
14
Constant-checked preconditions:
is well-defined.
15 Returns: , rounded towards the nearest odd integer.
16
Constraints:
is a signed or unsigned integer type ([basic.fundamental]).
17
Constant-checked preconditions:
is well-defined.
18 Returns: , rounded towards the nearest even integer.
19
Constraints:
is a signed or unsigned integer type ([basic.fundamental]).
20
Constant-checked preconditions:
is well-defined.
21 Returns: , rounded towards the nearest integer. If two integers are equidistant, the result is the integer with lower magnitude.
22
Constraints:
is a signed or unsigned integer type ([basic.fundamental]).
23
Constant-checked preconditions:
is well-defined.
24 Returns: , rounded towards the nearest integer. If two integers are equidistant, the result is the integer with greater magnitude.
25
Constraints:
is a signed or unsigned integer type ([basic.fundamental]).
26
Constant-checked preconditions:
is well-defined.
27 Returns: , rounded towards the nearest integer. If two integers are equidistant, the result is the greater integer.
28
Constraints:
is a signed or unsigned integer type ([basic.fundamental]).
29
Constant-checked preconditions:
is well-defined.
30 Returns: , rounded towards the nearest integer. If two integers are equidistant, the result is the lower integer.
31
Constraints:
is a signed or unsigned integer type ([basic.fundamental]).
32
Constant-checked preconditions:
is well-defined.
33 Returns: , rounded towards the nearest integer. If two integers are equidistant, the result is the odd integer.
34
Constraints:
is a signed or unsigned integer type ([basic.fundamental]).
35
Constant-checked preconditions:
is well-defined.
36 Returns: , rounded towards the nearest integer. If two integers are equidistant, the result is the even integer.
37
Constraints:
is a signed or unsigned integer type ([basic.fundamental]).
38
Constant-checked preconditions:
is well-defined.
39 Returns: A result object where
is the quotient returned byquotient
anddiv_ rounding ( x , y ) -
is ifremainder
is signed, otherwise the integer congruent to modulo where is the width ofT
.T
to have well-defined behavior even when
has undefined behavior.
equals
.
40
Effects:
Equivalent to
.
is negative and
is nonzero.
— end note]
6.7. [simd.bit]
Change [simd.bit] paragraph 4 as follows:
Preconditions: Constant-checked preconditions:
For every […].
Delete [simd.bit] paragraph 6:
Remarks: A function call expression that violates the precondition in the Preconditions: element is not a core constant expression ([expr.const]).
7. References
Appendix A — Reference implementation
See below a simplified implementation for educational purposes,
which works exclusively with
.
See [GitHub] for the full implementation.