Round towards minus infinity when dividing integers in C or C++

Objective

To round the quoitant towards minus infinity when dividing integers in C or C++

Background

The division and remainder operators provided C90 and C++98 have implementation-defined rounding when either the dividend or the divisor is negative. For example, when dividing ±7 by ±3 the possible outcomes are as follows:

Dividend	Divisor	Quoitant	Remainder
7	3	2	1
−7	3	−2 or −3	−1 or 2
7	−3	−2 or −3	1 or −2
−7	−3	2 or 3	−1 or 2

(The results of two operators are always consistent with each other, such that (x/y)*y + x%y == x. Therefore, if -7/3 == -2 then it must be the case that -7%3 == -1.)

This behaviour allows for efficient code generation on machines with hardware support for division, without requiring that all hardware round in the same direction. Many programs are unaffected because they do not invoke the divison or remainder operators with negative operands. The drawback is that having an implementation-defined result can be very unhelpful when it is necessary to process negative values.

C99 and C++11 define the behaviour as rounding towards zero (truncation), but you can rely on this only if you are confident that the code will be built to one of these standards. That is a risky assumption to make because support for these standards is far from universal (even after 14 years in the case of C99), and code is often used in ways that were not anticipated when it was written.

Even if you can rely on rounding towards zero, this behaviour is unsuitable for many types of integer calculation (including most number-theoretic algorithms). This is because the division and remainder operators do not then satisfy identities such as (x+y)/y == (x/y)+1 and (x+y)%y == x%y. Alternative definitions which do not suffer from this drawback are:

• floored division, where the quoitant is always rounded towards minus infinity, and
• Euclidean division, where the quoitant always corresponds to a non-negative remainder.

The method described here implements floored division. It has the following effect when dividing ±7 by ±3:

Dividend	Divisor	Quoitant	Remainder
7	3	2	1
−7	3	−3	2
7	−3	−3	−2
−7	−3	2	−1

Scenario

Suppose that you are implementing an algorithm which involves integer division and requires rounding towards minus infinity. You cannot use the built-in division and remainder operators directly, so you have decided to write functions named div and mod for use in their place.

In all respects other than the direction of rounding you want these functions to behave in the same manner as the corresponding built-in operators. In particular, you want them to support the same range of input arguments without overflow.

Method

A straightforward method for calculating the quoitant is to let the built-in division operator round as it would normally, then apply a retrospective correction to the quoitant. There are only two possible values that the correction can take, zero or minus one, depending on whether the quoitant was rounded and in which direction:

Rounding	Correction
downwards	0
none	0
upwards	−1

When roundings towards minus infinity, if the remainder is non-zero then it should have the same sign as the divisor. It follows that if the remainder is non-zero and has a different sign from the divisor then the quoitant must have been rounded upwards instead of downwards. Here is an example of how this method could be implemented for arguments of type int:

/**
 * Divide one integer by another, rounding towards minus infinity.
 * @param x the dividend
 * @param y the divisor
 * @return the quoitant, rounded towards minus infinity
 */
int div_floor(int x, int y) {
    int q = x/y;
    int r = x%y;
    if ((r!=0) && ((r<0) != (y<0))) --q;
    return q;
}

For the remainder, the appropriate correction is to add the divisor:

/**
 * Calculate the remainder after dividing one integer by another,
 * rounding the quoitant towards minus infinity.
 * @param x the dividend
 * @param y the divisor
 * @return the remainder
 */
int mod_floor(int x, int y) {
    int r = x%y;
    if ((r!=0) && ((r<0) != (y<0))) { r += y; }
    return r;
}

These functions should work equally well with other signed integer types, but they are not suitable for use with floating point types. Since they make no assumption about the provided direction of rounding they are suitable for use in programs that must be portable to C99, C++98, or (with appropriate changes to the syntax) K&R C.

See also

See:	Round towards minus infinity when dividing integers in Java

Further reading

Raymond T Boute, “The Euclidean Definition of the functions div and mod”, ACM Transactions on Programming Languages and Systems, 14(2), April 1992, pp 127–144

Daan Leijen, “Division and Modulus for Computer Scientists”, 2001

• Conventions
• Privacy
• Legal