Section 5.5, Number 12, NOT included in solutions manual The following sentence

Question

Section 5.5, Number 12, NOT included in solutions manual The following sentence could be added to the loop invariant for the Euclidean algorithm: There exists integers u,v, s, and t such that a=uA+vB and b=sA+tB a. Show that this sentence is a loop invariant for while (b DNE 0) r:= a mod b a:=b b:=r end while b. Show that if initially a=A and b=B, then sentence is true before the first iteration of the loop. c. Explain how the correctness proof for the Euclidean algorithm together with the results of (a) and (b) above allow you to conclude that given any integers A and B with A > B >= 0, there exist integers u and v so that gcd(A,B)=uA+vB d. By actually calculating u,v,s, and t at each stage of execution of the Euclidean algorithm, find integers u and v so that gcd(330,156)=330u+156v.

Explanation / Answer

(a)Assume that after a number of loop executions the current values of the variables are aold,bold, and

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---