Topics

Round towards minus infinity when dividing integers in Java

Content

1 Objective
2 Background
3 Scenario
4 Method
5 Alternatives
- 5.1 Correcting the quoitant without calculating the remainder
6 See also
7 Further reading

Tested on

OpenJDK (6, 7)

Objective

To round the quoitant towards minus infinity when dividing integers in Java

Background

The division and remainder operators provided by Java round the quoitant towards zero when acting on integers. For example, when dividing ±7 by ±3 the effect is as follows:

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

This behaviour is called ‘truncation’ because it amounts to discarding any digits of the quoitant located after the radix point. Many programming languages round by truncation, but that makes the division and remainder operators unsuitable for some types of calculation because they do not 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

It is possible to deduce what the direction of rounding would have been given the remainder, and given the sign of the unrounded quoitant:

Remainder	Unrounded quoitant	Direction
zero	n/a	none
non-zero	positive	downwards
non-zero	negative	upwards

The unrounded quoitant is negative if either the dividend or divisor is negative, but not if they both are. It is unfortunately not sufficient to examine the sign after rounding, as a value of zero could have been either positive or negative beforehand.

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
 */
private static int div(int x, int y) {
  int q = x/y;
  if ((x%y != 0) && ((x < 0) != (y < 0))) --q;
  return q;
}

If the remainder is non-zero then it should have the same sign as the divisor. Where it has the wrong sign it can be corrected by adding 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
 */
private static int mod(int x, int y) {
  int r = x%y;
  if (((r < 0) && (y > 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.

Alternatives

Correcting the quoitant without calculating the remainder

An alternative method for calculating the quoitant is to add an offset to the dividend before performing the division. This can be either instead of or in addition to applying a correction afterwards. Doing so avoids the need to make a distinction between arguements that divide exactly and those which do not, with the consequence that the div function need not calculate the remainder. Use of this technique can improve performance when the code is executed using a Java bytecode interpreter, but is likely to have the opposite effect when using an optimising JIT compiler.

Adding an offset to the dividend shifts the cut-off point at which rounding occurs. As previously, this action is necessary only when the unrounded quoitant is negative. There is a choice to be made as to the value of the offset:

An offset of one less than the magnitude of the divisor, applied in the direction that makes the quoitant more negative, yields the required quoitant directly. Unfortunately this results in an overflow for some inputs, so is not recommended.
An offset of one, applied in the direction that makes the quoitant more positive, yields a quoitant that is off by one. This must then be corrected, but the scope for overflow is greatly reduced, and can be eliminated entirely by reflecting the dividend onto the negative half of the number line when it would otherwise be positive.

Here is an implementation for arguments of type int, with offsets chosen to avoid overflow. It is adaptable for use with other signed twos-complement integer types:

private static int div(int x, int y) {
  if (y >= 0) {
    if (x >= 0) return x/y;
    else return ((x+1)/y)-1;
  } else {
    if (x > 0) return -1-((1-x)/y);
    else return x/y;
  }
}

As noted above, use of this method does not necessarily improve performance. For example, the table below shows the result of some measurements made using the HotSpot JIT compiler that is part of OpenJDK-6, with and without compilation enabled:

	JIT comiler	Interpreter
Using remainder	7.3 ns	62 ns
Double offset	9.2 ns	50 ns

A likely explanation for these results is as follows. If the underlying method for calculating the quoitant is based on long division then it is usually possible to obtain the remainder at the same time at little or no extra cost. However, since Java bytecode does not provide a combined division and modulus instruction, it would be impracticable for the interpreter to take advantage of this possibility. The JIT compiler acts on the same bytecode, but has greater freedom to choose how it is executed. Provided that it can recognise that the divisor and dividend are the same for both operations, there is nothing to prevent it from merging them into a single operation.

For most purposes it will probably not make sense to optimise against the use of a JIT compiler, however you should consider using this alternative method if it is more important to constrain the worst case performance than to improve the typical case.

Topics

Rate this page

Round towards minus infinity when dividing integers in Java

Content

Tested on