emillon
Joined 16 years ago
Karma
2,853
Submissions
394
Member since
Jan 10
Paris-based λ-term writer.
View on Hacker NewsJoined 16 years ago
- correction: define a loop invariant. Assuming the loop terminates, it will hold when the program exits the loop.
- termination: define a loop variant, something that changes at every iteration. If you can find a variant that is a strictly decreasing sequence of natural numbers (or an increasing, bounded sequence), you've established that the loop terminates.
Once you've done these two steps you know that the program terminates and the invariant holds at the end. (in your case, you won't be able to find a good variant - depending on the floating point semantics you use of course).