Signed Integer Division#
by Robert L. Smith
Originally appearing in Dr. Dobb's Journal September 1983
Not all methods of integer division produce a uniform result when the dividend and divisor have opposite signs. This may not be so important in the area of commerce where negative values are perhaps used less. When dealing with measurement and control, however, uniformity becomes more significant. The Forth-83 Standard adopts a method for signed integer division called "floored" division. While APL has used this method for the RES function for years and Small-Talk provides it as one of three methods for integer division, acceptance of the Standard makes Forth the first "popular" language to embrace this method based on its theoretical merits. The problem is one of mathematical purity versus user expectation. This article will attempt to clarify some of the issues involved.
Integer division is a mathematical function of two integers (a dividend and a divisor) that yields an integer quotient and an integer remainder. That appears to be a fairly straightforward operation, but there is not universal agreement of the desired results when one or both arguments are negative. When an ingeger quotient is used in plotting or machine control, the desired function is usually _not_ the quotient given by the majority of computers.
Most computers with a divide function produce a quotient that has a property of symmetry around zero when plotted as a function of the dividend, due to the fact that the quotient is rounded toward zero. Speaking mathematically, the property is actually one of anti-symmetry, where the sign of the quotient is reversed when the sign of the dividend (or numerator) is reversed. For integer division, this "symmetric" property leads to a sort of discontinuity around zero. In this case, the remainder is either zero or it takes the sign of the dividend. Figure 1a illustrates the quotient q as a function of a variable dividend, and a constant divisor 3. We readily see the discontinuity near zero. This may
+-------------------------------------------------------+ | | | 3 + o o o | | + o o o | | -9 + o o o 9 | | +-+-+-+-+-+-+-+-+-o-o-o-o-o-+-+-+-+-+-+-+-+-+- | | o o o + | | o o o + | | o o o -3 + | | | | (a) Quotient for Symmetric Integer Division | | | | | | | | + | | 2 + o o o o | | -9 + o o o o | | +-+-o-+-+-o-+-+-o-+-+-o-+-+-o-+-+-o-+-+-o-+-+- | | o o o o + 9 | | o o o o + -2 | | + | | | | (b) Remainder for Symmetric Integer Division | | | | Figure 1. | |_______________________________________________________|
be reasonably serious when this quotient function is used for plotting or moving robot arms. The integer quotient needs an associated remainder:
r = n - q * dwhere n is the numerator or dividend, d is the denominator or divisor, q is the quotient, and r is the remainder. The remainder function for the constant divisor 3 is illustrated in Figure 1b. If we look at the case of positive dividends and divisors, we observe the cyclic property that
r(n+d) = r(n)In other word, the remainder usually has a repeating or cyclical property as the dividend changes. For the remainder shown in Figure 1b, we see that this simple property is not maintained for dividends between -d and 0.
If we require that the remainder be cyclical, then the quotient no longer has any unusual discontinuities. There are a number of possible choices here. One obvious choice is to make the remainder the same as the modulus or residue function (1). In this case the quotient is rounded toward minus infinity. This rounding procedure is called the "floor" function. Figure 2 shows the floored quotient and its related modulus for the same arguments used in Figure 1. Notice the quotient behaves in a more nearly continuous fashion around zero. This is the form used in the Forth-83 Standard, as well as some of the older versions of Forth. The National 16032 microprocessor produces floored division in addition to the older "rounded toward zero" variety. The modulus function is called MOD in Forth-83 and in the National 16032. It is called RES in APL.
+-------------------------------------------------------+ | | | 3 + o o o | | + o o o | | -9 + o o o 9 | | +-+-+-+-+-+-+-+-+-+-+-o-o-o-+-+-+-+-+-+-+-+-+- | | o o o + | | o o o + | | o o o -3 + | | | | (a) Quotient for Floored Integer Division | | | | | | | | + | | o o o + o o o o | | -9 o o o + o o o o | | +-+-o-+-+-o-+-+-o-+-+-o-+-+-o-+-+-o-+-+-o-+-+- | | + 9 | | + -2 | | + | | | | (b) Remainder for Floored Integer Division | | | | Figure 1. | |_______________________________________________________|
The "floored" quotient shown in Figure 2 is not anti-symmetric around zero. However, for odd divisors one may easily obtain a symmetric result by adding a correction factor to the dividend prior to division. Although the quotient is generally not defined when the divisor is zero, the modulus is usually defined to take the value of the dividend for this case. If infinities are not allowed in computer representations, and the product of any number and zero is always zero, then this definition preserves the equation
n = q * d + rfor all values of d, including zero.
Alternative remainder functions include a positive modulus and a remainder that takes the sign of the quotient (2). Some other possibilities have the undesirable feature of negative remainders when the dividend and divisor are both positive.
Floored division is simply more useful in the majority of applications programs. The major objection is that the results are not what most people expect: -1 divided by 4 gives 0 in the rounded-toward-zero division case, but -1 for floored division. Both cases give the same results when the dividend and divisor have the same sign. Timing efficiencies may play a small role in deciding which form of division to use, but generally the division process is sufficiently slow that additional tests for different forms of rounding take only a little extra time. Indeed, for some processors with built-in signed and unsigned divide functions, it may be faster in the common case of positive arguments to test signs and use the unsigned division than to just use the signed division function. If you have an older Forth system (such as 79-Standard or fig-FORTH), the screen in Figure 3 shows a high-level conversion from the older form of /MOD to the newer version. For those unfamiliar with Forth, /MOD takes two arguments, the dividend and the divisor, and returns two results: the quotient and the modulus, or remainder. The quotient is returned as the most accessible element on the stack.
The appearance of floored division in some of the newer processor chips and languages indicates the increasing awareness of its utility. We might note in passing that even floating-point division will probably be different in the future than it was in the past due to the new Floating-Point Standard, which will require proper rounding of the quotient.
References (1) Donald K. Knuth, _The Art of Computer Programming: Volume I, Fundamental Algorithms_, Second Edition, Menlo Park: Addison-Wesley, 1973, p. 127.
(2) Robert Berkey, "Integer Division, Rounding and Remainders", 1982 FORML Conference Proceedings, San Jose, California: Forth Interest Group, 1983, pp. 13-23.
+---------------------------------------------------------------+ | | | ( Define 83-Standard /MOD in terms of old /MOD ) | | : /MOD ( num den -- mod quot ) | | OVER OVER XOR 0< ( test signs of arguments ) | | IF ( signs are different ) | | >R R@ /MOD OVER ( divide and examine remainder ) | | IF ( non-zero remainder ) | | 1- SWAP R> + SWAP ( adjust results ) | | ELSE ( zero remainder ) | | R> DROP ( discard old den ) | | THEN | | ELSE ( signs just the same ) | | /MOD ( just divide normally ) | | THEN ; ( end of definition ) | | | | | | Figure 3. | | High Level Forth Code to Convert to Floored Division | |_______________________________________________________________|
