尋找正整數的力量最快的算法是什麼？

Question

可能重複：
The most efficient way to implement an integer based power function pow(int, int)

只有兩個方法，我知道的是，

1. 單一的for循環：極其緩慢

2. 重寫遞歸計算。

我不知道是否有比這兩個更快的算法？任何按位技術都是受歡迎的。謝謝。

兩個算法C＃演示：

 class Math { 
     static public Int64 recurPow(Int64 a, Int64 e) { 
      if (e == 0) 
       return 1; 
      if (e == 1) 
       return a; 
      if ((e % 2) == 0) 
       return recurPow(a * a, e/2); 
      else 
       return recurPow(a * a, (e - 1)/2); 
     } 

     static public Int64 iterPow(Int64 a, Int64 e) { 
      Int64 result = a; 
      for (Int64 i = 1; i < e; ++i) 
       result *= a; 
      return result; 
     } 
    } 

Answer 1

的最優算法是NP完全問題，見http://en.wikipedia.org/wiki/Addition-chain_exponentiation

該頁面還鏈接了一些啓發式算法，給出不錯的答案，你可能想要其中之一。

你也在做comp3212嗎？