파이썬은 매우 큰 정수에 대해 제곱하여 지수화를 위해 pow()를 구현했습니다.

Question

제곱에 의한 지수화를 사용하는 비트 단위로 이진 비트를 넘기는 자체 pow()를 롤하려고합니다. http://en.wikipedia.org/wiki/Exponentiation_by_squaring. 그것은 몇 가지 간단한 실수 I 될 수 있도록

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

내가 파이썬 자신을 가르치고이이 문제에 대해 생각에서 당신을 도움이된다면이 분야에서 몇 가지 질문이 있었다 나는 만들고있어.

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) 

출력은 5,2,8와 31,21,12과 옳고 :이 모든 비극 잘못된 곳

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하지 않습니다.