Consider the following program where a and n are positive in

Consider the following program, where a and n are positive integers. Input: a, n n y while (m 1) 1 if m is even m m/2 if m is odd m (m-1) /2; Output x*y

Solution

A loop variant is a condition which should be satisfied immediately before and after each iteration of a loop. The values of a and n should be given by user as per program given in the problem.

Assume the value of a and n entered by the user are 5 and 9 respectively. The loop invariant condition aⁿ = x^m * y should be satisfied before and after each iteration of the while loop given in the program.

Initially the value of a and n are 5 and 9 respectively. The values of x, m, and y are initialized as follows:

x = a; m = n; y = 1;

Therefore, the value of x, m, and y are 5, 9, and 1 respectively. Check whether the condition aⁿ = x^m * y is satisfied or not.

aⁿ = x^m * y

5⁹ = 5⁹ * 1

5⁹ = 5⁹

Therefore, the condition is satisfied before the while loop. Execute the while loop for the given values of x, m, a, n, and y.

Iteration 1:

y = x*y

            y = 5*1

y = 5

            x = x*x

            x = 5*5

x = 25

            m = (m - 1)/2

            m = (9 - 1)/2

            m = 8/2

m = 4

Check whether the condition aⁿ = x^m * y is satisfied after the first iteration. The value of a, m, x, and y are as follows:

a = 5, x = 25, m = 4, y = 25, n = 9

aⁿ = x^m * y

5⁹ = 25⁴ * 5

5⁹ = (5²)⁴ * 5

5⁹ = 5⁸ * 5

5⁹ = 5^{8 + 1}

5⁹ = 5⁹

The given loop invariant condition is also satisfied after the first iteration and before the next iteration of the while loop.

Iteration 2:

            x = x*x

            x = 25*25

x = 625

            m = m / 2

            m = 4 / 2

m = 2

Check whether the condition aⁿ = x^m * y is satisfied after the first iteration. The value of a, m, x, and y are as follows:

a = 5, x = 625, m = 2, y = 5, n = 9

aⁿ = x^m * y

5⁹ = 625² * 5

5⁹ = (5⁴)² * 5

5⁹ = 5⁸ * 5

5⁹ = 5^{8 + 1}

5⁹ = 5⁹

The given loop invariant condition is also satisfied after the first iteration and before the next iteration of the while loop.

Iteration 3:

            x = x*x

            x = 625*625

x = 390625

x = 5⁴ * 5⁴

            m = m / 2

            m = 2 / 2

m = 1

Check whether the condition aⁿ = x^m * y is satisfied after the first iteration. The value of a, m, x, and y are as follows:

a = 5, x = 390625, m = 1, y = 5, n = 9

aⁿ = x^m * y

5⁹ = (5⁴ * 5⁴)¹ * 5

5⁹ = 5⁴⁺⁴ * 5

5⁹ = 5⁸ * 5

5⁹ = 5^{8 + 1}

5⁹ = 5⁹

The given loop invariant condition is also satisfied after the first iteration and before the next iteration of the while loop.

Iteration 4:

            output = x*y

            output = 390625*5

output = 1953125

Since the loop invariant condition aⁿ = x^m * y is satisfied before and after each iteration of the while loop given in the program. Thus, it is proved by induction the while loop given in the program has the loop invariant: aⁿ = x^m * y.

Hence, the given program computes a power of a raise to n i.e., aⁿ. since the value of a is 5 and n = 9. The program will compute aⁿ = 5⁹ = 1953125. The output of the program is 1953125 if the value of a and n are 5 and 9 respectively.