Error in integer exponentiation algorithm
gaba (guest) 10 Jul 2014 11:05
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.
