1

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

self made pow() c++

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.

Community
  • 1
  • 1
stackuser
  • 869
  • 16
  • 34

1 Answers1

2

The problem is that you are multiplying the intermediate results when you do x *= (x**2).... Instead, you just need to assign the newly computed value to x. Simply replace x*= with x= as follows:

def power(g_base,a,p_mod):
  x=1
  bits = "{0:b}".format(a)
  for i, bit in enumerate(bits):
    if bit=='1': x = (((x**2)*g_base)%p_mod)
    elif bit=='0': x = ((x**2)%p_mod)
  return x%p_mod

As a side note, I would not recommend putting multiple statements in one line separated by a semicolon (;). Although legal syntax, it is not very Pythonic.

Dhara
  • 6,587
  • 2
  • 31
  • 46