I'm having issues trying to understand the word "invariant" and "variant" and how it relates to programming in c. It's used a lot in my textbook and its mentioned quite often by my professor but I can't seem to properly understand it even after reading other replies on stack overflow.
Here's one statement my prof mentioned:
"Euclid’s gcd algorithm works because it maintains the invariant gcd(m, n) = gcd(n, r), in which r = m mod n"
I think this is the dumbed-down pseudo code for Euclid's GCD that is mentioned:
gcd(m, n) = gcd(n, r)
I'm confused on the invariant portion of the phrase. From Wikipedia it says the invariant is "a logical assertion that is held to always be true during a certain phase of execution". But to be honest I don't quite understand what they mean.
Why is gcd(m,n) = gcd(n,r) considered an invariant? Would someone be able to dumb down the phrase so people as uneducated as my self could understand why the following example is an invariant?
And is there any simple variant program example that someone could provide so I can see the difference between a variant and invariant? I'd appreciate any help.
If we take Wikipedia definition, invariant would be "GCD of the current pair of numbers is the same as GCD of the original pair of numbers". The way we go from one pair to another one ({m,n} -> {n,m%n}) is, of course, part of the algorithm, but not really related to invariant.
So in these terms the algorithm could be described: every time we jump to an easier (smaller numbers) problem with the same answer.