1

我正在尝试通过平方http://en.wikipedia.org/wiki/Exponentiation_by_squaring来滚动我自己的 pow() ，它使用幂运算一点一点地遍历二进制。如果这有助于您思考这个问题，那么这方面有一些问题：

Python 中用于浮点数的内置 pow() 和 math.pow() 之间的区别？

Python ** 和 % 大数字运算符的行为

自制 pow() C++

我正在自学 Python，所以这可能是我犯的一些简单错误。

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)

输出正确的是 31,21,12，错误的是 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
>>>

不知道这一切都在哪里发生了可悲的错误。

4

1 回答 1

2

问题是当你这样做时，你正在乘以中间结果 x *= (x**2)...。相反，您只需要将新计算的值分配给 x。只需替换x*=如下x=：

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

作为旁注，我不建议将多条语句放在一行中，用分号 ( ;) 分隔。虽然语法合法，但它不是很 Pythonic。

于 2013-05-07T14:33:06.657 回答