Consider the following algorithm Power(x, y), which takes as inputtwo positive i

Question

Consider the following algorithm Power(x, y), which takes as inputtwo positive integers x and y:

Algorithm Power(x, y):

z = 1; a = x; b = y;

while b != 0

do if b is even

then b = b/2; a = a^2

else b = b 1; z = az

endif

endwhile;

return z

(3.1) Prove that the algorithm maintains the followinginvariant:

[a^b] z = X^y .

(3.2) Prove that the value of z that is returned by the algorithmis equal to x^y

Consider the following algorithm Power(x, y), which takes as inputtwo positive integers x and y:

Algorithm Power(x, y):

z = 1; a = x; b = y;

while b != 0

do if b is even

then b = b/2; a = a^2

else b = b 1; z = az

endif

endwhile;

return z

(3.1) Prove that the algorithm maintains the followinginvariant:

[a^b] z = X^y .

(3.2) Prove that the value of z that is returned by the algorithmis equal to x^y

Explanation / Answer

3.1) step-1: Initially a=x, b=y and z=1              [a^b]z =[x^b]z      [substituting x for a, y for b and1 for z gives]                      = [x^y].1                        = x^y     Therefore the invariant is being followedinitially. step-2: Assume that it follows in nthstep and we will prove that invariant will be followed in n+1 thstep suppose values in nth step are an, bn,zn and [an ^ bn] zn = x^yas it follows the invariant in step-n Therefore step-n+1 has two cases i) when bn is even     then bn+1 = bn /2           an+1= (an)2             zn+1 = zn now [an+1 ^ bn+1] zn+1 =[an2 ^ bn/2]zn                                 = [an ^bn] zn                                   = x^y ii) when bn is odd     then bn+1 = bn -1           an+1= an             zn+1 = an zn now [an+1 ^ bn+1] zn+1 = [an^ bn-1] anzn                                 = [an ^bn] zn                                   =x^y Therefore in both the case the invariant is being followed Therefore our algorithm is following the invariant 3.2) In every step z is being multiplied by a2 or remainingthe same The number of steps would be ceiling of b/2 i) if b is odd initially,     z will be multiplied by a for the first time     and in the remaining steps it will be multipliedby a2     Therefore in the final step z contains (a)*[(a^2) * (a^2).......b-1/2 times]                                                        =x^y i) if b is even initially,    z will be multiplied by a2 every time     Therefore in the final step zcontains [(a^2) * (a^2).......b/2 times]                                                        =x^y Therefore the final value of z containsx^y

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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