pytorch中的log_softmax

快速幂

快速幂在ACM中是非常常用的一种算法，是常在求$a^{n}$但n很大的时候用于加速运算的算法（通常会对某个质数p取模），那快速幂为什么快？有多快？能否拓展到其他运算符中呢？

快速幂为什么快？有多快？

要了解快速幂为什么快就要先了解快速幂是怎么实现的，从其思想来看就是将n转换成二进制，并将其看成是多个2^x^（x为整数）相加的结果，将本该进行n次的运算降低到logn次，我们求出最大的2^x^需要进行logn次运算，而将这最多有logn个的结果再进行logn次运算，因此最终的时间复杂度为logn！

上代码！

const int p = 1e9+7;

int quick_pow(int a, int n){	//求a的n次方对p取模的值
    int ans=1;
    while(n){
        if(n&1) ans=(ans*a)%p;	//如果n当前位上的值为1，意味着我们需要乘上这个a
        a=a*a%p;	//位数每往高处走一位，就意味着a做了平方操作
        n>>=1;		//用n右移一位的方式来表示当前位数
    }
    return ans%p;
}

快速幂能否拓展？

答案是：可以！

假设现在的运算符为op。

我们将n个a都列出来，于是我们得到了

a op a op a op a……总共n个a进行op操作

按照快速幂的思想我们将这n个a进行划分，假设这里一共有6个a

a op a op a op a op a op a

很显然6=2+4，以二进制的形式表示也就是110，因此我们将这6个a划分为2个一组和4个一组，得到了

(a op a) op (a op a op a op a)

因此显然我们能够得到这样一个结论：当运算符满足结合律时，就可以用快速幂的思想对这个运算进行加速。例：加法，幂（可以尝试一下求$2^{2^{2^{2}}}$，连续幂运算是否能够如此加速）

但显然，如同减法、除法这种不满足结合律的运算就不能够使用快速幂进行加速。

最终代码：

#define op +
#define element_type int
#define e 0

element_type quick_pow(element_type a, int n){
    element_type ans=e;		//e在这里表示运算符op的单位元
    while(n){
        ans = ans op a;
        a = a op a;
        n>>=1;
    }
    return ans;
}

PS：想了解单位元相关知识移步线性代数中的特殊矩阵与二次型