Consider the following version of the Euclidean algorithm to compute god(a, b). Start with computing the largest power of 2 dividing both a and b. If this is 2", then divide a and b by 2". After this "preprocessing", do the following: Step 1: Swap the numbers if necessary to have a s b; Step 2: If a # 0, then check the parities of a and b; if a is even, and b is odd, then replace a by a/2; if both a and b are odd, then replace b by b - a; in each case, go to step (1); Step 3: If a = 0, then return 2" b as the greatest common denominator.(c) Show that the modified Euclidean algorithm always terminates with the right answer (d) Show that this algorithm, when applied to two 100-digit integers, does not take more than 1500 iterations