Hunter Liu's Website

5. Week 3 Tuesday: Problems with Division and the Modulo Operator

One of the great triumphs of cave mathematics was the realisation that the sum, difference, and product of two integers is an integer. Thus, when we add, subtract, or multiply two int’s in C++, we get an int back.

One of the great pains of learning how to program in C++ is dealing with the fact that dividing two integers gives you an integer, whereas the quotient of two integers need not be an integer. It turns out that the people designing the language had a reason for this, and those reasons come up again and again all throughout programming.

Let’s begin with an example. Consider the following snippet of code:

1int a = 10, b = 6; 
2double c = 6.0; 
3
4cout << a / b << endl; 
5cout << a / c << endl;

This prints the numbers 1 and 1.66667 to the screen. The first output is the result of a / b, which is division between two integers, while the secound output is the result of a / c, which is the division between an integer and a decimal. Even though we humans can tell that the two expressions are the same (we are dividing ten by six), the computer distinguishes between dividing two integers and dividing by a decimal number.

An arithmetic operator is +, -, *, or /, which do what we expect them to do. These are the rules for them:

• Applying any arithmetic operator to two int’s produces an int. That is, the sum, difference, product, and quotient of two int’s is always an int (unless dividing by zero).
• If a and b are integers and b is nonzero, then the result of a / b is truncated, i.e. the decimal portion is lopped off. 6 / 5 is 1.2, but the decimal is cut off, and we’re left with 1 as the result. This works on negative numbers too: -9 / 2 is -4.5, and the decimal is cut off to -4.
• Applying any arithmetic operator to at least one double produces a double. That is to say, the sum of an integer and a double is a double; the quotient of a double and an integer is a double; etc.

So, dividing two integers doesn’t always produce the result that we expect, but under what circumstances is this actually useful? Why not just use doubles for every number, and use the cmath functions ceil, floor, and round as necessary?

Consider this example problem:

Sample run: 
INPUT   20.15
OUTPUT  80 quarters, 1 dime, 1 nickel, 0 pennies. 

Note 2015 pennies is not the right answer. One may first convert the quantity $20.15 into 2015 cents. Then, the number of quarter one needs is the largest integer that’s smaller than the quantity \(\frac{2015}{25} \). In C++, that would just be 2015 / 25.

Double Trouble and the Modulo Operator

“Okay,” says the unconvinced student. “You could have just done floor(20.15 / 0.25); and it would have given you the same result.”

Great point, unconvinced student! There are two issues with that:

1. We will eventually do a similar computation for the nickels. Try printing the result of floor(20.15 / 0.05);, which tells you that you need 402 nickels to make $20.15. This is an example of a very slight inaccuracy with doubles interfering with the results. This will not happen with integer division.
2. We still need to work with the remaining money! We could do this in several lines: compute the number of quarters needed, then subtract 0.25 * quarters from the money inputted by the user. But there’s a considerably faster way to do this: the modulo operator.

The modulo operator is the % operator, and it (in short) computes the remainder of an integer division. For instance, 2015 % 25 = 15: when you divide 2015 be 25, you get 80, with 15 left over. More formally, the quantity a % b is defined as the number that makes the equation a = (a / b) * b + a % b true for any int’s a and b. Remember this equation: it will allow you to determine the output of a % b when either a or b are negative!

So, let’s write pseudocode for the example problem.

1. Take a decimal input money from the user.
2. Define the integer cents = money * 100.
3. Set the number of quarters to quarters = cents / 25. Replace cents with cents % 25.
4. Repeat step 3 for the dimes and nickels.
5. The value of cents at this step is now the number of pennies.
6. Print out the results.

1double d = 20.15; 
2int i1 = d * 100;        // truncates d * 100
3int i2 = floor(d * 100); 
4int i3 = round(d * 100); 
5int i4 = ceil(d * 100); 

With that out of the way, let’s code our solution:

 1#include <iostream>     // needed for cout, cin, endl 
 2#include <cmath>        // needed for round
 3
 4using namespace std; 
 5
 6int main() {
 7    // step 1 - ask user for money 
 8    double money; 
 9    cin >> money; 
10
11    // step 2 - convert to an integer number of cents 
12    int cents = round(money * 100); 
13
14    // steps 3 & 4 - obtain # of quarters, dimes, etc. 
15    int quarters = cents / 25; 
16    cents = cents % 25; 
17
18    int dimens = cents / 10; 
19    cents = cents % 10; 
20
21    int nickels = cents / 5; 
22    cents = cents % 5; 
23
24    // step 5 - current value of cents is the # of pennies 
25    int pennies = cents; 
26
27    // step 6 - print results! 
28    cout << quarters << " quarter(s), "
29         << dimes << " dime(s), "
30         << nickels << " nickel(s), "
31         << pennies << " penny(ies)." << endl; 
32
33    return 0; 
34}

Sample run: 
INPUT   30.3571 
OUTPUT  7 

INPUT   -39.82113
OUTPUT  1

INPUT   5
OUTPUT  0 

There are two things to remark about the modulo operator:

1. It’s a great way to test for divisibility. If a and b are integers, then a is divisible by b exactly when a % b == 0. Does this still work for negative numbers? Can you see why?
2. The utility of the modulo operator is only available to integers. Why doesn’t it work for doubles?

The first remark there is particularly difficult to implement with doubles alone, especially with the issue of finite precision! Do not try to do this with doubles.

Sample Run: 
INPUT   7
OUTPUT  <empty> 

INPUT   5
OUTPUT  Buzz

INPUT   4873140
OUTPUT  FizzBuzz

Sample run: 
INPUT   60
OUTPUT  13:00

INPUT   -381
OUTPUT  05:39