Velocity Reviews > C++ > what is a loop invariant

what is a loop invariant

johan1990
Guest
Posts: n/a

 07-26-2011
i am reading introduction to algorithms and i have no idea of what the
concept "loop invariant" means. i really appreciate it if there is a
easy way to explain it. :~)

Victor Bazarov
Guest
Posts: n/a

 07-26-2011
On 7/26/2011 9:26 AM, johan1990 wrote:
> i am reading introduction to algorithms and i have no idea of what the
> concept "loop invariant" means. i really appreciate it if there is a
> easy way to explain it. :~)

Uh... http://en.wikipedia.org/wiki/Loop_invariant isn't easy? Try it.
Also, consider 'comp.programming' for general questions like that.

V
--

Saeed Amrollahi
Guest
Posts: n/a

 07-26-2011
On Jul 26, 4:26*pm, johan1990 <(E-Mail Removed)> wrote:
> i am reading introduction to algorithms and i have no idea of what the
> concept "loop invariant" means. i really appreciate it if there is a
> easy way to explain it. *:~)

Hi
From Accelerated C++ by Andrew Koenig & Barbara Moo, page 20:
... loop invariant is a property that we assert will be true about
a loop [like while or for loop] each time it is about to test
its condition.

for example:
int i = 0;
// invariant: we have said "hello" i times so far
while (i < 10) {
std::cout << "Hello, world!\n";
// we just said "hello" one more time and
// the invariant is false now
++i;
// increment i and now invariant is true again
}
// invariant is true, because at this point
// we have said "hello" 10 times

As Victor mentioned the loop invariant is a general
programming concept and it's not limited to C++.

Regards,
-- Saeed Amrollahi

Nick Keighley
Guest
Posts: n/a

 07-27-2011
On Jul 26, 10:55*pm, "Paul" <(E-Mail Removed)> wrote:
> "johan1990" <(E-Mail Removed)> wrote in message
>
> news:(E-Mail Removed)...
>
> >i am reading introduction to algorithms and i have no idea of what the
> > concept "loop invariant" means. i really appreciate it if there is a
> > easy way to explain it. *:~)

>
> Dunno what is a varaint and and invariant?
> Sounds like a varaible and a ?? maybe I am on the wroing track

yes

Juha Nieminen
Guest
Posts: n/a

 07-27-2011
Paul <(E-Mail Removed)> wrote:
>
> "johan1990" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed)...
>>i am reading introduction to algorithms and i have no idea of what the
>> concept "loop invariant" means. i really appreciate it if there is a
>> easy way to explain it. :~)

>
> Dunno what is a varaint and and invariant?
> Sounds like a varaible and a ?? maybe I am on the wroing track

If you don't know, why do you answer?

Todd Carnes
Guest
Posts: n/a

 07-27-2011
On Tue, 26 Jul 2011 10:02:50 -0400, Victor Bazarov wrote:

> On 7/26/2011 9:26 AM, johan1990 wrote:
>> i am reading introduction to algorithms and i have no idea of what the
>> concept "loop invariant" means. i really appreciate it if there is a
>> easy way to explain it. :~)

>
> Uh... http://en.wikipedia.org/wiki/Loop_invariant isn't easy? Try it.
> Also, consider 'comp.programming' for general questions like that.
>
> V

Actually, the Wikipedia article is NOT written very well. For example,
the very first sentence reads... "In computer science, a loop invariant
is an invariant used to prove properties of loops." When one is defining
something for someone, one should NEVER use the same word they are
explaining in the explanation. (in this case "invariant").

Also, the rest of the explanation expects the reader to be fairly well
versed in computer science & logic, which one cannot assume from the OP's
question.

Todd

Juha Nieminen
Guest
Posts: n/a

 07-27-2011
Paul <(E-Mail Removed)> wrote:
>> If you don't know, why do you answer?

>
> Because its a discussion group not just Q and A's.

If someone asks a question, he is expecting people who know the answer
to tell him. He does not expect people who have no idea to start guessing.
It was not a quiz to see who wins the prize for giving the correct answer.

If you don't know, but are interested in the answer yourself, the proper
reply is "I'm interested in knowing the answer to this question too".

Jorgen Grahn
Guest
Posts: n/a

 07-27-2011
On Wed, 2011-07-27, Todd Carnes wrote:
> On Tue, 26 Jul 2011 10:02:50 -0400, Victor Bazarov wrote:
>
>> On 7/26/2011 9:26 AM, johan1990 wrote:
>>> i am reading introduction to algorithms and i have no idea of what the
>>> concept "loop invariant" means. i really appreciate it if there is a
>>> easy way to explain it. :~)

>>
>> Uh... http://en.wikipedia.org/wiki/Loop_invariant isn't easy? Try it.
>> Also, consider 'comp.programming' for general questions like that.
>>
>> V

>
> Actually, the Wikipedia article is NOT written very well.

It reads like many other CS-related article: as if it's written by a
student who just came back from a lecture explaining loop invariants,
but who hasn't really digested it yet.

> For example,
> the very first sentence reads... "In computer science, a loop invariant
> is an invariant used to prove properties of loops." When one is defining
> something for someone, one should NEVER use the same word they are
> explaining in the explanation. (in this case "invariant").
>
> Also, the rest of the explanation expects the reader to be fairly well
> versed in computer science & logic, which one cannot assume from the OP's
> question.

This part of the intro doesn't ring true, either:

Informally, a loop invariant is a statement of the conditions that
should be true on entry into a loop and that are guaranteed to
remain true on every iteration of the loop. This means that on exit
from the loop both the loop invariant and the loop termination
condition can be guaranteed.

Maybe I have forgotten too much of what I once learned, but in this code

// A
while(expr) {
// B
}
// C

I understand a loop invariant to be something which I assert is always
true during all of B -- but not necessarily at C!

To the original poster: ask your lecturer. It's a course on algorithms
-- that's what (s)he's there for!

/Jorgen

--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .

Alf P. Steinbach
Guest
Posts: n/a

 07-27-2011
On 27.07.2011 23:22, Jorgen Grahn wrote:
>
> Maybe I have forgotten too much of what I once learned, but in this code
>
> // A
> while(expr) {
> // B
> }
> // C
>
> I understand a loop invariant to be something which I assert is always
> true during all of B -- but not necessarily at C!

No, that would be of little practical value.

The point of the loop INVARIANT is that it's true before the loop, and
after each iteration, so that it's guaranteed to be true after the loop.

The word "invariant" simply means unchanging, that it keeps on having
the same (boolean) value, namely the value true. We say that it HOLDS
when it's true, and that it doesn't hold or is BROKEN when it's false.
As with a class invariant it can and usually must be broken by the code
that does things, because things can't practically be done with that
invariant being true all the time. So the code must very carefully break
the invariant and then RE-ESTABLISH the invariant, every iteration.

It's the main thing that guarantees that IF the loop terminates, then
one knows that the loop invariant is true.

For example, to compute the integer power x^n (x raised to the n'th
power), one might choose an invariant like

pow = x^i

where i is a loop variable.

Then one might write

i = 0; pow = 1; // pow = x^i
while( i != n )
{
pow *= x; ++i; // pow = x^i
}
cout << pow << endl; // pow = x^i && i = n

One still doesn't know that the loop will terminate, however.

Maybe it will just go on forever?

So that part of proving a loop correct, relies on another value called
the loop VARIANT, where "variant" means "changing". It's an integer that
on every iteration gets closer to some value X (mathematicians prefer to
say that it decreases, and choose X = 0). And then you simply choose as
your loop continuation condition that the variant is not X.

Since the variant is an integer, it will reach X at some point.

In the example above, the variant is the variable i plus the fact that
it increases every loop iteration plus the ceiling value n.

A mathematician or computer scientist, being bound by the necessity of
conforming, will instead say that the variant is the expression n-i (or
any expression that behaves roughly the same way, like 2*(n-i)), where
it's implicit that it decreases every iteration, and that the floor
value is 0. With the implicit stuff it's simpler to communicate the
variant, but it's more difficult to reason about it. So that's their
choice, ease of communication rather than ease of reasoning.

I think the best treatment I have read about loop invariants and
variants was by Niklaus Wirth in an article in Scientific American.

He demonstrated how an algorithm expressed as a loop could be optimized
by changing it in ways that preserved the invariant and variant. This
resulted in a new and mucho faster algorithm. As I recall his article
involved the text search idea of skipping ahead a maximum number of
characters, with those maximum skips precomputed before the search.

Cheers & hth.,

- Alf

Geoff
Guest
Posts: n/a

 07-28-2011
On Tue, 26 Jul 2011 06:26:49 -0700 (PDT), johan1990 <(E-Mail Removed)>
wrote:

>i am reading introduction to algorithms and i have no idea of what the
>concept "loop invariant" means. i really appreciate it if there is a
>easy way to explain it. :~)

A loop invariant is any statement, variable or expression that does
not depend on the actions of the loop or any control variable of the
loop.

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Isaac Won Python 9 03-04-2013 10:08 AM Jonathan Lee C++ 3 07-31-2010 11:52 AM James Kanze C++ 0 07-30-2010 10:30 AM Giovanni Bajo Python 1 03-11-2008 11:34 PM DaKoadMunky C++ 8 12-05-2004 08:53 PM