Lab 3 : Division Algorithms

1 Preliminaries

If you are using Python 2, add the following statement to the top of your file (if you don’t know which version you are using, there’s no harm in adding it anyway):

from __future__ import print_function

To run doctests, add the following to the bottom of your file:

if (__name__ == '__main__'):
  import doctest
  doctest.testmod()

2 Implementing the book proof

For integers \(a,b \in \mathbb{Z}\), we will call a remainder any r satisfying \(a = qb + r\) for some \(q \in \mathbb{Z}\). There are infinite such remainders. What we normally call the remainder is the least non-negative remainder: i.e., a remainder \(r\) such that \(0 \leq r < |b|\).

We assume throughout this section that \(a,b \in \mathbb{Z}\). .. and that \(b > 0\).

Exercise 1 Recall that the first step was to define a set \(R\) which is a subset of the remainders for \(a\) and \(a\). Each \(q \in \mathbb{Z}\) gives a different one. Define a function which computes a remainder for a given \(q\).

def remainder(a, b, q):
    """Given q computes a remainder for a and b.

    >>> remainder(9, 2, 0)
    9
    >>> remainder(3453, 23, 100)
    1153
    >>> remainder(1153, 23, 50)
    3

    """

Exercise 2 We further insisted that the remainders in \(R\) be nonnegative, so that we might find its minimum element. But in order for there to be a minimum, we needed to show that it was nonempty. Define a function which returns \(q\) paired with the corresponding nonnegative remainder. Assume that \(b > 0\). (Use Exercise 1.)

def nonneg_rem(a, b):
    """Computes a nonnegative remainder for a and b. Assumes b > 0.
    Returns the pair containing q and the corresponding
    remainder.

    Since we want x so that a - xb >= 0, we take x = -|a|.

    >>> nonneg_rem(5, 2)
    (-5, 15)
    >>> nonneg_rem(0, 2)
    (0, 0)
    >>> nonneg_rem(-5, 2)
    (-5, 5)

    """

Exercise 3 Finally, we took the minimum \(r \in R\) and its corresponding \(q\) (and proceeded to prove that these were unique). Define a function which returns \(q\) paired with the corresponding least nonnegative remainder. Assume that \(b > 0\). (Use Exercises 1 and 2.)

def least_nonneg_rem(a, b):
    """Finds least nonneg remainder. Assumes b > 0.

    >>> least_nonneg_rem(0, 5)
    (0, 0)
    >>> least_nonneg_rem(5, 2)
    (2, 1)
    >>> least_nonneg_rem(-5, 2)
    (-3, 1)
    >>> least_nonneg_rem(-5, 1)
    (-5, 0)

    """

Exercise 4 Generalize least_nonneg_rem so that we assume only that \(b \neq 0\). (Use Exercise 3.)

def div_alg(a, b):
 """Integer division of a by b. Returns the quotient paired with
 the remainder.  Assumes b =/= 0.

 >>> div_alg(0, 5)
 (0, 0)
 >>> div_alg(5, 2)
 (2, 1)
 >>> div_alg(-5, 2)
 (-3, 1)

 >>> div_alg(5, -2)
 (-2, 1)
 >>> div_alg(-5, -2)
 (3, 1)

 """

3 Printing a run of div_alg

In this section, we will write a program that lets us see div_alg run step-by-step.

Exercise 5 Define a function which returns the number of digits in the decimal representation of an integer.

def base10_len(a):
    """Number of digits in base 10 representation of integer a

    >>> base10_len(0)
    1
    >>> base10_len(9)
    1
    >>> base10_len(10)
    2
    >>> base10_len(-100)
    3

    """

Exercise 6 In this exercise, we will acquaint ourselves with some of Python’s string formatting functionality. It helps with tasks like printing nice tables of numbers of differing lengths.

If we want to print only a single number, all we have to do is

>>> print(5)
5

What if we want to print two numbers side-by-side with some space between? Then it’s up to us to convert the numbers to strings and add the space, before we print. Try

>>> "{0:d} {1:d}".format(5, 17)
'5 17'
>>> print("{0:d} {1:d}".format(5, 17))
5 17

Think of {0:d} as a first hole to fill with a number and {1:d} as a second hole to fill with a number. The arguments to format are the actual numbers to fill in (in order). An example with more holes to fill:

>>> "{0:d} {1:d} {2:d}".format(105, 17, 23423)
'105 17 23423'

Now let’s think about making a table. For a table, we need a fixed column width if the numbers are going to line up. Information about column width can be included as follows:

>>> "{0:5d} {1:4d} {2:7d}".format(105, 17, 234234)
'  105   17  234234'

In this example, we have set the column width corresponding to the first hole to be 5, to the second hole to be 4 and to the third hole to be 7.

Finally, what if we want to set the column width according to the length of, for example, an input number which may be different on different calls?

>>> "{0:{len_a}d}".format(105, len_a=10)
'       105'

This syntax puts a hole within a hole and gives it a name len_a. We fill it by supplying the keyword argument to format, len_a=10. 10 here can of course be a variable defined in the body of your function corresponding, say, to the length of the number.

>>> a = 105343
>>> len_a = base10_len(a)
>>> "{0:{len_a}d}".format(a, len_a=(len_a + 1))
' 105343'

Exercise 7 Define a function which prints a run of div_alg as a table. Each line of the table contains \(q\) and the result of calling remainder on \(a\), \(b\) and \(q\). For simplicity, you may assume that \(b > 0\). (Modify least_nonneg_rem by adding print statements and removing the return statement.)

def div_alg_table(a, b):
    """ Prints the each call to remainder as a line in a table
    during the execution of div_alg.

    >>> div_alg_table(-12,2)
    -12 12
    -11 10
    -10  8
     -9  6
     -8  4
     -7  2
     -6  0

    """

4 Inefficiency of div_alg

To analyze the efficiency of an algorithm, a standard approach is to compare the length of the input to the number of “steps” in the computation. Doing so rigorously belongs to a mathematical field of its own. But we can get a useful impression of efficiency just by running some experiments.

Exercise 8 Write a function which prints the decimal length of the input (which is the sum of the lengths of the two input integers) and also the number of steps div_alg_steps uses in evaluating that input. Here a step means a call to remainder. For simplicity, you may assume that \(b > 0\). (Modify least_nonneg_rem by removing the return statement and by adding a variable step initialized to 0 which is incremented by 1 each time remainder is called.)

def div_alg_steps(a, b):
    """Prints the length of the input and number of steps in a run of
    div_alg. Assumes b > 0.

    >>> div_alg_steps(10, 2)
    Length of input: 3
    Number of steps: 16
    >>> div_alg_steps(100, 2)
    Length of input: 4
    Number of steps: 151
    >>> div_alg_steps(1000, 100)
    Length of input: 7
    Number of steps: 1011

    """

Exercise 9 Experiment with div_alg_steps with inputs of various sizes (start small). For example, on my computer, the following takes several seconds to compute:

>>> div_alg_steps(10**7, 2)
Length of input: 9
Number of steps: 15000001

1. Give example inputs which would require hours on a standard PC / laptop. Justify.
2. Give example inputs which would require years on a standard PC / laptop. Justify.
3. Give example inputs which would require centuries on a standard PC / laptop. Justify.
4. The universe is supposed to die in \(10^{1000}\) years. Give example inputs for which there is not enough time left in the universe to compute.
5. If you haven’t already, give example inputs for 4 which you could easily evaluate in your head. Why is div_alg so inefficient?

5 Long Division

It’s possible that one reason you find div_alg’s inefficiency unacceptable is that you know how to perform division with remainder with pencil and paper in a relatively short period of time (e.g, well before the end of the universe).

The goal of this section is to write a program which performs decimal long division. If you are looking for a challenge, feel free to skip straight to Exercise 13 and try it yourself from scratch.

Exercise 10 Long division in fact involves a restricted form of remainder minimization. The main difference is that the search is limited to single digit quotients. Write a function which finds \(q \in \{0,1,\dotsc,9\}\) and \(r \geq 0\) so that \(a = qb + r\) and \(r\) is as small as possible. Assume that \(a \geq 0\) and \(b > 0\).

def one_digit_quot(a, b):
    """
    >>> one_digit_quot(100, 7)
    (9, 37)
    >>> one_digit_quot(100, 23)
    (4, 8)
    >>> one_digit_quot(100, 101)
    (0, 100)
    """

Exercise 11 Long division takes advantage of the fact that numbers can be encoded as sequences (or lists) of digits. Write a function encode which takes a nonnegative integer \(a\) and returns a list of its decimal digits. The function should take an optional argument z which pads on the left with zeros to give the encoding at least length z. (zfill is helpful for this).

def encode(a, z=0):
    """
    >>> encode(2346)
    [2, 3, 4, 6]
    >>> encode(0)
    [0]
    >>> encode(2346,7)
    [0, 0, 0, 2, 3, 4, 6]

    """

Exercise 12 Now write a function decode which takes a list of decimal digits and returns the corresponding integer.

def decode(l):
    """
    >>> decode([0])
    0
    >>> decode([0, 0, 3, 4])
    34

    """

Exercise 13 Lastly, implement unsigned long division. Here are the steps:

1. Encode \(a\) as enc_a.
2. Initialize q and r to empty lists.
3. Iterate over the enc_a as follows:
   1. Append the next digit of enc_a to the end of r. (This is “bringing down the next digit.”)
   2. Decode r and divide by \(b\) as in Exercise 10, returning q1 and r1.
   3. Update r to be r1 encoded to be the same length as r (padding as necessary).
   4. Append q1 to the end of q.
4. Decode q and r and return them as a pair.

def unsigned_long_div(a, b):

    """Integer division using long division base 10.
    Assumes a >= 0, b > 0.

    >>> unsigned_long_div(0, 5)
    (0, 0)
    >>> unsigned_long_div(250, 23)
    (10, 20)

    """

Finally, try out your unsigned_long_div on some large inputs. What do you think of its efficiency?