Hi, i've noticed that, while mathematically, the integer exponentiation algorithm given in class does 2*(l-1) operations at most, the algorithm actually given always does one more operation than required (and therefore does 2*(l-1)+1 at most)
def power(a,b): """ computes a**b using iterated squaring """ result=1 while b>0: # b is nonzero if b % 2 == 1: # b is odd result = result*a a=a**2 b = b//2 return result
Once b == 1, we first do a = a**2 and then do b=b//2. So now b is zero, and the new a is not multiplied by anything, and therefore squaring it was a meaningless operation. So the given algorithm doesnt do between l-1 and 2*(l-1) operations, but rather between l and 2*l-1 operations! There should be an "if" there somewhere to make the python algorithm truly mimic the math.