In this section, we connect divisibility and division with remainder to the division and modulus operations found in many programming languages, which enables us to write performant versions of our naive functions.
division schemes
Since division of an integer (the dividend) by a nonzero integer (the divisor) does not always yield an integer, we need a reliable scheme for producing an integer. This choice of integer division is often paired with a modulus or remainder operator.
We will write a div b
for the integer division of $ a $ by $ b $ and a mod b
for the corresponding modulus or remainder operation. These two operators are often
defined so that a == b * (a div b) + (a mod b)
, which looks very much like the quotient and remainder from the division algorithm.
However, depending on the scheme and the signs of the dividend and divisor, the quotient and remainder may or may not match those from the division algorithm. There are four typical schemes for defining integer division. Many programming languages will implement one or more of these.
- Truncated division is division where the quotient is rounded towards zero. The corresponding
modulus operator will yield a remainder whose sign matches the dividend.
For example, the47 div 10 ~> 4 47 mod 10 ~> 7 47 div -10 ~> -4 47 mod -10 ~> 7 -47 div 10 ~> -4 -47 mod 10 ~> -7 -47 div -10 ~> 4 -47 mod -10 ~> -7
%
operator in C, Go, Rust, and Swift are based on truncation while therem
operator in Elixir, Haskell, and Lisp are based on truncation. - Floored division is division where the quotient is rounded towards negative
infinity. The corresponding modulus operator will yield a remainder whose sign
matches the divisor.
For example, the47 div 10 ~> 4 47 mod 10 ~> 7 47 div -10 ~> -5 47 mod -10 ~> -3 -47 div 10 ~> -5 -47 mod 10 ~> 3 -47 div -10 ~> 4 -47 mod -10 ~> -7
%
operator in Python and Ruby are based on floored division while themod
operator in Haskell and Lisp are based on floored division. - Euclidean division is the division defined by the division algorithm from the
previous section. In particular, the quotient and remainder are defined so that
the remainder is always nonnegative.
For example, Rust provides Euclidean division functionality in the standard library via the47 div 10 ~> 4 47 mod 10 ~> 7 47 div -10 ~> -4 47 mod -10 ~> 7 -47 div 10 ~> -5 -47 mod 10 ~> 3 -47 div -10 ~> 5 -47 mod -10 ~> 3
div_euclid()
andrem_euclid()
integer methods. - Rounded division is division where the quotient is rounded to the nearest integer.
The corresponding modulus operator will yield a remainder closer to zero, ie, a
remainder $ r $ such that $ -|b|/2 < r <= |b|/2 $.
This is not as common, but the47 div 10 ~> 5 47 mod 10 ~> -3 47 div -10 ~> -5 47 mod -10 ~> -3 -47 div 10 ~> -5 -47 mod 10 ~> 3 -47 div -10 ~> 5 -47 mod -10 ~> 3
mods
operator in Maple uses rounded division, for example. There is also functionality based on rounded division in C and Swift, however it is floating point as opposed to integer functionality.
Note also that some languages provide combined division with remainder functionality,
for example divmod
in Python and Ruby or div_rem
in Rust.
exercises
- Using your language's modulus operator, write a more performant
divides
function that has the same output as the naive version from 1.1. divisibilitySome test values:
divides(15, 45) ~> true
divides(-15, 45) ~> true
divides(15, -45) ~> true
divides(-15, -45) ~> true
divides(10, 45) ~> false
divides(-10, 45) ~> false
divides(10, -45) ~> false
divides(-10, -45) ~> false
divides(7, 0) ~> true
divides(7, 7) ~> true
divides(7, -7) ~> true
divides(1, 7) ~> true
divides(-1, 7) ~> true
divides(0, 7) ~> false
solutionmodule NumberTheory::Division def divides(b, a) b != 0 && a % b == 0 end end
- Use your language's division and modulus operators to write a more performant
div_rem
function that has the same output as the naive version from the last section.Some test values:
div_rem(47, 10) ~> [4, 7]
div_rem(47, -10) ~> [-4, 7]
div_rem(-47, 10) ~> [-5, 3]
div_rem(-47, -10) ~> [5, 3]
div_rem(90, 10) ~> [9, 0]
div_rem(90, -10) ~> [-9, 0]
div_rem(-90, 10) ~> [-9, 0]
div_rem(-90, -10) ~> [9, 0]
div_rem(10, 47) ~> [0, 10]
div_rem(10, -47) ~> [0, 10]
div_rem(-10, 47) ~> [-1, 37]
div_rem(-10, -47) ~> [1, 37]
div_rem(0, 99) ~> [0, 0]
div_rem(0, -99) ~> [0, 0]
solutionmodule NumberTheory::Division def div_rem(a, b) remainder = a % b remainder += b.abs if remainder < 0 quotient = (a - remainder) / b [quotient, remainder] end end
- Write a
div
function that returns the quotient from the division algorithm, respectively.Some test values:
div(47, 10) ~> 4
div(47, -10) ~> -4
div(-47, 10) ~> -5
div(-47, -10) ~> 5
div(90, 10) ~> 9
div(90, -10) ~> -9
div(-90, 10) ~> -9
div(-90, -10) ~> 9
div(10, 47) ~> 0
div(10, -47) ~> 0
div(-10, 47) ~> -1
div(-10, -47) ~> 1
div(0, 99) ~> 0
div(0, -99) ~> 0
solutionmodule NumberTheory::Division def div(a, b) div_rem(a, b).first end end
- Write a
rem
function that returns the quotient from the division algorithm, respectively.Some test values:
rem(47, 10) ~> 7
rem(47, -10) ~> 7
rem(-47, 10) ~> 3
rem(-47, -10) ~> 3
rem(90, 10) ~> 0
rem(90, -10) ~> 0
rem(-90, 10) ~> 0
rem(-90, -10) ~> 0
rem(10, 47) ~> 10
rem(10, -47) ~> 10
rem(-10, 47) ~> 37
rem(-10, -47) ~> 37
rem(0, 99) ~> 0
rem(0, -99) ~> 0
solutionmodule NumberTheory::Division def rem(a, b) div_rem(a, b).last end end