爲什麼我的函數在輸入值magnatude中限制Python時間？

我試圖使該測試命令time Python中的功能。該函數應該採取m,n作爲參數，並計算MODEXP(a,e,p)其中p是素數發生器至多2^m和e在第一種情況是2^n和在第二種情況下是2^(n-1)並且a是隨機的正整數小於p。爲什麼我的函數在輸入值magnatude中限制Python時間？

這裏是我的代碼：

import random 
def question_3(m,n): 
    list = [] 
    for i in xrange(2,2**m): 
     flag=True 
     for num in list: 
      if(i%num==0): 
       flag=False 
     if(flag): 
      list.append(i) 
      p = choice(list) 
      a = randint(1,int(p)-1) 
      e = pow(2,n) 
    return pow(a, e, p) 

    time t = question_3(5,5) #non-Python syntax.

的問題是，與m和n此功能着的工作比20對他們倆的更大，我不知道爲什麼。

來源

2013-11-20 noazet abdo

這是您的實際代碼？我不認爲'time t = question_3（5,5）'是有效的Python語法。 – Kevin

實際上我是用鼠尾草做的，它是有效的 –

你的代碼不工作的方式是什麼？你得到一個錯誤還是它似乎掛起？如果for循環運行超過一百萬次（2 m，m => 20），代碼可能會掛起並不令人感到意外。同樣，一旦你打到m〜30，你的列表將開始達到最大可能的大小（如果你在一臺32位機器上）。 – JonathanV

你的代碼運行在我的盒子精美不掛。正如其他人指出的那樣，它是O（2 ** n），因此運行時間呈指數增長。這裏我的時間：

m = n = 2; time needed: 1.90734863281e-05 
m = n = 3; time needed: 1.50203704834e-05 
m = n = 4; time needed: 2.21729278564e-05 
m = n = 5; time needed: 4.38690185547e-05 
m = n = 6; time needed: 9.41753387451e-05 
m = n = 7; time needed: 0.000232934951782 
m = n = 8; time needed: 0.000643014907837 
m = n = 9; time needed: 0.00198698043823 
m = n = 10; time needed: 0.00656795501709 
m = n = 11; time needed: 0.0229339599609 
m = n = 12; time needed: 0.082200050354 
m = n = 13; time needed: 0.299206972122 
m = n = 14; time needed: 1.09857010841 
m = n = 15; time needed: 4.06366610527 
m = n = 16; time needed: 15.0994331837 
m = n = 17; time needed: 56.4191129208

對於m = n = 100，大概需要1.3 * 10^49秒。

來源

2013-11-20 18:09:32 Hyperboreus

好了，現在當我試圖讓M = N = 100這讓我這個OverflowError：Python的詮釋太大，轉換爲C長 –

顯然你的Python解釋器不支持任意長度的整數，（這可能是對SPEC） ... – Hyperboreus

@Hyperboreus：'xrange'在內部使用C長。在Python 3中'range'使用python abitrary-precision ints。 – geoffspear

爲什麼我的函數在輸入值magnatude中限制Python時間？

回答

相關問題