繰り返し二乗法をpythonで実装してみた

蟻本p114の繰り返し二乗法をpythonで書いてみた
通常のべき乗を計算とどの程度高速化ができているかを$3^{1000}$の計算で比較します。

####繰り返し二乗法の実装

import time

def pow(x, n):
  ans = 1
  while(n > 0):
    if(bin(n & 1) == bin(1)):
      ans = ans*x
    x = x*x
    n = n >> 1 #ビットシフト
  return ans

x = 3
y = 1000

start = time.time()
#繰り返し２乗法を使う場合
ans1 = pow(x,y)
elapsed_time1 = time.time() - start
print ("elapsed_time1:{0}".format(elapsed_time1) + "[sec]")
#通常のべき乗
ans2 = x**y
elapsed_time2 = time.time() - elapsed_time1
print ("elapsed_time2:{0}".format(elapsed_time2) + "[sec]")

####結果比較

#繰り返し二乗法
elapsed_time1:8.797645568847656e-05[sec] 
#通常のべき乗
elapsed_time2:1561884434.65922[sec]

めっちゃ早い・・・！