Python 实现 pow() 通过对非常大的整数进行平方来求幂

Question

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

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++

我正在自学 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
>>> 

不确定这一切都出了什么悲惨的错误。

Answer 1

问题是当你这样做时你正在乘以中间结果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。