Implement the following accelerated version of Euclid's algorithm for gcd(s, t) with precondition 1 < s <= t. Use the programming conventions outlined in the online materials and the format below. Include preconditions, postconditions, and invariant outcomes. Recall that prior outcomes must be restored to remain invariant. 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 or switching the roles of s and 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, 4³=64, 4⁴=256. We subtract 64 from 250 (256 is too big). The new t is 186. We start by considering 256—which is too big to subtract from 250—then 64. We subtract 64 from 186, obtaining 122 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. There was a switching of roles in the digits in the last step.

 

Part 2.1 Implementation (preferably Python, but Java is OK) 

Use the programming conventions outlined in the online materials.

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.

Part 2.4 Worst case exploration 

Take the case for the Euclidean algorithm—gcd(3, n) where n is even. For this case only, compare the time efficiency of the classical Euclidean algorithm with the efficiency of the algorithm described for Part 2.