Part 2

Implement the following accelerated version of Euclids 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 250then 64. We subtract 64 from 186, getting 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.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.

NB. subtraction of the smaller y from the larger x.

There are two ways of doing the Euclidean algorithm and it is expected that students will use subtraction method for comparison.