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

ちなみに、複数のステートメントをセミコロン ( ;) で区切って 1 行に入れることはお勧めしません。正当な構文ですが、あまり Pythonic ではありません。

于 2013-05-07T14:33:06.657 に答える