遞歸的效率與指數的迭代

所以我試圖實現一個更有效的方法來計算2^n。遞歸的效率與指數的迭代

我知道你可以將它分割爲O(logn)，使用遞歸很容易。當它的奇數（或類似的東西）時，你保持2除以乘以更低的權力。問題是我用手寫出了我的乘法方法，因爲它的數字很大。所以它需要返回多個參數。

我能想到的一個解決方案是製作一個包含所有需要的信息的對。除此之外，儘管我試圖找出如何使用迭代編寫它。我能看到的唯一方法是使用某種數據結構，然後通過將n除以2並在n爲奇數時存儲該值來循環。然後編寫一個for循環，並在每次迭代時檢查該值是否包含在數據結構中。在我看來，這似乎是一個相對昂貴的操作。

它有可能最終效率低於遞歸版本嗎？

我這樣做是因爲：

我不能讓國民生產總值的工作。
我想我正在學習寫大數課並與之合作。

來源

2012-01-17 emschorsch

您是否嘗試過移位？或者你是否需要十進制這個非常大的數字？ – Mysticial 2012-01-17 05:56:38

我只使用自然數，但他們需要精確到2^100000這麼大的數字，目前我的程序需要13秒才能完成，因爲如果指數是2的乘方因爲迭代過程很簡單，高效的算法達到一個點，然後開始乘以2增加所花費的時間。 – emschorsch 2012-01-17 06:01:10

相關：http://stackoverflow.com/questions/8771713/efficient-exponentiation-for-huge-numbers-im-talking-googols如果你想在十進制而不是二進制答案。那麼更多的是如何從二進制轉換爲十進制的問題。 – Mysticial 2012-01-17 06:08:21

如果您打算使用大數字而不是重新發明輪子，那麼您可能應該查看GNU MP Bignum Library。

關於遞歸與迭代的問題，答案是你總是可以把它們寫成等價的;一個只能自稱爲tail call的遞歸函數與while循環一樣高效（前提是您的編譯器支持尾部調用優化，但最常用的編譯器是）。舉例來說，你所描述的快速冪函數的尾遞歸版本（僞代碼）：

function fastExp(base, exponent, accumulator) { 
    if(exponent == 0) { 
    return accumulator; 
    } else if(exponent % 2 == 0) { 
    return fastExp(base * base, exponent/2, accumulator); 
    } else { 
    return fastExp(base, exponent-1, base * accumulator); 
    } 
}

覺得這個遞歸函數爲一個循環，在循環條件是exponent != 0的，和遞歸呼叫類似於goto s到循環的開始。（您需要accumulator = 1調用它，當你開始，順便說一句。）這是等同於以下：

function fastExp(base, exponent) { 
    var accumulator = 1; 
    while(exponent != 0) { 
    if(exponent % 2 == 0) { 
     base *= base; 
     exponent /= 2; 
    } else { 
     exponent -= 1; 
     accumulator *= base; 
    } 
    } 
    return accumulator; 
}

所以你可以看到，他們是等價的，因此，將執行相同數量的操作。

來源

2012-01-17 05:57:19 Philippe

您的聲明，即帶有尾調用的遞歸函數與while循環一樣高效，只有編譯器優化它時纔是如此。雖然gcc的確如此，但我不知道它的普遍性如何，因爲編寫尾遞歸代碼在C++中並不常見。 – celtschk 2012-01-17 06:20:15

這是一個有效的觀點。 gcc做到了，Visual Studio做到了，LLVM做到了。我不確定其他人，但我敢說，任何嚴肅的編譯器都會實現這種優化。 – Philippe 2012-01-17 06:23:33

多數民衆贊成我很高興我應該玩更多的指數來找到這樣的規則纔剛剛來到這裏，問這個問題。我想爲我的代碼進行一次優化，因爲我正在使用一個數組，我將包含一個if如果accumulator = 1會測試哪個會節省時間，特別是如果指數是2^n的非常大的冪。儘管我猜想保存的最大時間是答案中數字的兩倍（我的代碼中有2個循環）。 – emschorsch 2012-01-17 06:34:39

如果要存儲一切爲個序列和 s..ie。在二進制格式，2^n是簡單地通過一個單一1a的前面小號序列，也許你可以用事實來簡單的代碼

2^1 = 10 
2^2 = 100 
2^3 = 1000 
2^4 = 10000

等等等等，除非這是一個學習練習，我會用一個標準的任意精度庫像什麼菲利普建議

走

來源

2012-01-17 06:00:02

我的實現目前是一個整數，其中每個索引代表一個數字。我可能會將其轉換爲矢量，但我仍然會遇到大部分相同的問題。 – emschorsch 2012-01-17 06:04:54

@emschorsch如果你將你的號碼存儲在基數2的數組中，這是非常簡單的 – 2012-01-17 06:05:26

但是然後我必須轉換回十進制的最終答案。 – emschorsch 2012-01-17 06:20:15

遞歸的效率與指數的迭代

回答

相關問題