快速幂

发表于 更新于 分类于 Disqus：

快速幂

普通幂运算实现，例如计算 xnx^n 的函数。

需要注意的是，当n为负数的时候，需要进行转换，例如2−3=(12)32^{-3} = (\frac{1}{2})^{3}

//x为底数，n为幂
double my_pow(double x,int n){
    double ans{1};
    
    if(n<0){
        x = 1/x;
        n = -n;
    }
    for(int i{0};i<n;i++){
        ans*=x;
    }
    return ans;
}

普通幂需要计算n次乘法。

原理、实现

例如计算393^9

9=10012 39=310012=31∗20+0∗21+0∗22+1∗23=(31∗20)(30∗21)(30∗22)(31∗23) (31∗20)(30∗21)(30∗22)(31∗23)=(31∗20)(1)(1)(31∗23)(1)9 =1001_{2} \\ \space \\ 3^9 = 3^{1001_2} \\= 3^{1*2^0+0*2^1+0*2^2+1*2^3} \\ = (3^{1*2^0})(3^{0*2^1})(3^{0*2^2})(3^{1*2^3}) \\ \space \\ (3^{1*2^0})(3^{0*2^1})(3^{0*2^2})(3^{1*2^3})\\=(3^{1*2^0})(1)(1)(3^{1*2^3}) \tag{1}

32n32n−1=32n−1∗232n−1=32n−1(2)\dfrac{3^{2^n}}{3^{2^{n-1}}} = \frac{3^{2^{n-1}*2}}{3^{2^{n-1}}}={3^{2^{n-1}}} \tag{2}

我们把幂数转换为二进制，（2）式可以得出，数列 32n3^{2^n}的前一项的平方=下一项。

此时代码。

//x为底数，n为幂
double q_pow(double x,int n){

    double ans{1};
    if(n<0){
        x = 1/x;
        n = -n;
    }
    while(n!=0){
        if(n&1)ans*=x;  //如果当前的位是1，则乘数列的对应项。
        x*=x;  //根据（2）式计算下一项
        n>>=1;
    }
    return ans;
}

可以看出来，快速幂计算了2∗log2n2*log_2n次。

可以看出快速幂可显著减少乘法的运算次数。