assume that the value of n is already initialized to a nonne

(assume that the value of n is already initialized to a non-negative integer).

(PS: Please write down detail steps of Initialization, Maintenance,Termination)

Solution

By defiition : A loop invariant is a formal statement about the relationship between variables in your program which holds true just before the loop is ever run (establishing the invariant) and is true again at the bottom of the loop, each time through the loop (maintaining the invariant).

Siplifiy the function as below

.. // the Loop Invariant must be true here
while ( TEST CONDITION ) {
// top of the loop
...
// bottom of the loop
// the Loop Invariant must be true here
}
// Termination + Loop Invariant = Goal

Write the algorithm for the function given .i.e power

int R = a;
int k = 1;

//Invariant: R = a * ... * a
//where the number of * operations = k-1

While (k < n)
{
   R = R * a;

   k++;

   //Invariant: R = a* ... * a
   //where the number of * operations = k-1 (starting k=0)
}

//Post condition: R = a * ... * a
//where the number of * operations = n-1

Here the goal of the loop is: \"Result: (a) multiplied by itself (n) times\"

Iitialization:

It should hold true just before entering the loop and after each iteration.

Maintainence:

  it will be true before and after each iteration i.e It should hold true just before entering the loop and after each iteration. It should give an idea about the current progress towards the final goal. Now loop invariant is \"Result (R) holds the multiplication of (a) by itself (k-1) times\".

Termination:

The code will terminate after  has reached the last value of n where the condition failsi.e

the loop terminates when (k = n) so we have k - 1 = n - 1 multiplications by the time we finish the loop. This is exactly the goal of the algorithm .