Problem 4 - Discrete Mathematics with Applications

Question

Prove that the given predicate \(\mathrm{P}(n)\) in each algorithm is a loop invariant. Algorithm gcd \((x, y)\) (" This algorithm computes the gcd of two positive integers \(x\) and \(y .^{*}\) ) \(0 .\) Begin \((* \text { algorithm } *)\) 1\. while \(x \neq y\) do 2\. \(\quad\) if \(x>y\) then \(\begin{array}{ll}{3 .} & {x+x-y} \\ {4 .} & {\text { else }}\end{array}\) \(5 . \quad y \leftarrow y=x\) \(6 . \quad \operatorname{gcd}-x\) 7\. End \((* \text { al gorithm } *)\) \(P(n) : \operatorname{gcd}\left(x_{n}, y_{n}\right\\}=\operatorname{gcd}(x, y\\}\) where \(x_{n}\) and \(y_{n}\) denote the values of \(x\) and \(y\) at the end of \(n\) iterations of the loop.

Step-by-Step Solution

Answer

In summary, to prove that the given predicate \(P(n)\) is a loop invariant for the gcd algorithm, we have shown that: 1. The loop invariant holds before the loop starts (Initialization). 2. The loop invariant holds during the iterations of the loop (Maintenance). 3. The loop invariant gives us the desired result when the loop terminates (Termination). Thus, we have proven that the predicate \(P(n)\) is a loop invariant for the gcd algorithm.

Step 1: Initialization

Before the loop starts, we have the original values of \(x\) and \(y\). Since the initial values of \(x\) and \(y\) and their gcd are the same, we have \(\mathrm{gcd}(x_0, y_0) = \mathrm{gcd}(x, y)\), where \(x_0\) and \(y_0\) are the initial values of \(x\) and \(y\). Therefore, the loop invariant holds before the loop starts.

Step 2: Maintenance

To show that the loop invariant holds during the iterations of the loop, we will assume that the invariant holds before the loop and show that it still holds after the loop. Let's consider the two cases in the loop: Case 1: \(x > y\) In this case, the algorithm updates \(x\) to \(x \leftarrow x - y\). Since \(\mathrm{gcd}(x - y, y) = \mathrm{gcd}(x, y)\), we have \(\mathrm{gcd}(x_{n+1}, y_{n+1}) = \mathrm{gcd}(x_n - y_n, y_n) = \mathrm{gcd}(x, y)\). Thus, the loop invariant holds for this case. Case 2: \(x \leq y\) In this case, the algorithm updates \(y\) to \(y \leftarrow y - x\). Since \(\mathrm{gcd}(x, y - x) = \mathrm{gcd}(x, y)\), we have \(\mathrm{gcd}(x_{n+1}, y_{n+1}) = \mathrm{gcd}(x_n, y_n - x_n) = \mathrm{gcd}(x, y)\). Thus, the loop invariant holds for this case as well. Therefore, if the loop invariant holds before an iteration, it also holds after that iteration.

Step 3: Termination

The loop terminates when \(x = y\). At this point, we have \(\mathrm{gcd}(x, y) = \mathrm{gcd}(x_n, y_n) = x_n = y_n\). Since the loop invariant has been proven to hold for the entirety of the loop, we can conclude that the predicate \(P(n)\) is indeed a loop invariant for the gcd algorithm.

Key Concepts

Greatest Common Divisor (GCD)

The Greatest Common Divisor, often abbreviated as GCD, is a fundamental concept in number theory. It represents the largest positive integer that can divide two or more integers without leaving a remainder. For example, the GCD of 8 and 12 is 4. This is because 4 is the highest number that can equally divide both 8 and 12.
In order to compute the GCD, various algorithms can be used, among which the Euclidean algorithm is quite popular due to its efficiency. The Euclidean algorithm involves repeated division by remainders, progressively simplifying the problem. The given algorithm described in the exercise is another approach to finding the GCD using subtraction. When two numbers are equal, their GCD is the number itself. By repeatedly subtracting the smaller number from the larger and continuing this process, we eventually reach two equal numbers, which is the GCD.

Algorithm Correctness

To ensure that an algorithm works as intended, proving its correctness is a crucial step. This involves demonstrating that the algorithm yields the right output for all valid inputs.
The correctness of an algorithm can be verified through different methods:

• Initialization: Ensuring the algorithm starts in a correct state.
• Maintenance: Proving the algorithm remains in a correct state with each iteration or recursive call.
• Termination: Confirming that the algorithm eventually finishes and reaches the correct end state.

In our GCD algorithm, we use these steps to prove correctness. First, the initialization step ensures the loop invariant holds before the loop starts. Next, during the maintenance step, we check that the invariant is maintained for each iteration. Lastly, at termination, the goal is achieved when the two numbers become equal, proving the algorithm's correctness.

Mathematical Induction

Mathematical induction is a powerful proof technique used to verify the truth of an infinite number of cases. While this exercise doesn't directly require formal induction as a technique, it follows a similar logical structure.
Here's how mathematical induction works:

• Base Case: Verify the statement is true for the initial value.
• Inductive Step: Assume the statement holds for some arbitrary instance and then prove it holds for the next instance.

In the context of the loop invariant proof for the GCD algorithm, the step where we establish the invariant holds before the first loop iteration is analogous to verifying the base case in induction. Then, assuming it holds for an arbitrary iteration (inductive hypothesis), we show it holds for the next iteration (inductive step). This continues until we reach termination.

Predicate Logic

Predicate logic is a formal framework that allows us to make precise statements about mathematical objects. It's an extension of propositional logic, dealing with predicates and quantifying elements in statements.
In the given exercise, the predicate \(P(n)\) is used to express the idea that the GCD remains constant throughout the iterations of the algorithm. The predicate thus becomes a crucial part of proving that a specific property (in this case, the equality of the GCD at various stages) holds consistently.

• Universal quantification: Statements are universally quantified to hold for any possible input values of the variables involved.
• Variables and mappings: Variables such as \(x_n\) and \(y_n\) represent changing states in mathematical expressions.

Through predicate logic, we can concisely express complex logical ideas, allowing us to demonstrate that our assertions about the loop invariant and algorithm are universally correct, iterable, and consistent.