Important functions in CS: mod, ceiling, floor

Here's a brief explanation about how the / and % operators work when given two integers in C, C++ or Java.

x/y evaluates to |x|/|y| using integer division and with the correct sign attached (if x and y are the same sign then the result is positive, otherwise it's negative).

11/4   ==> 2
-11/4  ==> -2
11/-4  ==> -2
-11/-4 ==> 2

And x%y evaluates to whatever you have to add to (x/y)*y to get x (commonly known as the "remainder after division").

xxxxxxxxxx
11%4   ==> 3    Because 2*4 + 3 = 11
-11%4  ==> -3   Because -2*4 + -3 = -11
11%-4  ==> 3    Because -2*-4 + 3 = 11
-11%-4 ==> -3   Because 2*-4 + -3 = -11

Modular reduction or "mod"

Some people call % the "mod" operator because it is closely related to "modular reduction" in mathematics. In fact x%y is exactly the same as "x reduced modulo y" (usually just called "x mod y") when x and y are both positive integers, which is the most common case for %. This section explains the difference between x%y and x mod y.

x mod y is only defined when y is positive, and the result is never negative. So right away that means three out of the four examples above for % disagree with modular reduction.

Division Algorithm

To calculate x mod y you follow what's known as the "division algorithm". Given any integer x and positive integer y, x mod y is the value r that results from finding the unique integers q and r that satisfy

Note that when x and y are positive, q is the quotient resulting from integer division x/y and r is the remainder after that division, and so this process yields the same thing as q = a / b and r = a % b. When x is negative and y is positive, however, q may need to be 1 bigger so that yq is a more negative number than x, allowing r to be positive. So, whereas -11%4 = -3, we get -11 mod 4 = 1 from q=-3 and r=1.

Practice Exercises

What are 20%3, -20%3, 20%-3, and -20%-3? Verify your work by demonstrating x = (x/y)*y + r where r is your answer.

Use the division algorithm to find 20 mod 3, and -20 mod 3. Verify your work by demonstrating x = yq + r.

Use the division algorithm to find 20 mod 4, and -20 mod 4. Verify your work by demonstrating x = yq + r.

Application

Modular arithmetic is used extensively in cryptography. For example, to authenticate that a document hasn't been altered it is common to break the document's data into 96-bit chunks, treat each chunk as a 96-bit number, and then do a big mathematical computation with the numbers and reduce the result modulo $2^{128}-1$.

Because the mathematical calculation can have intermediate results that are very very big, it is useful that intermediate results can be reduced at-will (making them smaller) without changing the final result. Here are a couple of theorems stating exactly what I mean.

Theorem: Suppose x, y, and n are natural numbers. Then, (x+y) mod n = [(x mod n)+(y mod n)] mod n.

Theorem: Suppose x, y, and n are natural numbers. Then, (xy) mod n = [(x mod n)+(y mod n)] mod n.

The reason this is useful, is it allows you to break a large problem involving mod into smaller ones.

Example: $2^{20} \bmod 5 = [(2^{10})(2^{10})] \bmod 5 = [(2^{10} \bmod 5)(2^{10} \bmod 5)] \bmod 5$. Since I happen to know $2^{10} = 1024$ and that $1024 \bmod 5 = 4$, I can substitute and get $[(2^{10} \bmod 5)(2^{10} \bmod 5)] \bmod 5 = [(4)(4)] \bmod 5 = 16 \bmod 5 = 1$. If I go to wolframalpha.com and type "2^20 mod 5" it confirms that 1 is the correct answer.

Practice Exercises

Calculate $3^{10} \bmod 10$ by using laws of exponents and the above theorem to mod intermediate results and simplify the computation. Verify your answer using WolframAlpha.

Calculate $7^8 \bmod 10$ using the same method.

Calculate $(3^{10} + 7^8) \bmod 10$.

Other common functions: ceiling, floor

These two functions are rounding functions. Both take a real number and return an integer. Floor always rounds towards negative infinity (ie, rounds down "toward the floor") and ceiling always rounds toward positive infinity (ie, rounds up "toward the ceiling").

Sometimes these function names are spelled out (eg, floor(1.5) or ceil(-2)), but more commonly symbols that suggest the ceiling or floor of a room are used. So, $\lfloor 1.5 \rfloor$ for floor(1.5) and $\lceil 2 \rceil$ for ceil(-2).

Example: floor(10) = $\lfloor 10 \rfloor$ = 10. No rounding needed for integers. floor(10.1) = $\lfloor 10.1 \rfloor$ = 10. Round toward negative infinity. floor(-10.1) = $\lfloor -10.1 \rfloor$ = -11. Round toward negative infinity.

ceil(10) = $\lceil 10 \rceil$ = 10. No rounding needed for integers. ceil(10.1) = $\lceil 10.1 \rceil$ = 11. Round toward positive infinity. ceil(-10.1) = $\lceil -10.1 \rceil$ = -10. Round toward positive infinity.

Practice Exercises

What are $\lfloor \pi \rfloor$, $\lfloor -\pi \rfloor$, $\lceil \pi \rceil$, $\lceil -\pi \rceil$?