Use a loop invariant to prove that the following program segment for computing the nth power, where n is a positive integer, of a real number x is correct.
power := 1 i := 1 while i <= n power := power*x i := i+1
Let p be the loop invariant and we need to prove that before, inside and termination of loop “power = x i−1 and i ≤ n + 1.”.
For iniatial case: i=1 and power = xi-1 = x0 =1;
In the loop: i<=n; Since I is incerement by 1; and we know that powerinitial =xi-1;
So, the new power will be powernew= powerinitial*x= xi-1*x = xi-1+1 = x(i+1)-1 ;
Now, We know that i=i+1; for new case
Then, on putting i in the place of (i+1), for new case
We get powernew= xi-1 ;
This process goes throughout the loop.
Now, after the termination of loop, ie. i<=n is false;
We get i=n+1;
by putting the value of i in power
powern = xi-1 = xn+1-1 = xn.
I hope it helps.
Thank you
Get Answers For Free
Most questions answered within 1 hours.