1.3. remainders in programming

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.

  1. Truncated division is division where the quotient is rounded towards zero. The corresponding modulus operator will yield a remainder whose sign matches the dividend.
    47 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
    
    For example, the % operator in C, Go, Rust, and Swift are based on truncation while the rem operator in Elixir, Haskell, and Lisp are based on truncation.
  2. 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.
    47 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
    
    For example, the % operator in Python and Ruby are based on floored division while the mod operator in Haskell and Lisp are based on floored division.
  3. 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.
    47 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
    
    For example, Rust provides Euclidean division functionality in the standard library via the div_euclid() and rem_euclid() integer methods.
  4. 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 $.
    47 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
    
    This is not as common, but the 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

  1. Using your language's modulus operator, write a more performant divides function that has the same output as the naive version from 1.1. divisibility

    Some 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
    solution
    module NumberTheory::Division
      def divides(b, a)
        b != 0 && a % b == 0
      end
    end
  2. 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]
    solution
    module NumberTheory::Division
      def div_rem(a, b)
        remainder = a % b
        remainder += b.abs if remainder < 0
        quotient = (a - remainder) / b
        [quotient, remainder]
      end
    end
  3. 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
    solution
    module NumberTheory::Division
      def div(a, b)
        div_rem(a, b).first
      end
    end
  4. 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
    solution
    module NumberTheory::Division
      def rem(a, b)
        div_rem(a, b).last
      end
    end