5.1 Arithmetic operations

Processes such as addition of numbers are called binary operations. (The word “binary” here reflects the fact that a binary operation combines two data items.) A binary operation is a particular form of function. To see this, we need to recognise the appropriate signature.

If you add two integers, then the resulting value is also an integer. So addition of integers takes two integers and returns an integer value. Thus adding integers is a function with signature Int × Int → Int. We can add any two integers, so addition is a total function (that is, has precondition true). We can describe a function, +, corresponding to addition of integers, as below.

function (infix) (x + y on Int) return in Int

pre   true.

post   The returned value is the result of adding x and y.

Where we use infix notation to write the value returned by a function, we will set out the signature line in the function description in a slightly different way from that used in Section 4, as illustrated above.

Activity 21

Describe a function, −, corresponding to integer subtraction written using infix notation.

We saw in Activity 3 that division of one integer by another does not necessarily result in an integer. For example, 2 ÷ 4 = 0.5 and 0.5 is not an integer. This means that we cannot define a function for what we might call “everyday division” that returns an integer value for integer inputs.

Sometimes, we need a form of division of integers that does yield an integer result. For example, suppose our supermarket features a special ‘buy 4, get 1 free’ order on bottles of wine. If a customer comes to the till with nine bottles of wine, then the till needs to calculate how many free bottles they should receive. Now nine bottles of wine contain two lots of four bottles (with one bottle left over). So the customer receives two free bottles of wine. This is an example of integer division. Integer division of 9 by 4 gives the result 2. (Hopefully, the cashier will point out to the customer with 9 bottles of wine that they are entitled to another free bottle!)

As another example, suppose that we want to perform integer division of 29 by 8. Now 3 × 8 = 24, while 4 × 8 = 32. When we perform integer division of 29 by 8 we obtain the result 3. Since 29 − 3 × 8 = 5, dividing 29 by 8 leaves a remainder of 5. Notice that the remainder, 5, satisfies the condition that 0 ≤ 5 < 8.

Integer division has two integers as input. It is a binary operation on Int, so we could use infix notation to write integer division. Now, many programming languages use / as an infix notation for both integer division and for real number division. In such cases, it is vital to appreciate that these are different processes, whose precise behaviour depends upon the type of the values supplied. To emphasise that integer division is not the familiar process of “everyday division”, we will write it as DIV, and use function rather than infix notation to give its values. For example, DIV (29, 8) = 3.

How can we describe integer division in general? To do this, some vocabulary is useful. In writing DIV (29, 8) = 3, the number 8 is called the divisor, and 3 is called the quotient.

We can generalise the equation 29 = 3 × 8 + 5 to give n = q × d + r (where d is the divisor, q is the quotient and r the remainder). The remainder must not be too large. In this example, the remainder 5 is less than 8. In general, the remainder r must be less than the divisor, d. Also, the remainder r is not negative. We can express these conditions on r algebraically as 0 ≤ r < d. So, in general, the quotient, q, is the largest integer by which we can multiply the divisor, d, while leaving a remainder that is not negative. If we subtract (q × d) from n, the resulting remainder needs to be non-negative and less than d.

Integer division has two integers as inputs and returns an integer. So the integer division function has signature DIV : Int × Int → Int. Since we write DIV using function notation, we can describe this function as below.

function DIV (n in Int, d in Int) return in Int

pre   d > 0.

post   The returned value q is the result of integer division of n by d. It satisfies the condition that if r = n − (q × d), then we have 0 ≤ r < d.

Notice that we only consider the case where the divisor, d, is strictly greater than 0. There is no restriction on the number n that is being divided, though. The examples we have considered so far have n positive.

What do these semantics give if n < 0? As an example, consider n = −29 and d = 8. We have −29 = −4 × 8 + 3 and the semantics give DIV (−29, 8) = −4. (Note that the remainder, r = 3, satisfies the condition 0 ≤ r < d, which is 0 ≤ r < 8 in this case.)

If n = 0, we have DIV (0, d) = 0 for any d that satisfies the precondition.

Activity 22

Give the following values:

• (a) DIV (27,4).
• (b) DIV (32,17).
• (c) DIV (−27, 4).
• (d) DIV (0,6).
• (e) DIV (3,0).

A second process associated with integer division returns the remainder rather than the quotient. This is again a binary operation. We will write this operation as MOD(n, d). This operation can be described as below.

function MOD(n in Int, d in Int) return in Int

pre   d > 0.

post   The returned value r is the remainder after integer division of n by d. It satisfies the conditions 0 ≤ r < d and r = n – (q × d), where q is an integer. The remainder MOD(n, d) is sometimes called the value of n modulo d, or more briefly n mod d. Many programming languages use the infix notation n % d for this operation.

Activity 23

Give the following values:

• (a) MOD(67, 10).
• (b) MOD(55, 5).
• (c) MOD(−27, 4).

Activity 24

• (a) Suppose that you buy 335 grams of walnuts at 299 pence per kg, and the price of this purchase is expressed as a whole number of pence by ignoring any fraction. What is the cost of this purchase?
• (b) Now consider a general purchase of this form, of weight grams of a product costing price pence per kilogram. Using the function DIV , give a formula for the cost of such a purchase.