寻找正整数的力量最快的算法是什么？

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吗？