LoginSignup
2

More than 3 years have passed since last update.

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

Posted at

蟻本p114の繰り返し二乗法をpythonで書いてみた:relaxed:
通常のべき乗を計算とどの程度高速化ができているかを$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()
#繰り返し2乗法を使う場合
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]

めっちゃ早い・・・!

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2