I'm trying to roll my own pow() which goes over a binary bit by bit using exponentiation by squaring http://en.wikipedia.org/wiki/Exponentiation_by_squaring. There were some questions in this area if this helps you in thinking about this problem:
Difference between the built-in pow() and math.pow() for floats, in Python?
Behavior of Python ** and % operators with big numbers
I'm teaching myself Python so it may be some simple mistake I'm making.
def power(g_base,a,p_mod): x=1; b=[1]; bits = "{0:b}".format(a) for bit in bits: if bit=='1': x *= (((x**2)*g_base)%p_mod) elif bit=='0': x *= ((x**2)%p_mod) else: x *= 1 #t = [b.append(((x**2)*g_base)%p_mod) if bit == '1' else b.append((x**2)%p_mod) for bit in bits] return x%p_mod a,b,c=5,2,8 #a,b,c=31,21,12 print "power(): ",power(a,b,c) print "pow(): ",pow(a,b,c) The output is right with 31,21,12 and wrong with 5,2,8:
Python 2.7 (r27:82525, Jul 4 2010, 09:01:59) [MSC v.1500 32 bit (Intel)] on win32 Type "copyright", "credits" or "license()" for more information. >>> ================================ RESTART ================================ >>> power(): 5 pow(): 1 >>> ================================ RESTART ================================ >>> power(): 7 pow(): 7 >>> Not sure where this all went tragically wrong.
