I have the following exponentiation routine, which takes $O(\log n)$ stepsfunction power(a:real, n:positive integer)begin  x:=1;  i:=n;  while i > 0 do  begin    if(i % 2 == 1) then   //i odd      x:=x*a    i:=floor(i/2)    if(i > 0) then      a:=a*a  end;  power:=xendI'm trying to prove that it always gives $a^n$.  I think it might be provable via induction on $n$.  in the examples i went through i found that it always ends with $i=1$ before the final division down to $0$.
Proving correctness of an exponentiation routine
correctness proof;loops;program verification