Consider the following code. int f(int x, int y) { int r = 1; while (y...

 

Transcribed Image Text:

Consider the following code. int f(int x, int y) { int r = 1; while (y > 1) { if (y % 2 == 1) { r = x * r; 1 2 3 4 5 6 7 8 9 } x = x= x; y = y / 2; } 10 return rx; 11 } 1. Complete the following table for iterations 0,1,2,3, 4 (iteration 0 means outside of the loop) iteration xy loop invariant 0 1 2 4 2. Find a loop invariant that involves r? 3. Find a loop invariant that involves x and y? 4. Formally prove that the loop invariant in part (b) (that involves x and y) is true before and after each execution of the loop. That is, you need to prove that the loop invariant holds true initially, then at the end of each iteration. 5. This function returns r r. What does it computes in terms of the inputs x and y? Consider the following code. int f(int x, int y) { int r = 1; while (y > 1) { if (y % 2 == 1) { r = x * r; 1 2 3 4 5 6 7 8 9 } x = x= x; y = y / 2; } 10 return rx; 11 } 1. Complete the following table for iterations 0,1,2,3, 4 (iteration 0 means outside of the loop) iteration xy loop invariant 0 1 2 4 2. Find a loop invariant that involves r? 3. Find a loop invariant that involves x and y? 4. Formally prove that the loop invariant in part (b) (that involves x and y) is true before and after each execution of the loop. That is, you need to prove that the loop invariant holds true initially, then at the end of each iteration. 5. This function returns r r. What does it computes in terms of the inputs x and y?

Answer rating: 100% (QA)

1 Initially x 3 r 1 y 4 first iteration y 2 1 is false So r remains sam... View the full answer