Below is the pseudocode for exponentiation by squaring. Precondtion: n greaterth

Question

Below is the pseudocode for exponentiation by squaring. Precondtion: n greaterthanorequalto 0 int power (int m, int n) {int x = m; int y = n; int result = 1; while (y is notequalto 0) {if (y is even) x = x * x; y = y/2;} else {result = result * x; y = y - 1;}} return result;} Postcondition: result = m^n Assume that the loop invariant is m^n = result * x^y. Show that 1) the invariant holds before the loop (base case), 2) assuming invariant holds after k-th iteration, and execution takes a k+1-st iteration, the invariant still holds (inductive step), 3) the loop exit condition and the loop invariant imply the postcondition result = m^n. Find a suitable decrementing function. Prove that the function is indeed a decrementing function.

Explanation / Answer

int power(int m,int n)

int x=m;

int y=n;

int result=1;

while(y!=0)

{

if(y is even)

{

x=x*x;

y=y/2;

if(y is even)

{

y=y/2;

x=x*x;

}

else {

result=result*x;

y=y-1;

x=x*x;

y=y/2;

}

}

else {

result=result*x;

y=y-1;

x=x*x;

y=y/2;

}

}

return result;

}

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.