算法-求f的n次方，高效实现方案。

Question

f是浮点数，n是整数。

Answer 1

public class Test2
{
/**
* 总共运算了2*s+res+1次
* @param args
*/
public static void main(String args[])
{
double f=2;//f
int n=10;//n
int s=(int) Math.sqrt(n);//求其开根的整数部分
double tfs=1,res=1,result=1;//f的s次方,剩余部分的幂,最终结果
for(int i=0;i<s;i++)tfs*=f;
for(int i=0;i<(n%s);i++)res*=f;
for(int i=0;i<(n/s);i++)result*=tfs;
System.out.println(result*res);//输出结果
}
}

Answer 2

根据二进制计算，时间复杂度应该在Log(n).

#define MAX_BIT_NUM 256
//计算2的正整数次幂，分奇偶计算,提高效率
int _binpower(int n)
{
int rst=1;
for(int i=0;i<n;++i){
if(n%2)
rst*=2;
else
rst=binpower(n/2)*binpower(n/2);
}
return rst;
}

//n为2的指数次方的结果
double _power2multiple(double a,int n)
{
double rst;
if(n==1)
return a;
rst=power2multiple(a,n/2);
return rst*rst;
}

double power(double a,int n) {
char b[MAX_BIT_NUM]={0};
double rst=1.0;
int c=n<0?-n:n;

//将c转化为二进制数组
int i=1;
while(c) {
b[i] =c%2; ++i; c>>=1;
}
b[0] = i;

int tmp = 0;
//利用二进制数组进行幂运算
for(i=1;i<=b[0];++i) {
if(b[i]) {
tmp=_binpower(i-1);
rst*=_power2multiple(a,tmp);
}
}
return n>0?rst:1.0/rst;
}