Kiến thức

Tại sao pow (a, d, n) nhanh hơn rất nhiều so với a ** d% n?

110

Tôi đang cố gắng thực hiện

kiểm tra tính nguyên thủy Miller-Rabin

và không hiểu tại sao lại mất quá nhiều thời gian (> 20 giây) cho các số cỡ trung bình (~ 7 chữ số). Cuối cùng tôi đã tìm thấy dòng mã sau là nguồn gốc của vấn đề:

x = a**d % n

(trong đó a, dntất cả đều giống nhau, nhưng không bằng nhau, các số cỡ trung bình, **là toán tử lũy thừa và %là toán tử mô đun)

Sau đó, tôi đã thử thay thế nó bằng những thứ sau:

x = pow(a, d, n)

và so sánh thì nó gần như tức thời.

Đối với ngữ cảnh, đây là hàm gốc:

from random import randint  def primalityTest(n, k): if n < 2: return False if n % 2 == 0: return False s = 0 d = n - 1 while d % 2 == 0: s += 1 d >>= 1 for i in range(k): rand = randint(2, n - 2) x = rand**d % n # offending line if x == 1 or x == n - 1: continue for r in range(s): toReturn = True x = pow(x, 2, n) if x == 1: return False if x == n - 1: toReturn = False break if toReturn: return False return True  print(primalityTest(2700643,1)) 

Một ví dụ về tính thời gian:

from timeit import timeit  a = 2505626 d = 1520321 n = 2700643  def testA(): print(a**d % n)  def testB(): print(pow(a, d, n))  print("time: %(time)fs" % {"time":timeit("testA()", setup="from __main__ import testA", number=1)}) print("time: %(time)fs" % {"time":timeit("testB()", setup="from __main__ import testB", number=1)}) 

Đầu ra (chạy với PyPy 1.9.0):

2642565 time: 23.785543s 2642565 time: 0.000030s 

Đầu ra (chạy với Python 3.3.0, 2.7.2 trả về thời gian rất giống nhau):

2642565 time: 14.426975s 2642565 time: 0.000021s 

Và một câu hỏi liên quan, tại sao phép tính này nhanh hơn gần như gấp đôi khi chạy với Python 2 hoặc 3 so với PyPy, trong khi thường thì PyPy

nhanh hơn nhiều

?

python

 

performance

 

pypy

 

lyallcooper

nguồn

Chuyên mục: Kiến thức

Related Articles

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

Check Also
Close
Back to top button
444 live app 444 live 444 live app 444live kisslive kiss live yy live yylive