6

I was wondering which are the benefits of using truncation towards minus infinity (Haskell, Ruby) instead of truncation towards zero (C, PHP), from the perspective of programming languages/compilers implementation.

It seems that truncating towards minus infinity is the right way to go, but I haven’t found a reliable source for such claiming, nor how such decision impact the implementation of compilers. I’m particularly interested in possible compilers optimizations, but not exclusively.

Related sources:

Division in Haskell

When is the difference between quotRem and divMod useful?

Community
  • 1
  • 1
rla4
  • 1,228
  • 13
  • 25

3 Answers3

9

These actually are not even the only choices and, in fact, maybe not even usually the best. I could summarize here, but it is perhaps better to just link to this excellent paper that contrasts truncate, floor, and Euclidean division, covering the theory and some real world applications, The Euclidean Definition of Functions div and mod, Raymond T. Boute.

Leon Noordam
  • 73
  • 6
Jake McArthur
  • 894
  • 4
  • 8
  • The paper's conclusion is a bit more concrete. It states that truncation towards minus infinity (called F-definition) is the **only** comparable (in desirable properties) to the E-definition. – false Nov 14 '13 at 18:20
  • And both truncation towards minus infinity and this "Euclidean" definition are identical for positive divisors (that is, both `div` and `mod` are the same). The difference shows only for negative divisors. – false Nov 14 '13 at 19:18
5

Here is a quote from the (informative) Rationale in Annex C of ISO/IEC 10967-1:2012 Language independent arithmetic (vl. LIA-1) C.5.1.2.2. Ellipsis ... inserted by me.

... Two rounding rules are in common use: round toward minus infinity (quotI), and round toward zero. The latter is not specified in LIA-1, due to proneness for erroneous use, when the arguments are of different signs. For example,

quotI(-3,2) = -2    round toward minus infinity, specified in LIA-1

divtI(-3,2) = -1     round toward zero, no longer specified by any part of LIA

quotI ... as well as ... all satisfy a broadly useful translation invariant:

   quotI(x + i * y, y) = quotI( x, y) + i    if y ≠ 0, and no overflow occurs

... quotI is the form of integer division preferred by many mathematicians. divtI (no longer specified by LIA) is the form of division introduced by Fortran.

Integer division is frequently used for grouping. For example, if a series of indexed items are to be partitioned into groups of n items, it is natiural to put item i into group i/n. This works fine if quotI is used for integer division. However if divtI (no longer specified in LIA) is used, and i can be negative, group 0 will get 2 ⋅ n-1 items rather than the desired n. This uneven behaviour for negative i can cause subtle program errors, and is a strong reason against the use of divtI ...

Community
  • 1
  • 1
false
  • 10,264
  • 13
  • 101
  • 209
  • 3
    I can't think of any time I've found round-toward-zero, nor the associated remainder function, useful. Further, the only code I can think of where the a==(a/b)*b + a%b guarantee was useful was code which was trying to work around the fact that division uses round-toward-zero. Another place where round-toward-negative-infinity wins, btw: computing things like the rounded average of three numbers. The expression `(a+b+c+1)/3` works nicely if the average is positive, or if one is using round-toward-negative-infinity division. How would one do the equivalent with round-toward-zero? – supercat Nov 13 '13 at 20:41
  • 1
    @supercat: It needs to be repeated over and over again :-) – false Nov 28 '13 at 17:48
4

There are various trade-offs with the different kinds of rounding in integer division. And as Jake McArthur mentioned, this is not the only ones. For example, there's also rounding to the nearest integer.

Another consideration is that integer division and remainder go hand-in-hand. The quotient * divisor + remainder = dividend law holds. So different types of division rounding will produce different types of remainder. For example:

  • Division rounding towards zero, produces a remainder that always has the same sign as the dividend. For example, in C and Java, (-5) % 3 = -2 (because (-5) / 3 = -1, and (-1) * 3 + (-2) = -5); whereas 5 % (-3) = 2 (because 5 / (-3) = -1, and (-1) * (-3) + 2 = 5).
  • Division rounding towards negative infinity, produces a remainder that always has the same sign as the divisor. For example, in Python and Ruby, (-5) % 3 = 1 (because (-5) / 3 = -2, and (-2) * 3 + 1 = -5); whereas 5 % (-3) = -1 (because 5 / (-3) = -2, and (-2) * (-3) + (-1) = 5).
  • Division rounding towards the nearest integer, produces a remainder (out of the two possible ones) that is the smallest (closest to zero).

Having a remainder with the same sign as the divisor is often the most useful in math and computer science. One often needs to compute the remainder with a fixed divisor. For example, x % 2. In languages where the remainder has the sign of the dividend, like C and Java, this expression could evaluate to -1, 0, or 1, depending on x. However, in languages where the remainder has the sign of the divisor, like Python and Ruby, this expression could only evaluate to 0 (if even) or 1 (if odd). This is probably much more in line with what is intended.

I believe that many processor architectures, including the x86 architecture, contains an instruction for integer division that rounds towards zero. So it may be more efficient to compute this on most computers. I am not sure if there is an instruction for integer division that rounds towards negative infinity.

newacct
  • 119,665
  • 29
  • 163
  • 224
  • 1
    There isn't an x86 instruction for integer division by arbitrary divisors that rounds toward negative infinity, but there is an instruction for dividing signed numbers by powers of two which does so (arithmetic right shift). Further, for many constant divisors, round-toward-negative-infinity division could be performed with four fast instructions (load, multiply, add, shift), but round-toward-zero makes things slower and more complicated. – supercat Nov 13 '13 at 20:36
  • Clearly just a small typo, but where you wrote `5 % (-3) = 1` I think you meant `5 % (-3) = -1` (tested in python) – Joshua Perrett Oct 04 '21 at 16:38
  • 1
    @JoshuaPerrett: fixed – newacct Oct 04 '21 at 20:06