1
What are the inputs and outputs of the algorithms listed in the first sentence of this section?
Computer programs, bicycle assembly instructions, knitting instructions, and recipes all have several things in common. They all tell us how to do something; and the usual format is as a list of steps or instructions. In addition, they are usually prefaced with a description of the raw materials that are needed (the input) to produce the end result (the output). We use the term algorithm to describe such lists of instructions. We assume that the reader may be unfamiliar with algorithms, so the first section of this appendix will introduce some of the components of the algorithms that appear in this book. Since we would like our algorithms to become computer programs in many cases, the notation will resemble a computer language such as Python or Sage; but our notation will be slightly less formal. In some cases we will also translate the pseudocode to Sage. Our goal will be to give mathematically correct descriptions of how to accomplish certain tasks. To this end, the second section of this appendix is an introduction to the Invariant Relation Theorem, which is a mechanism for algorithm verification that is related to Mathematical Induction
Most of the algorithms in this book will contain a combination of three kinds of steps: the assignment step, the conditional step, and the loop.
In order to assign a value to a variable, we use an assignment step, which takes the form: \begin{equation*} \textrm{Variable = Expression to be computed} \end{equation*} The equals sign in most languages is used for assignment but some languages may use variations such as := or a left pointing arrow. Logical equality, which produces a boolean result and would be used in conditional or looping steps, is most commonly expressed with a double-equals, ==.
An example of an assignment is k = n - 1 which tells us to subtract 1 from the value of n and assign that value to variable k. During the execution of an algorithm, a variable may take on only one value at a time. Another example of an assignment is k = k - 1. This is an instruction to subtract one from the value of k and then reassign that value to k.
Frequently there are steps that must be performed in an algorithm if and only if a certain condition is met. The conditional or "if ... then" step is then employed. For example, suppose that in step 2 of an algorithm we want to assure that the values of variables x and y satisfy the condition x <= y. The following step would accomplish this objective.
2. If x > y: 2.1 t = x 2.2 x = y 2.3 y = t
Steps 2.1 through 2.3 would be bypassed if the condition x > y were false before step 2.
One slight variation is the "if ... then ... else" step, which allows us to prescribe a step to be taken if the condition is false. For example, if you wanted to exercise today, you might look out the window and execute the following algorithm.
1. If it is cold or raining: exercise indoors else: go outside and run 2. Rest
The conditional step tells us to do something once if a logical condition is true. A loop tells us to repeat one or more steps, called the body of the loop, while the logical condition is true. Before every execution of the body, the condition is tested. The following flow diagram serves to illustrate the steps in a While loop.
Suppose you wanted to solve the equation \(f(x) = 0\text{.}\) The following initial assignment and loop could be employed.
1. c = your first guess 2. While f(c) != 0: c = another guess
Caution: One must always guard against the possibility that the condition of a While loop will never become false. Such "infinite loops" are the bane of beginning programmers. The loop above could very well be such a situation, particularly if the equation has no solution, or if the variable takes on real values
In cases where consecutive integer values are to be assigned to a variable, a different loop construction, a For loop, is often employed. For example, suppose we wanted to assign variable k each of the integer values from m to n and for each of these values perform some undefined steps. We could accomplish this with a While loop:
1. k := m 2. While k <= n: 2.1 execute some steps 2.2 k = k + l
Alternatively, we can perform these steps is with a For loop.
For k = m to n: execute some steps
For loops such as this one have the advantage of being shorter than the equivalent While loop. The While loop construction has the advantage of being able to handle more different situations than the For loop.
What are the inputs and outputs of the algorithms listed in the first sentence of this section?
What is wrong with this algorithm?
Input: a and b, integers Output: the value of c will be a - b (1) c = 0 (2) While a > b: (2.1) a := a - l (2.2) c := c + lAnswer
Describe, in words, what the following algorithm does:
Input: k, a positive integer Output: s = ? (1) s = 0 (2) While k > 0: (2.1) s = s + k (2.2) k = k - 1
Write While loops to replace the For loops in the following partial algorithms:
S = 0
for k = 1 to 5: S = S + k^2
The floor of a number is the greatest integer less than or equal to that number.
m = a positive integer greater than 1
B = floor(sqrt(m))
for i = 2 to B: if i divides evenly into m, jump to step 5
print "m is a prime" and exit
print "m is composite" and exit
Describe in words what the following algorithm does:
Input: n, a positive integer Output: k? (1) f= 0 (2) k=n (3) While k is even: (3.1) f = f+ 1 (3.2) k = k div 2
Fix the algorithm in Exercise 2.
Consider the following algorithm implemented in Sage to compute \(a^m mod \, n\text{,}\) given an arbitrary integer \(a\text{,}\) non-negative exponent \(m\text{,}\) and a modulus \(n\text{,}\) \(n \ge 0\text{.}\) The default sample evaluation computes \(2^5\, mod\,7 = 32\,mod\,7 = 4\text{,}\) but you can edit the final line for other inputs.
It should be fairly clear that this algorithm will successfully compute \(a^m (mod\, n)\) since it mimics the basic definition of exponentiation. However, this algorithm is highly inefficient. The algorithm that is most commonly used for the task of exponentiation is the following one, also implemented in Sage.
The only difficulty with the "fast algorithm" is that it might not be so obvious that it works. When implemented, it can be verified by example, but an even more rigorous verification can be done using the Invariant Relation Theorem. Before stating the theorem, we define some terminology.
Given a variable \(x\text{,}\) the pre value of \(x\text{,}\) denoted \(\grave x\text{,}\) is the value before an iteration of a loop. The post value, denoted \(\acute x\), is the value after the iteration.
In the fast exponentiation algorithm, the relationships between the pre and post values of the three variables are as follows. \begin{equation*} \acute{b} \equiv \grave{b} \grave{t}^{\grave{k} mod\,2}(mod\, n) \end{equation*} \begin{equation*} \acute{t} \equiv \grave t^2(mod\,n) \end{equation*} \begin{equation*} \acute k = \grave k//2 \end{equation*}
Given a algorithm's inputs and a set of variables that are used in the algorithm, an invariant relation is a set one or more equations that are true prior to entering a loop and remain true in every iteration of the loop.
We claim that the invariant relation in the fast algorithm is \(b t^k = a^m (mod\,n)\text{.}\) We will prove that his is indeed true below.
Given a loop within an algorithm, if \(R\) is a relation with the properties
R is true before entering the loop
the truth of R is maintained in any iteration of the loop
the condition for exiting the loop will always be reached in a finite number of iterations.
then R will be true upon exiting the loop.
We can verify the correctness of the fast exponentiation algorithm using the Invariant Relation Theorem. First we note that prior to entering the loop, \(b t^k = 1 a^m = a^m (mod\,n)\text{.}\) Assuming the relation is true at the start of any iteration, that is \(\grave{b} \grave{t}^{\grave k} = a^m (mod\,n)\text{,}\) then \begin{equation*} \begin{split} \acute{b} \acute{t}^{\acute{k}} & \equiv (\grave{b} \grave{t}^{\grave{k}\,mod\,2})(\grave t^2)^{ \grave k//2}(mod\,n)\\ & \equiv\grave{b} \grave{t}^{2(\grave{k}//2) +\grave{k}\,mod\,2 }(mod\,n) \\ & \equiv \grave{b} \grave{t}^{\grave{k}}(mod\,n)\\ & \equiv a^m (mod\,n) \end{split} \end{equation*} Finally, the value of \(k\) will decrease to zero in a finite number of steps because the number of binary digits of \(k\) decreases by one with each iteration. At the end of the loop, \begin{equation*} b = b t^0 = b t^k \equiv a^m(mod\,n) \end{equation*} which verifies the correctness of the algorithm.
How are the pre and post values in the slow exponentiation algorithm related? What is the invariant relation between the variables in the slow algorithm?
Verify the correctness of the following algorithm to compute the greatest common divisor of two integers that are not both zero.
HintVerify the correctness of the Binary Conversion Algorithm in Chapter 1.