Importance of Loop Invariant in programming

Introduction:

It is hard to keep track of what is happening with loops. Loops which don’t terminate or terminate without achieving their goal behavior is a common problem in computer programming. Loop invariants help. A loop invariant is a formal statement about the relationship between variables in your program which holds true just before the loop is ever run (establishing the invariant) and is true again at the bottom of the loop, each time through the loop (maintaining the invariant).

Why Loop Invariant:
It captures what the loop does not do, i.e., what it leaves unchanged over any single execution of the loop body (and hence over the entire execution of the loop)

Loop Invariant

  •     Invariant means unchanged
  •     The person who writes the loop, also writes the loop invariant which describes what remains unchanged
  •     Permits understanding what the loop does without having to understand (at the same time) how it does it.
  •     We can reason about the loop’s effect on the larger program without hand tracing each loop iteration.

 General Pattern of loop invariant in Code

...
// the Loop Invariant must be true here
while ( TEST CONDITION ) {
// top of the loop
......
......
// bottom of the loop
// the Loop Invariant must be true here
}
// Termination + Loop Invariant = Goal
...
invariant + termination => goal

Below code is example of Loop Invariant

  
  int j = 10;
  for(int i=0; i<11; i++)
   {  
     // Your loop code stuff
     j--;
   } 
  At the end i+j = 10
  so here J= 10 is loop invariant

If you Understand Give me the answer of

 if (i % 2 == 0)
 {
   while (i>=0)
    {
       i = i/2;
       if (i%2 != 0)
         {
       i =i-1;
     }
       else
         {
           i= i-2
         }
    }
 }

 What is appropriate loop invariant for the while loop _________

Reference Link: http://www.cs.miami.edu/~burt/learning/Math120.1/Notes/LoopInvar.html

http://stackoverflow.com/questions/3221577/what-is-a-loop-invariant

Page keyword: What is loop invariant, loop invariant in while loop, loop invariant example, loop invariant code example

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s