Finding a good loop invariant for a powering procedure
-
03-11-2019 - |
Question
Consider the following algorithm for computing integer powers:
Procedure power(integer x, integer n)
power := 1
for i := 1 to n
power := power * x
return power
Can we say that the loop invariant is $power \leq x^n$ ?
Before the loop $power$ is initialized to $1$ so its equal to $1 \leq x^n$.
How do we prove maintenance of the invariant?
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange