C++ Loop Invariants

[jshm415]

Hello, I am learning how to find a loop invariant. For this particular problem, how is the answer val = i?

When you get up to i = 2, the value of val becomes 3.

If this is wrong, what would be the loop invariant?

int val = 0;

for(int i = 0 ; i < 10; i++)
{
val += val + 1;
}

At i = 0, val is 0
At i = 1, val is 1. (The total value of val is going to be three)
At i = 2, the value of val is 3. (3 + 3 + 1)

val = 3 and i =2 Therefore val != i

[giblit]

At i = 0, val is val + val + 1 = 0 + 0 + 1 = 1
at i = 1 valu is val + val + 1 = 1 + 1 + 1 = 3
at i = 2 val is val + val + 1 = 3 + 3 + 1 = 7.

Anyways if you compile with a cout you can see the results:

1 2 3 4 5 6 7 8 9 10 11 12 13

#include <iostream> int main() { int val = 0; const int Iterations = 10; for( int i = 0; i < Iterations; ++i ) { val += val + 1; std::cout << "Val = " << val << std::endl; } return 0; }

Val = 1 Val = 3 Val = 7 Val = 15 Val = 31 Val = 63 Val = 127 Val = 255 Val = 511 Val = 1023

http://ideone.com/GumGfu

[jshm415]

Oops, I made a mistake. In the original post I said : val = 1.

I meant val = i.

[giblit]

Anyways I thought a loop invariant was the same before and after the loop?

So If you did something like:

int i = 0;
for( ; i < 10; ++i )
{
    std::cout << i << std::endl;
}

i would be an invariant because it is less than 10 before and after.

I could be wrong though.