[阶乘]快速整乘方的log(N)算法


求一个数的N次幂

#include
double power(double a,int n)
{
    int mask,len=sizeof(int)*8-1;
    double s=1.0;
    if(n==0) return 1.0;
    if (n < 0)
    {
        n = -n;
        a = 1.0 / a;
    }
    for (mask = 0x4000; len > 0 && !(n & mask); --len, mask >>= 1);
    for (mask = 1; len > 0; --len, mask <<= 1, a *= a)
        if (n & mask)
            s *= a;
    return s;
}

int main()
{
    double a,s;
    int n;
    printf("a nn");
    scanf("%lf%d",&a,&n);
    s=power(a,n);
    printf("s= %fn",s);
    return 0;
}

解释:

算法极简单,变形 a^n = a^(2^t1+x^t2+...2^tm) = a^(2^t1) * a^(2^t2)... * a^(2^tm).

例:a^(2^tm) = (((a^2)^2)...)^2,tm次迭代。而n本身已经告诉了我们t1...tm的值,即各位的序号,用位操作可将其挖掘出来。按这个方法手工算一下a^7:
1. 7 = 0000...0111B = 2^0 + 2^1 + 2^2;
2. a^7 = a^(2^0) * a^(2^1) * a^(2^2)
3. 看出后一项是前项的平方,可用3次迭代a *= a即可。

再解释代码:
mask就是挖掘n某位的东西,0x4000相当于01000...0(1后14个零),最高位是符号位,在第1个for里右移,第2个for里左移,因为必须听a的,a只能不断累加;len在第一个for里记录n的最高位,在第二个for里仅当循环次数游标;就这些。

补:kk的直接移n的完美算法 for (; n; s *= n & 1 ? a : 1.0, a *= a, n >>= 1);

发表评论