快速幂、快速幂取模的分析与代码实现

2019-04-13 12:29发布

写在前面

在网上搜了相关内容,感觉写的都不是特别详细,也没有人讲,只能自己理解了。下面会写一下这3个算法的分析与实现。当然都是基于自己的理解。因为博主搜了很多博客都是没有详细的解释,数学渣一脸懵逼啊。所以关于原理的解释如果有错误请一定要评论我改正!

朴素的求幂算法

也就是平常使用pow函数,最简单的实现就是一直累乘,可以得到这样的代码: int Pow(int a,int b){ int ans = 1; for(int i = 0;i < b;i++){ ans *= a; } return ans; } 可以看到,算法的时间复杂度是O(n)。为了降低时间复杂度,我们可以使用快速幂算法,将时间复杂度降低到O(logn),n是幂。

快速幂

关于快速幂,博主的理解是使用位运算。下面是数学证明: 关于a^b,举一个实际的例子——2^10。 那么对于6而言,如果我们将10变成二进制,那么就是:1010,如果变成加权的情况可以得到表达式: 0*2^0 + 1*2^1 + 0*2^2 + 1*2^3 代入原来的2^10可以得到表达式: 2^(0*2^0 + 1*2^1 + 0*2^2 + 1*2^3) 然后再拆开并化简这个表达式,可以得到: 2^(2^1) * 2^(2^3) 也就是说,我们在求解2^10的时候,可以考虑成根据二进制的权值来求解的。那么在关于位运算的部分,我们可以逐位获取b的位,碰到0,就累乘,碰到1,就将累乘的值乘到答案。由此可以得到代码: int Pow(int a,int b){ int ans = 1; int base = a; while(b){ if(b & 1) ans *= base; base *= base; b >>= 1; } return ans; }   关于位运算的部分,这里只简单提一下,更多详细内容请百度。if语句中的b & 1,也就是将b与1按位与,那么1的二进制是1,也就是说b除了最后一位,其他位都和0相与,那么得到的值一定都是0。而最后一位与上1,那么原来位实际上是不变的。这样我们就获得了b的最后一位的值。while循环中b >>= 1,是移位运算,将b向右移动1位。因为每次我们都是要获取最后一位,看是0还是1,那么每次移动1位,下一次在碰见if语句,就得到原来最后一位的前一位了。 核心代码是下面这一部分: if(b & 1) ans *= base; base *= base; b >>= 1; 博主理解这里理解半天Orz,这里其实是对上面一句话的模拟:“2^(2^1) * 2^(2^3)”。实际操作一下吧: 可以看到,出现0的时候,我们就累乘,得到的是幂的累积值。出现1的时候,我们将累积的幂值进行累乘。或者说碰见一个1,就出现一次底数2。 如果仍然没有太理解,debug一下会有很多帮助。

快速幂取模

这一部分就跟数论关系很大了。取模也是数论问题中经常出现的。那么对于幂来取模,如果我们直接用模运算实际上是速度很慢的(因为试除法)。所以我们不妨在求快速幂的时候添加一些内容,从而得到结果。这个算法需要了解一下数论的一个定理: (a*b) mod c = ((a mod c)*(b mod c)) mod c 那么根据上面的定理可以推导出另一个定理: (a^b) mod c = (a mod c)^b mod c 具体的证明这里不再赘述,主要是看第二个定理,恰好符合我们的小标题——快速幂取模。我们可以在求快速幂的时候,通过对底数取模的方式,不断缩小底数的规模。那么我们在上面快速幂的基础上,添加取模,就可以完成整个操作。 int pow_mod(int a,int b,int c){ int ans = 1; int base = a%c; while(b){ if(b & 1) ans = (ans*base)%c; base = (base*base)%c; b >>= 1; } return ans; } 如果能理解上面的快速幂算法,那么这个也会比较好理解了。定理里面,底数是要有一次取模运算的。这里我们在给base赋值的时候就运行了一次。那么对于后面的一次取模,我们实际上利用了分配率,即: (a*b) mod c = ((a mod c)*(b mod c)) mod c 我们求幂的本质仍然是求积。所以每次我们对base或者ans进行运算的时候,都必须使用一次分配率,所以都要mod c。