Part 2

Implement the following accelerated version of Euclid's algorithm for gcd(s, t) with precondition 0 < s <= t. Use the programming conventions outlined in the online materials and the format below. Include preconditions, postconditions, and outcomes. Recall that outcomes must accumulate, so prior outcomes must be restored. Favor loops of the form while(!outcome) because they are readily verifiable. Explain efficiency as requested below.

Increment k until s^k <= t and s^k+1 > t, retaining s², s³, ... s^k. Diminish t by s^k. If (the new) t is still the larger of s and t, iterate down s², s³, ... s^k starting with s^k, repeating the process of finding the highest power of s to subtract from t. If the new t is the smaller of s and t, switch the roles.

For example, to find gcd(4, 250), s=4, and we consider 4, 4²=16, 64, 256. We subtract 64 from 250. The new t is 186. We start by considering 256which is too big to subtract from 256then 64. We subtract 64 from 186, getting 124 for t, and repeat the process. So we go from gcd(4, 250) to gcd(4, 186) to gcd(4, 122) to gcd(4, 58) to gcd(4, 42) to gcd(4, 26) to gcd(4, 10) to gcd(4, 6) to gcd(4, 2) to gcd(2, 2) = 2. (No switching of roles took place in this example.)

Part 2.1

Implementation (preferably Python, but Java is OK)

If you don't use the programming conventions outlined in the online materials, explain substantively why yours are easier to verify and analyze.

Your code replaces this

Part 2.2

Efficiency: "n"

What is "n" in this case? Explain.

Part 2.3

Best case time with explanation

Caution: don't overthink this.

Your response replaces this

Part 2.4

Worst case exploration

Take a worst case for the Euclidean algorithmgcd(2, n) where n is odd. For this case only, compare the time efficiency of the classical Euclidean algorithm with the efficiency of the algorithm described for Part 2.

The classical algorithm Your response replaces this.

The algorithm in part 2for this example Your response replaces this