Remainder

From Wikipedia, the free encyclopedia - View original article

 
Jump to: navigation, search

In arithmetic, the remainder (or modulus) is the amount "left over" after performing the division of two integers which do not divide evenly, that is, where the result of the division cannot be expressed as an integer.

For natural numbers[edit]

If a and d are natural numbers, with d non-zero, it can be proven that there exist unique integers q and r, such that a = qd + r and 0 ≤ r < d. The number q is called the quotient, while r is called the remainder. See Euclidean division for a proof of this result and division algorithm for algorithms describing how to calculate the remainder.

General case for integers[edit]

If a and d are integers, with d non-zero, then a remainder is an integer r such that a = qd + r for some integer q, and with |r| < |d|.

When defined this way, there are two possible remainders. For example, the division of −42 by −5 can be expressed as either

−42 = 9×(−5) + 3

as is usual for mathematicians,[citation needed] or

−42 = 8×(−5) + (−2).

So the remainder is then either 3 or −2.

This ambiguity in the value of the remainder can be quite serious computationally; for mission critical computing systems, the wrong choice can lead to dangerous consequences. In the case above, the negative remainder is obtained from the positive one just by subtracting 5, which is d. This holds in general. When dividing by d, if the positive remainder is r1, and the negative one is r2, then

r1 = r2 + d.

For floating-point numbers[edit]

When a and d are floating-point numbers, with d non-zero, a can be divided by d without remainder, with the quotient being another floating-point number. If the quotient is constrained to being an integer, however, the concept of remainder is still necessary. It can be proved that there exists a unique integer quotient q and a unique floating-point remainder r such that a = qd + r with 0 ≤ r < |d|. As in the case of division of integers, the remainder could be required to be negative, that is, −|d| < r ≤ 0.

Extending the definition of remainder for floating-point numbers as described above is not of theoretical importance in mathematics; however, many programming languages implement this definition—see modulo operation.

Satisfaction of an inequality[edit]

The way remainder was defined, in addition to the equality a = qd + r an inequality was also imposed, which was either 0 ≤ r < |d| or −|d| < r ≤ 0. Such an inequality is necessary in order for the remainder to be unique—that is, for it to be well-defined. The choice of such an inequality is somewhat arbitrary. Any condition of the form x < r ≤ x + |d| (or x ≤ r < x + |d|), where x is a constant, is enough to guarantee the uniqueness of the remainder.

In programming languages[edit]

With two choices for the inequality, there are two choices for the remainder, one negative and the other positive. This means that there are also two possible choices for the quotient. In number theory the positive remainder is chosen by convention. But programming languages need not, and different languages have adopted different conventions: Pascal goes with number theory in choosing the result of the mod operation positive (while not always a = (a div d )*d + a mod d ).[1] C99 chooses the remainder with the same sign as the dividend a. (Before C99, the C language allowed either choice.) Perl, Python (only modern versions), and Common Lisp choose the remainder with the same sign as the divisor d. Haskell and Scheme offer two functions, remainder and moduloPL/I has mod and rem, while Fortran has mod and modulo; in each case, the former agrees in sign with the dividend, and the latter with the divisor.

See also[edit]

References[edit]

  1. ^ Pascal ISO 7185:1990 6.7.2.2

Further reading[edit]